元祖ワシ的日記

有限体Fp上で

x^2 = a

を解くことを考えます。根があるかないかは平方剰余の相互法則
 

x^2 = aが Fp根を持つ
<=>
(a/p) = 1 (ルジャンドルの記号)
<=>
a^(p-1)/2 = 1

で簡単に分かるのですが具体的にxが何であるかを求めるにはどうしたらよいのでしょうか？

Fpは有限群なので全ての元について根かどうかを解けばよいのですが、この手法はpが大きくなると破綻するのは自明です。そこで、ここでは別のアプローチを紹介します。

以下 aはFpで平方剰余であると仮定しておきます。また実数の世界にあやかって、x^2=aなるxを√aと表すことにします。（このようなxは2つ存在しもう一方は-√aです）。

pが4n+3型の素数のとき

pが4n+3ならば話は簡単です。

aは平方剰余なので

a^(p-1)/2 = 1

です。この両辺にaをさらに掛ければ

a^(p+1)/2 = a

となります。しかし、(p+1)/2は偶数ですから

a^(p+1)/4 = √a

ゆえに a^(p+1)/4が根(のうちの1つ)です。

pが4n+1型の素数のとき

この場合(p-1)/2が偶数のため(p+1)/2が奇数となり上の手法は使うことができません。ならば(p-1)が奇数になるまで 2で割るのはどうでしょうか？すなわち

p-1 = 2^k * s

とし、a^s乗を考えるのです。このa^s はあと2^k乗すれば 1になるのですから1の2^k乗根です。このa^sは原始的かどうか（すなわち 2^k乗根して始めて1になるかどうか）はわかりません。しかし仮に１つ原始2^k乗根を知っているとすれば全ての2^k乗根は

1, r, r^2, r^3, ..., r^(2^k-1)

とかけます。このようなrはこちらの手法で試行錯誤的に（だが簡単に）見つけることができます。さらに aは平方剰余だということがわかっているので実際は偶数番目だけのどれかであり、

a^s  = r^2n 

と書けます。このnが何かは今はわかりません。（この手法では最後までこのnが何かはわかりません）。しかし、nが何であるかわからなくても r^2n * r^2m=1となるようなmを見つけることができます。それには次の性質を利用します。

x, y が原始N乗根ならば x * y は原始N/2乗根である。

つまり原始128乗根どうしを掛け合わせると原始64乗根になるということです。ある数が原始何乗根かどうかはその数を自乗していき-1になる冪を調べればわかります。以下例で説明したほうがわかりやすいと思いますので例で解説します。

例

p=769 , a=8として  x^2 = a を解くとします。p-1=768 = 3 * 2^8 ですからF769には原始256乗根が存在し、試行錯誤法で計算するとr=7であることがわかります。

a^3 = 8^3 = 512

です。512は

512^64 = -1

ですから、原始128乗根の1つ、すなわち

1, 7^2, 7^4, ... 7^254

のうちのどれかです。

そこで原始128乗根である 7^2 = 49 をかけることにより原始64乗根（もしくはそれ以上）にすることができます。実際かけてみると

8^3 * 7^2 = 480

となり480は

480^32 = -1

ですから、原始64乗根です。そこで原始64乗根である 7^4 を両辺にかけます

8^3 * 7^2 * 7^4 = 518

518は同様の計算で原始32乗根ですから 7^8を両辺にかけます。

8^3 * 7^2 * 7^4 * 7^8 = 729

729は原始8乗根です（原始１６乗根をすっとばして2段階あがった）ので、両辺に7^32をかけます

8^3 * 7^2 * 7^4 * 7^8 * 7^32 = 707

707は原始4乗根ですから両辺に7^64をかけます。

8^3 * 7^2 * 7^4 * 7^8 * 7^32 * 7^64 = 1

ここで始めて1となりました。両辺に8をかけると

8 * 8^3 * 7^2 * 7^4 * 7^8 * 7^32 * 7^64 = 8

となり左辺の指数はすべて偶数です。故に

8^2 * 7 * 7^2 * 7^4 * 7^16 * 7^32 = √8

となります。左辺を計算してみると503になります。たしかに

503^2 = 8

です。