原始根探し
１．原始根は粘り強い
このワークシートはMath by Codeの一部です。
＜原始根ってなんだっけ？＞
７で割った余りで数を同一視する整数の世界、
つまり、mod７でのべき乗計算をしてみる。
aのべき乗を順次計算してみよう。
たとえば、
a=2 (mod 7)なら,
21≡2 (mod 7),
22≡4 (mod 7),
23≡1 (mod 7),
24≡2 (mod 7),
25≡4 (mod 7),
26≡1 (mod 7)
と、２，４，１を２回繰り返す。
powermod(2,k,7)のkを動かしても1,2,4しか結果がでない。
初めて１と合同になるのは６乗ではなく、3乗だ。だから周期３乗で繰り返す。
a=3 (mod 7)なら、
31≡3 (mod 7),
32≡2 (mod 7),
33≡6 (mod 7),
34≡4 (mod 7),
35≡5 (mod 7),
36≡１と、繰り返すことなく６乗まで粘って１になる。
この最後までねばるヤツが原始根だ。
３を使うと、そのべき乗でmod7の0以外の要素7-1=６個が全部出そろう。
powermod(3,k,7)のkを1から6までまわすと、1から6の剰余がすべて出そろう。
３はすべての元の生成者になれるという意味で生成元、原始根だ。
aが原始根なら、p-1乗で初めてap-1≡1(mod p)となる。
順番はともかく、かぶりがない、１対１対応だ。
だから、逆算にも役立つ。そういう、ありがたい要素が原始根だ。
＜原始根はレアなの？＞
そんなありがたい原始根だけど、有り、難い、つまりレアな存在というものではない。
mod7でみてみよう。
11≡1 (mod 7),
23≡1 (mod 7),
36≡1 (mod 7),
43≡1 (mod 7),
56≡1 (mod 7),
62≡1 (mod 7)
原始根は3だけではない、５もそうだ。
原始根を3,5をｒとすると、
L=[1,2,3,4,5,6]の要素ｘを順にpowermod(r,x,7)=Lになる。
mod 7の原始根は３と５の2個があることがわかった。
＜指数の約数＞
こんどは原始根以外にスポットライトをあてよう。
たとえば、２は３乗で１になり、振り出しに戻る。
原始根と同じ６乗で１になる必要があるから、３乗を２回くりかえして６乗になる。
たとえば、６は２乗で１になり、振り出しに戻る。
原始根と同じ６乗で１になる必要があるから、２乗を３回くりかえした６乗になる。
つまり、原始根は最大周期６乗で１になったけど、原始根以外でも６乗すれば必ず１になる。
これはオイラーの小定理からそうなる。
だから、その手前の周期のｘ乗で１になるとしたら、ｘ乗をｙ回くりかえして６乗になる。
つまり、ｘは６の約数になるということだ。
aが原始根でないときは、am≡1(mod p)なら、mはp-1のp-1より小さい約数だ。
２．全体をみると部分がわかる
原始根だけ特別扱いしないで、平等に調べて全体をみよう。
11≡1 (mod 7),
23≡1 (mod 7),
36≡1 (mod 7),
43≡1 (mod 7),
56≡1 (mod 7),
62≡1 (mod 7)
周期が６の要素は3,6の２個。
周期が３の要素は2,4の２個。
周期が２の要素は6の1個。
周期が1の要素は1の1個。
2+2+1+1=6（個）
x=[6,3,2,1]に対してy=[2,2,1,1]となる関数はないかな？
mod11ならどうだろうか？
11 ≡1 (mod 11),
210≡1 (mod 11),
35 ≡1 (mod 11),
45 ≡1 (mod 11),
55 ≡1 (mod 11),
610≡1 (mod 11)
710≡1 (mod 11),
810≡1 (mod 11),
95 ≡1 (mod 11),
102 ≡1 (mod 11),
周期が10の要素は4個。
周期が5 の要素は4個。
周期が2 の要素は1個。
周期が1 の要素は1個。
4+4+1+1=10
x=[10,5,2,1]に対してy=[4,4,1,1]となる関数はないかな？
この２つの事例から
x=1ならy=1,
素数x=p（2,3,5）ならy=p-1。
合成数x=pq(6,10)ならy=(p-1)(q-1)となっている。
もう見当がつきましたか？
これは、オイラー関数φそのものだね！
要素そのものではなく約数と個数と互いに素に着目することで、全体像が見えてきたね。
つまり、
mod pの剰余x(１からp-1個)に対して、powermod(x,k,p)の値の周期はp-1の約数になる。
周期1は1個(ｘ＝１)。
周期n(素数)はn-1個。
周期d(合成数)になる要素はφ(d)個。
1+n-1+....φ(d)=ｐ−１（個）になる。
p-1の約数すべてにわたって周期ごとの要素数を合計するとp-1になる。
つまり、
∑φ(d)=p-1
周期が最大のp-1になる要素が原始根だったから、
どんな素数ｐでも
原始根はφ(p−1)個あるということだ。
３．原始根を探そう
素数pには原始根が必ずあり、その個数はφ(p-1)だとわかった。
では、１からp-1のうち、どれが原始根になるのか？
それは、p-1個の要素を順にp-1乗まで調べないとみつからないのか？
たとえば、p=7のとき
11≡1 (mod 7),
23≡1 (mod 7),
36≡1 (mod 7),
43≡1 (mod 7),
56≡1 (mod 7),
62≡1 (mod 7)
で、3,5が原始根だった。
31≡3 (mod 7),
32≡2 (mod 7),
33≡6 (mod 7),
34≡4 (mod 7),
35≡5 (mod 7),
36≡1 (mod 7)
51≡5 (mod 7),
52≡4 (mod 7),
53≡6 (mod 7),
54≡2 (mod 7),
55≡3 (mod 7),
56≡1 (mod 7)
と順に計算すれば、aをp-2回aにかけてそのつど剰余を書き出してみつかった。
＜p-1の素因数分解＞
p-1=6=2・3と素因数分解される。
p1e1p2e2....となったとき、
要素aについて、
どの素数piについても a(p-1)/pi≡1(mod p)でないなら、aは原始根となる。
６の周期乗はどれも１(mod p)になるので、一番あやしいのは6の自明でない約数乗、２乗、３乗で１(mod p)になることだ。だから、２乗、３乗だけを調べれば良い。
a=1は論外。
a=2から６までで、２乗と３乗だけ剰余をしらべよう。φ(6)=(2-1)(3-1)=2個原始根があるはず。
22≡4 、23≡8≡1 (mod 7) ３乗で１になるから２はアウト。
32≡9=2 33≡6 (mod 7) ２乗も３乗も1にならないからOK。
42≡16=2 , 43≡8=1(mod 7) ３乗で１になるからアウト。
52≡25=4 , 53≡12=5(mod 7) ２乗も３乗も1にならないからOK。
２個見つかったから終了。
面白いのは、p=5やp=17のとき。
p-1=4,16のように素因数は2しかない。
だから、
p=5のときは4/2=2乗が１にならないとすぐ原始根とわかる。
p=17のときは16/2=8乗が１にならないとすぐ原始根とわかる。
（理由）
p-1＝p1e1p2e2... (素因数分解１）とする。
aが原始根でなければ、
p-1より小さいp-1の約数ｍでam≡1(mod p)となる。
だから、m=p1f1p2f2... （素因数分解２）とする。
２つの素因数分解１，２を比較したときに、p-1とｍの大小関係から
指数eのリストと指数ｆのリストで必ずｆにeより小さいものがある。
それが１番目なら、(p-1)/p1でもmのｋ倍(kは１以上）になる。
だから、a(p-1)/p1≡(am)k≡1k≡1(mod p)となる。
これが１回もおきないなら、m=p-1となり、aが原始根ということになるね。
質問：原始根を求める関数はどうやって作りますか？juliaやpythonで
（剰余n、原始根の個数、原始根のリスト）を返す、関数primitiveRoot(n)を作ることができる。
100以下の素数に対して、原始根のリストを表示してみよう。
#[IN]julia
#=====================================================================
#素数判定関数
function isPrime(n)
lim = Int(round(n^0.5))
if n<2
return false
end
for num in 2:lim
if n % num ==0
return false
end
end
return true
end
#オイラー関数
function eu(n)
divs=filter( m -> n % m==0,1:n) #nの約数リスト
ps= filter(p -> isPrime(p),divs) #nの素因数リスト
zs= [1-1/x for x in ps] #素数の倍数を除く割合リスト
return Int(n *prod(zs))
end
#素数ｎの原始根を求める関数
function primitiveRoot(n)
q=n-1
divs=filter( m -> q % m==0,1:q) #qの約数リスト
ps= filter(p -> isPrime(p),divs) #qの素因数リスト
ids = [q÷x for x in ps] #テスト用の指数リスト
rems = [ x for x in 1:q] #テスト対象の剰余リスト
#powermodが1になるものを抜き出すために−１して積が０になると除外する。
tested=[prod([powermod(x,id,n)-1 for id in ids]) for x in rems]
#非ゼロになるインデックスが原始根となる。
return findall(!iszero,tested)
end
P =filter(n->length(filter( m -> n % m==0,1:n))==2, 5:100)
pp=[(x,eu(x),primitiveRoot(x)) for x in P]
#=====================================================================
[OUT]
23-element Vector{Tuple{Int64, Int64, Vector{Int64}}}:
(5, 4, [2, 3])
(7, 6, [3, 5])
(11, 10, [2, 6, 7, 8])
(13, 12, [2, 6, 7, 11])
(17, 16, [3, 5, 6, 7, 10, 11, 12, 14])
(19, 18, [2, 3, 10, 13, 14, 15])
(23, 22, [5, 7, 10, 11, 14, 15, 17, 19, 20, 21])
(29, 28, [2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27])
(31, 30, [3, 11, 12, 13, 17, 21, 22, 24])
(37, 36, [2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35])
(41, 40, [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35])
(43, 42, [3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34])
(47, 46, [5, 10, 11, 13, 15, 19, 20, 22, 23, 26 … 31, 33, 35, 38, 39, 40, 41, 43, 44, 45])
(53, 52, [2, 3, 5, 8, 12, 14, 18, 19, 20, 21 … 32, 33, 34, 35, 39, 41, 45, 48, 50, 51])
(59, 58, [2, 6, 8, 10, 11, 13, 14, 18, 23, 24 … 40, 42, 43, 44, 47, 50, 52, 54, 55, 56])
(61, 60, [2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59])
(67, 66, [2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63])
(71, 70, [7, 11, 13, 21, 22, 28, 31, 33, 35, 42 … 55, 56, 59, 61, 62, 63, 65, 67, 68, 69])
(73, 72, [5, 11, 13, 14, 15, 20, 26, 28, 29, 31 … 42, 44, 45, 47, 53, 58, 59, 60, 62, 68])
(79, 78, [3, 6, 7, 28, 29, 30, 34, 35, 37, 39 … 54, 59, 60, 63, 66, 68, 70, 74, 75, 77])
(83, 82, [2, 5, 6, 8, 13, 14, 15, 18, 19, 20 … 62, 66, 67, 71, 72, 73, 74, 76, 79, 80])
(89, 88, [3, 6, 7, 13, 14, 15, 19, 23, 24, 26 … 63, 65, 66, 70, 74, 75, 76, 82, 83, 86])
(97, 96, [5, 7, 10, 13, 14, 15, 17, 21, 23, 26 … 71, 74, 76, 80, 82, 83, 84, 87, 90, 92])