mod pでの平方剰余を計算する(p mod 8 = 5の場合)

pをある程度限定した素数とした時の平方剰余を計算してみます。
整数論の世界では実数の世界でのルートという言葉は使わないようです。

いくつかの整数論の定理を利用しますので、事前に明示しておきます。
これらの定理は超有名なので、整数論の本に必ず載っています。

オイラーの基準(Euler’s Criterion)
pを奇素数, aを整数とする.この時,
$( \frac {a} {p} ) = {a}^{ \frac {p-1} {2} } \begin{eqnarray} \bmod p \end{eqnarray}$

平方剰余の第２補充法則
pを奇素数とすると,
$p = 1,7 \begin{eqnarray} \bmod 8 \end{eqnarray}の場合$
$( \frac {2} {p} ) = 1$
$p = 3,5 \begin{eqnarray} \bmod 8 \end{eqnarray}の場合$
$( \frac {2} {p} ) = -1$
ここでカッコはルジャンドル記号と言います.

本題
素数pとしてp mod 8 = 5の場合だけを考えます。
この時, p mod 4 = 1でもあります。
この素数の例としては ${2} ^ {255} - 19$ があります。

p = 8k + 5と書けます。また $\frac {p-1} {4}$ は整数です。

${x} ^ {2} = a\mod p$ の解は存在すると仮定して、解xを求めたいです。
解が存在するということは、
$( \frac {a} {p} ) = 1$ です。オイラーの基準を使うと、
${a} ^ { \frac {p-1} {2} } = ( \frac {a} {p} ) = 1\mod p$

$\frac {p-1} {4}$ は整数なので、左辺は ${a} ^ { \frac {p-1} {4} 2}$ となり、
ケースa) ${a} ^ { \frac {p-1} {4} } = 1 \mod p$
ケースb) ${a} ^ { \frac {p-1} {4} } = -1 \mod p$
のどちらと言えます。

a)の場合は、 $x = {a} ^ {k+1}$ が解となります。
なぜなら、
${x} ^ {2} = {a} ^ {2k+2} = {a} ^ { \frac {p-5} {4} + 2} = {a} ^ { \frac {p-1} {4}} a = a\mod p$
となるからです。
b)の場合は、
$x = {2} ^ {2k+1} {a} ^ {k+1}$ が解となります。
なぜなら、
${x} ^ {2} = {2} ^ {4k+2} {a} ^ {2k+2} = {2} ^ { \frac {p-1} {2} } {a} ^{ \frac {p-1} {4}} a = {2} ^ { \frac {p-1} {2} } (-1) a\mod p$
ここでオイラーの基準でa=2と置いた式を使うと
$( \frac {2} {p} ) = {2}^{ \frac {p-1} {2} } \begin{eqnarray} \bmod p \end{eqnarray}$
平方剰余の第２補充法則を使うと、
この左辺は-1なので結局、最後の式は $(-1) (-1) a = a\mod p$ となり、解となっていることが分かりました。
まとめると、解は、
a)の場合
$x1= {2} ^ { \frac {p-1} {4}} {a} ^ {\frac {p+3} {8} }$
であり、
b)の場合
$x2= {a} ^ { \frac {p+3} {8} }$
となることが分かりました。
どちらも同じ因子が現れていますね。
コンピュータで計算する場合は、場合分けの計算を省くために、
この因子 ${a} ^ { \frac {p+3} {8} }$ を先に計算し、その二乗を計算して、aに一致するか確かめます。
一致すればb)の場合なので、そこで終了です。
一致しない場合はa)の場合なので、さらに2のベキ乗因子を計算して掛ければ解が得られます。