元祖ワシ的日記

\[
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$が$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$が$8N+1$型の素数についてはちょっとややこしいので次のエントリーに書きます。