整数論において奇素数\(p\)をModulusとしたとき, \(a \in GF(p)\)について $$ x^{2} \equiv a \, mod \, p $$
となる \(x\)が存在するとき\(a\)を\(p\)の平方剰余であるという.
\(a\)が平方剰余であるかどうか(上式で解を持つかどうか)を判定するのに使われるのがEuler's criterion（オイラーの基準）である.
式はシンプルで, \(a \in GF(p)\)を入力に取り, 出力は\(\{0,1,-1\}\)のどれかである. (ルジャンドル記号の話は割愛する)
0が出力されるのは\(a\)が\(p\)で割り切れる場合であり, この記事内では扱わない.
$$
a^{\frac{p-1}{2}} \, mod \, p =
\begin{cases}
0 \newline
1 \newline
-1
\end{cases}
$$
上式で1が出力されれば\(a\)は平方剰余である(\(x^{2} \equiv a \, mod \, p\)の解が存在する).
なぜ1を得たときに\(a\)が平方剰余となるのかを解説していこう.
まずフェルマーの小定理より, modulusは素数なので任意の \(a \in GF(p)\)について
$$ a^{p-1} \equiv 1 \, mod \, p $$
これを変形していく.
\begin{eqnarray} a^{p-1} & \equiv & 1 \, mod \, p \newline a^{p-1} - 1 & \equiv & 0 \newline (a^{\frac{p-1}{2}} - 1)(a^{\frac{p-1}{2}} + 1) & \equiv & 0 \newline \end{eqnarray}
2つの因数が得られ, これらを別々に考える.
・ \((a^{\frac{p-1}{2}} - 1) \equiv 0\)
\begin{eqnarray} a^{\frac{p-1}{2}} - 1 & \equiv & 0 \, mod \, p \newline a^{\frac{p-1}{2}} & \equiv & 1 \, mod \, p \newline \end{eqnarray}
ここで, \(x^{2} \equiv a \)とすると
\begin{eqnarray} {x^{2}}^{\frac{p-1}{2}} & \equiv & 1 \, mod \, p \newline x^{p-1} & \equiv & 1 \, mod \, p \newline \end{eqnarray}
\(a\) と \(p\) は互いに素であり \(x\) と \(p\) も同様に互いに素であるためフェルマーの小定理に従う.
したがって, \(x^{2} \equiv a \, mod \, p\)を満たす\(x\)は存在し, \(a\)は平方剰余であることがいえる.
言い換えると, \(a^{\frac{p-1}{2}} \, mod \, p = 1\) であれば \(x^{2} \equiv a \, mod \, p\)を満たす\(x\)が必ず存在する.
・ \((a^{\frac{p-1}{2}} +1) \equiv 0\)
\begin{eqnarray} a^{\frac{p-1}{2}} + 1 & \equiv & 0 \, mod \, p \newline a^{\frac{p-1}{2}} & \equiv & -1 \, mod \, p \newline (& \equiv & p-1 \, mod \, p) \end{eqnarray}
先ほどと同様に, \(x^{2} \equiv a \)とすると
\begin{eqnarray} {x^{2}}^{\frac{p-1}{2}} & \equiv & -1 \, mod \, p \newline x^{p-1} & \equiv & -1 \, mod \, p \newline \end{eqnarray}
\(x\) と \(p\) は互いに素であるため, フェルマーの小定理に従うはずである. このような\(x \in GF(p)\)は存在しない.
これは \(x^{2} \equiv a \, mod \, p\)を満たす\(x\)が存在せず, \(a\)は平方剰余でないことを意味している.
楕円曲線の整数点
Euler's criterionを利用すると, \((x, y) \in GF(p)\)で総当たりをしなくても, \(x \in GF(p)\)で右辺を計算した結果が平方剰余かどうか判定すれば, ある\(x\)について曲線の式を満たす\(y\)が存在するか判別できる.
Euler's criteriionはあくまで平方剰余かどうかを判別するだけで, 実際の解を得るわけではない点に注意. 解を得るには Tonelli–Shanks algorithm を読むと良い.
