Pebble Coding

プログラマーの作業メモ

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

前回 mod pでの平方剰余を計算する(p mod 8 = 5の場合) - Pebble Coding
p mod 8 = 5の時の平方剰余を計算しましたが、今回は、
p mod 4 = 3の時の平方剰余を計算してみましょう。
この場合も簡単に計算が可能です。 前回と同じように
 {x} ^ {2} = a
の解は存在することを仮定します。つまり、
 ( \frac {a} {p}) = 1
です。
 p = 4k + 3と書けます。
解は、
 x = {a} ^ {k + 1}
となります。なぜなら、
 {x} ^ {2} = {a} ^ {2k +2} = {a} ^ {2k+1} a = {a} ^ { \frac {p-1} {2} } a
オイラーの基準を使い、右辺は、
 = ( \frac {a} {p} ) a = a
となり、式を満たします。 解をpで書くと
 x = {a} ^ { \frac {p+1} {4} }
となります。