Pebble Coding

プログラマーの作業メモ

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}

平方剰余の第2補充法則
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}
平方剰余の第2補充法則を使うと、
この左辺は-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のベキ乗因子を計算して掛ければ解が得られます。

参考: http://course1.winona.edu/eerrthum/13Spring/SquareRoots.pdf