pを素数とする。
i(1≦i≦p−1)の2乗の mod p の時の値を調べてみる。
例えば、p=7の時の値を調べて見よう。
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 にはpの値を代入する。
結果は以下のとおり。
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
1、2、4は、何かの2乗となっている。
3、5、6は、何かの2乗とはなっていない。
このように、
i2=a(mod p)
となるようなiが存在する場合、aをpの平方剰余(quadratic residue)と呼び、
(a/p)=1
と表す(Legendre の記号)。
平方剰余でない場合を、非平方剰余と呼ぶ。このときの Legendre 記号の表記は、
(a/p)=−1
と表す。
100以下の素数p(2を除く)について、a(1≦p≦p−1)が平方剰余かどうかを調べてみよう。
アルゴリズムは以下のようになる。
for i=1 to p-1
j=modpow(i^2, p) : ' j is quadratic residue of p.
next i
配列a( )をとっておいて、初期値として−1をセットしておき、上のようなjに対して、
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 = pEnd Function
先頭の prime table で定数を設定している部分は、原始根の時と同じ要領である。
実行結果は次のとおり(表のサイズが大きいので注意のこと)。
平方剰余は以下の公式の組み合わせにより計算できる。
(q/p)(p/q)=(-1)(p-1)/2・(q-1)/2
(平方剰余の相互律)
(-1/p)=(-1)(p-1)/2
(2/p)=(-1)(p2-1)/8
前頁 | 目次 | 次頁 |
---|