11章　平方剰余（quadratic residue）

ｐを素数とする。
ｉ（１≦ｉ≦ｐ−１）の２乗の mod　p の時の値を調べてみる。
例えば、ｐ＝７の時の値を調べて見よう。

	1	2
1	p	7
2	i	i^2 mod p
3	1	=MOD(RC[-1]^2,R1C2)

R3C2 に計算式、=MOD(RC[-1]^2,R1C2) を入力し、R3C2 から R8C2 までコピーする。
R1C2 にはｐの値を代入する。
結果は以下のとおり。

	1	2
1	p	7
2	i	i^2 mod p
3	1	1
4	2	4
5	3	2
6	4	2
7	5	4
8	6	1

１、２、４は、何かの２乗となっている。
３、５、６は、何かの２乗とはなっていない。

このように、

i²＝ａ（mod p）

となるようなｉが存在する場合、ａをｐの平方剰余（quadratic residue）と呼び、

(a/p)＝１

と表す（Legendre の記号）。
平方剰余でない場合を、非平方剰余と呼ぶ。このときの Legendre 記号の表記は、

(a/p)＝−１

と表す。

100以下の素数ｐ（２を除く）について、ａ（１≦ｐ≦ｐ−１）が平方剰余かどうかを調べてみよう。
アルゴリズムは以下のようになる。

for  i=1  to  p-1
    j=modpow(i^2, p) : ' j is quadratic residue of p.
next  i

配列ａ( )をとっておいて、初期値として−１をセットしておき、上のようなｊに対して、

a(j)=1

とする。

Excel のマクロは以下のようになる。

Sub Record8() Worksheets("Sheet5").Activate ' prime table Dim p(25) p(1) = 2: p(2) = 3: p(3) = 5: p(4) = 7: p(5) = 11 p(6) = 13: p(7) = 17: p(8) = 19: p(9) = 23: p(10) = 29 p(11) = 31: p(12) = 37: p(13) = 41: p(14) = 43: p(15) = 47 p(16) = 53: p(17) = 59: p(18) = 61: p(19) = 67: p(20) = 71 p(21) = 73: p(22) = 79: p(23) = 83: p(24) = 89: p(25) = 97 ' Cells(2, 1).Value = "n" Cells(2, 2).Value = "p" For i = 1 To 96: Cells(i + 2, 1) = i: Next i For n = 2 To 25: Cells(1, n) = p(n): v = qua_res(p(n), n): Next n End Sub Function qua_res(p, k) Dim a(97) For i = 1 To p - 1: a(i) = -1: Next i For i = 1 To p - 1: j = i ^ 2 - p * Int(i ^ 2 / p): a(j) = 1: Next i For i = 1 To p - 1: Cells(i + 2, k).Value = a(i): Next i qua_res = p End Function

先頭の prime table で定数を設定している部分は、原始根の時と同じ要領である。

実行結果は次のとおり（表のサイズが大きいので注意のこと）。

平方剰余は以下の公式の組み合わせにより計算できる。

• (ab/p)＝(a/p)(b/p)
• ｐ、ｑを奇素数とするとき、

  (q/p)(p/q)＝(-1)^{(p-1)/2・(q-1)/2}
  （平方剰余の相互律）

• ｐを奇素数とするとき、

  (-1/p)＝(-1)^(p-1)/2
  (2/p)＝(-1)^(p2-1)/8