平方根を見つけることの複雑さ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 22:39 UTC 版)
「平方剰余」の記事における「平方根を見つけることの複雑さ」の解説
つまり、数値 a と法 n が与えられたときに、以下のタスクがどれほど難しいか、ということである。 x2 ≡ a (mod n) の解 x が存在するかどうかの判定 存在すると仮定して、その具体的な計算 ここでは、法が素数と合成数の場合で重要な違いが明らかになる。 素数 p を法として、平方剰余 a は 1 + (a|p) 個の根を持つ（つまり、 a N p の場合は根なし、 a ≡ 0 (mod p) の場合は1個、a R p で(a,p) = 1 の場合は2個。） 一般に、もし法が合成数 n であれば、 n を異なる素数のべき乗の積として表現したときに、その最初のものを法として根の数が n1 個、次のものを法として根の数が n2 個…と続けていくと、nを法として n1n2... 個の根が存在する。 素数のべき乗を法とする解を組み合わせて n を法とする解を作る理論的な方法は、中国の剰余定理と呼ばれ、効率的なアルゴリズムで実装できる。 例えば： x2 ≡ 6 (mod 15) を解く。x2 ≡ 6 (mod 3) は1つの解 x = 0、x2 ≡ 6 (mod 5) が2つの解 x = 1, 4 を持つ。 したがって、15を法として2つの解 x = 6, 9 が存在する。 x2 ≡ 4 (mod 15) を解く。x2 ≡ 4 (mod 3) は2つの解 x = 1, 2、x2 ≡ 4 (mod 5) が2つの解 x = 2, 3 を持つ。 したがって、15を法として4つの解 x = 2, 7, 8, 13 が存在する。 x2 ≡ 7 (mod 15) を解く。x2 ≡ 7 (mod 3) は2つの解 x = 1, 2 を持ち、x2 ≡ 7 (mod 5) は解が存在しない。 したがって、15を法として解が存在しない。
※この「平方根を見つけることの複雑さ」の解説は、「平方剰余」の解説の一部です。
「平方根を見つけることの複雑さ」を含む「平方剰余」の記事については、「平方剰余」の概要を参照ください。
- 平方根を見つけることの複雑さのページへのリンク
