元祖ワシ的日記

$$x^2=a \pmod p$$
を求めるアルゴリズムとその原理の紹介です。アルゴリズムについては
mod pでの平方根
に書いてあるものと基本的に同じです。
任意の素数$p$に対して

$$a^{\frac{p-1}{2}} = \pm 1\pmod p$$

が成立しその符号は$a$が平方剰余かどうかで決まります。今回二乗して$a$になる数を探すので$a$は必ず平方剰余です。つまり上式の値は1です。この式の両辺にさらに$a$を乗ずると

$$a^{\frac{p+1}{2}} = a\pmod p$$

よって$\frac{p+1}{2}$が偶数なら

$$(a^{\frac{p+1}{4}})^2 = a\pmod p$$

よって

$$a^{\frac{p+1}{4}}$$
が解になります。これは$p$が$4N+3$型の素数のときに使えます。簡単ですね。

 

例)

$p=31$として、2の平方根を求めてみる。

$2^{15}=1\pmod{p}$

だから両辺に2を乗じて

$2^{16}=2\pmod{p}$

を得る。よって$2^8$が平方根になる。実際に計算してみると

$2^8=8\pmod{p}$であるから8が2の平方根である。実際$8^2=2\pmod{p}$である。

 

そうではないとき（つまり$p$が$4N+1$型の素数のとき）は次のように考えます。

$$a^{\frac{p-1}{4}}=\pm 1 \pmod{p}$$

です。ここから両辺に$a$を乗ずると

$$a^{\frac{p+3}{4}}=\pm a \pmod{p}$$

よって$p$が$8N+5$型の素数ならば

$$\pm (a^{\frac{p+3}{8}})^2= a \pmod{p}$$
符号が正の場合は$a^{\frac{p+3}{8}}$が解になります。

負の場合は$4N+1$型の素数は-1が平方剰余であるのであらかじめ$-1$の根号($x^2$=-1となる数。仮に$i$と記述する）を求めておけば $ia^{\frac{p+3}{8}}$が解になります。

$i$は平方非剰余の数を$(p-1)/4$すれば見つかります。$1\cdots p-1$なる数のうち半数が平方剰余で半数が平方非剰余ですから2から順番に探索していけば高確率ですぐ見つかりますが$8N+5$型については2が常に平方非剰余ですので$2^{(p-1)/4}$をあらかじめ計算しておけば良いことになります。

 

例)

$p=101$として$5$の平方根を求める。

$5^{(101+3)/8}=56\pmod{p}$

である。よって56が平方根の可能性がある。実際計算をしてみると

$56^2=5\pmod{p}$

であるから56が5の平方根である。

 

同じく$p=101$として$6$の平方根を求める。

$6^{(101+3)/8}=14\pmod{p}$
である。よって14が平方根の可能性がある。実際計算をしてみると

$14^2=95=-6\pmod{p}$

である。そこで二乗して-1になる数を探す。2からチェックをしていくと

$2^{25}=10\pmod{p}$

である。実際

$10^2=-1\pmod{p}$

だから$10$は-1の平方根。これより

$14\times 10=39\pmod{p}$

を得、39が6の平方根であることがわかる。

最後に残ったケース、$p$が$8N+1$型の素数についてはちょっとややこしいので次のエントリーに書きます。