ぺんぎんさんのおうち

トリトリトリ

Euler's criterion 平方剰余の判別

整数論において奇素数\(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 を読むと良い.