10章　原始根（primitive root）

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

　1　　2　　3　　4　

1 p 7 　　

2 a , n 1 2 3

3 1 =MOD(RC1^R2C,R1C2) =MOD(RC1^R2C,R1C2) 　

4 2 　　　

	1	2	3	4
1	p	7
2	a , n	1	2	3
3	1	=MOD(RC1^R2C,R1C2)	=MOD(RC1^R2C,R1C2)
4	2

R3C2 に計算式、=MOD(RC1^R2C,R1C2) を入力し、R3C2 から R8C7 までコピーする。
R1C2 にはｐの値を代入する。
結果は以下のとおり。

　1　　2　　3　　4　　5　　6　　7　

1 p 7 　　　　　

2 a , n 1 2 3 4 5 6

3 1 1 1 1 1 1 1

4 2 2 4 1 2 4 1

5 3 3 2 6 4 5 1

6 4 4 2 1 4 2 1

7 5 5 4 6 2 3 1

8 6 6 1 6 1 6 1

	1	2	3	4	5	6	7
1	p	7
2	a , n	1	2	3	4	5	6
3	1	1	1	1	1	1	1
4	2	2	4	1	2	4	1
5	3	3	2	6	4	5	1
6	4	4	2	1	4	2	1
7	5	5	4	6	2	3	1
8	6	6	1	6	1	6	1

ｐ＝７に対してａ＝３の時は、６乗（＝ｐ－１）の時はじめて１となり、
かつ１からｐ－１までの数が全て現れる。
このような性質を持つ数を、素数ｐの原始根（primitive root）と呼ぶ。

上の表を眺めていると、いくつかの点に気付く。

ｐ＞３について、１、ｐ－１は原始根とならない。
（ｐ＝２のときは、１が原始根。
ｐ＝３のときは、２が原始根。）
ａが原始根のとき、a^(p-1)/2＝(p-1) （mod p）
（これは必要十分条件ではないので、ａが原始根でなくでも、
a^(p-1)/2＝(p-1) （mod p）となる場合がある）

等。

100以下の素数（２、３を除く）について、原始根を求めてみよう。
素数ｐに対して、2 <= a <= p-1 の範囲で、ａが原始根か否かを調べて表示する。
原始根か否かの判定は、ワーク領域として (p-1) 個分の配列 t(p-1) を用意して０で初期化、
1 <= i <= (p-1) の範囲で、aⁱ mod p の値を計算、
t(i) が０のときは格納（t(i)=1とする）、
t(i) が１の時は (p-1) 乗する前に同じ余りになってしまったことを意味し、
原始根とはなり得ない。1 <= i <= (p-1) で、t(i) が全て 1 となった場合、ａは原始根となる。
Excel のマクロは以下のようになる。

Sub Record9()
    Worksheets("sheet2").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(1, 1).Value = "a...p"

    For i = 2 To 96: Cells(i, 1) = i: Next i
    For i = 3 To 25: v = prm_root(p(i), i - 1): Next i

End Sub

Function prm_root(p, k)
    Dim t(100)

    r = p - 1: q = r / 2
    Cells(1, k).Value = p

    For a = 2 To r
        For j = 1 To r: t(j) = 0: Next j
        b = a: t(b) = 1
        For j = 2 To r
            b = b * a - p * Int(b * a / p): t(b) = 1
        Next j
        f = 0
        For j = 2 To r
          If t(j) = 0 Then f = 1
        Next j
        If f = 0 Then Cells(a, k).Value = "r"
    Next a

    prm_root = a
End Function

先頭の prime table で定数を設定している部分は、他の言語の時にも応用がきく。

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

原始根に関しては、

２を原始根として持つ素数は、無数に存在する

という有名な未解決問題 (Artin 予想) がある。

前頁	目次	次頁

E-mail : kc2h-msm@asahi-net.or.jp

三島　久典

10章 原始根（primitive root）

10章　原始根（primitive root）