原始根で指数・対数
ax≡b(mod37）を解く
１．小さい原始根
このワークシートはMath by Codeの一部です。
原始根はべき計算の生成元でした。
だから、法ｐの剰余計算が、原始根を使えばべき乗によって、
すべての剰余を表現できるので、べき乗の合同方程式を解きたいときにとても役に立つ。
そうはいっても、べき乗の底は小さい方がいいね。
だから、複数ある原始根のうち、できるだけ小さい数を選ぼう。
＜原始根は小さくしよう＞
指数計算の桁爆発を避けたいので、できるだけ小さな原始根を選ぼう。
原始根、つまり、底
法、底
3、２
5、２
7、３
11、２
13、２
17、３
19、２
23、５
29、２
31、３
37、２
41、６
43、３
47、５
53、２
59、２
61、２
67、２
71、７
73、５
79、３
83、２
89、３
91、５
97、２
２．原始根で指数と対数
原始根aの意味は、powermod(a,x,p)の値が、xをすべての剰余を入れると、それがバラバラにかぶりなく
返ってくる、つまり、全単射（1対1）の写像を作ってくれるということだった。
だから、逆関数も全単射できれいに返ってくる。
たとえば、底を２、法を13として指数計算してみよう。
ベキ表
21≡2(mod 13),
22≡4(mod 13),
23≡8(mod 13),
24≡3(mod 13),
25≡6(mod 13),
26≡12(mod 13)
27≡11(mod 13),
28≡9(mod 13),
29≡5(mod 13),
210≡10(mod 13),
211≡7(mod 13),
212≡1(mod 13)
213≡2(mod 13),
・これを指数関数として表示することができる。y≡2x(mod13)
つまり、
x={1,2,3,4,5,6,7,8,9,10,11,12}に対して
y={2,4,8,3,6,12,11,9,5,10,7,1,2}
これがベキ表だ。(mod13)
もちろん、単調増加関数ではないが、全単射の写像になってはいる。
geogebraでは、p=13
x=sequence(p-1)
原始根をa=2 , 初期値をb=aとして、a b (mod p)を次のbとする。
つまり、
yn=a yn-1(mod p) , y1=a という漸化式を関数化することでベキ表が作れるはずだね。
y=IterationList( Mod(a b,p),b,{a},b)
これがベキ表
この逆関数である対数関数をｘ≡I(y)とかくことにしよう。
y={2,4,8,3,6,12,11,9,5,10,7,1,2}に対して
x={1,2,3,4,5,6,7,8,9,10,11,12}となる。
これが指数取り出し表だ。
2a≡A(mod 13) ならa=I(A)
2b≡B(mod 13) ならb=I(B)
・2I(AB)≡AB≡2a2b≡2 a+b≡2 I(A)+I(B)(mod 13)
2I(AB)-I(A)-I(B)≡1(mod13)
フェルマーの小定理から212≡1(mod13)
この２式の指数を比較して、I(AB)-I(A)-I(B)は12の倍数。
つまり、I(AB)≡I(A)+I(B)(mod12)
・また、B=Aにして、複数かけ算すると、
l(AA)≡l(A)+l(A)=2l(A)(mod12)
l(AAA)≡3l(A)(mod12)
つまり、I(Ak)≡k I(A)(mod12)
(対数法則の一般化）
mod pの原始根をｇとするとき
ga≡A(mod p) ならa=I(A)で指数を取り出す対数関数
gb≡B(mod p) ならb=I(B)で指数を取り出す対数関数
I(AB)≡I(A)+I(B) (mod p-1)
I(Ak)≡k I(A) (mod p-1)
法も変えて合同方程式を解こう。
３．対数で指数を取り出す
＜対数関数の使い方＞
原始根を2とし、mod13とする。
指数取り出し表はmod13ではなく（mod 12)になる。
y={2,4,8,3,6,12,11,9,5,10,7,1,2}に対して
x={1,2,3,4,5,6,7,8,9,10,11,12}
これを意味が伝わりやすくなるｙ＝a, x=I(a)とかき、aの降順に並べかえ、I(a)も対応させよう。
a= { 1, 2, 3, 4, 5, 6, 7, 8, 9 ,10,11,12}に対して
I(a)={12,1, 4, 2, 9, 5,11, 3, 8, 10, 7, 6}
geogebraでは、原始根a=2, p=13とするとき
x=sequence(p-1)
y=IterationList(Mod(a b,p),b,{a},b)
これがベキ表だから。
id=zip((yy,aa), yy ,y ,aa, x) と(y,x)の順のタプルのリストを作ることで逆関数にする。
idT=sort(id)でyの昇順にすると、yを１からp-1まで並べたときのｘを取り出す
指数取り出し表になる。
a=10=2×5に対して、I(10)はI(2)+I(5)=1+9=10と計算できる。
a=8=23に対して、I(8)はI(2)×3=1×3＝３と計算できる。
通常の指数・対数関数のように単調増加ではないにしても、
１対１対応だから、A≡B(mod p)からI(A)≡I(B)(mod p-1)という指数の関係に置き換えることができる。
指数にしてしまうことで、A,Bを素因数分解して,
(mod p)の積とベキの計算を(mod p-1)の和と積に還元できる。
もちろん、最終的には指数ではなく、(mod p)のべき表を使った計算に戻そう。
（例）「ｘ≡1156(mod 13)の解」は？
両辺の対数をとり、指数を取り出そう。
I(x)≡I(1156)(mod12)
I(x)≡56I(11)＝(12×4+8) I(11)≡8 I(11)(mod12)
指数取り出し表で指数にする。aからI(a)を読む。l(11)=7.
I(x)≡8 ･7=56≡8(mod 12)
べき表でI(a)からaを読む。l(a)=8となるa=9だから、x≡9(mod 13)。
つまり、powermod(11,56,13)=9が表の読み取りで求められた。
（例）「ｘ≡81233(mod 13)の解」は？
原始根が2で、8=23
両辺の対数をとり、指数を取り出そう。
I(x)≡I(23・1233)(mod12)
I(x)≡3699 I(2)＝(12×308+3) I(2)≡3 I(2)(mod12)
指数取り出し表で指数にする。aからI(a)を読む。I（２）＝1.
I(x)≡3･1≡3(mod 12)
べき表でI(a)からaを読む。l(a)=3となるa=8.
x≡8(mod 13)。
つまりpowermod(8, 1233,13)=8が表の読み取りで求められた。
（例）「1次合同式11x≡9(mod 13)の解」は？
原始根が2
両辺の対数をとり、指数を取り出そう。
I(11x)≡I(9)(mod12)
I(11)+l(x)≡I(9)(mod12)
指数取り出し表で指数にする。aからI(a)を読む。I（9)=8
7+l(x)≡8(mod 12)
l(x)≡8-7=1(mod 12)
べき表でI(a)からaを読む。l(a)=1 となるa=2. x≡2(mod 13)。
（例）「1次合同式 19x≡23(mod 37）の解」は？
mod37のべき表から
mod36の指数取り出し表を作ることから始めよう。
a =
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36}
I(a)=
{36,1,26,2,23,27,32,3,16,24,30,28,11,33,13, 4, 7,17, 35,25,22,31,15,29,10,12, 6,34,21,14, 9, 5,20, 8,19,18}
両辺の対数をとり、指数を取り出そう。
I(19x)≡I(23)(mod 36)
対数法則
I(19)+I(x)≡I(23)(mod36)
指数取り出し表で指数にする。aからI(a)を読む。l(23)=15.
35+I(x)≡15(mod36)
移項する
I(x)≡15-35≡-20+36≡16(mod36)。
べき表として使う。I(a)からaを読む。I(a)=16から逆にたどると、a=9。
x≡9(mod 37)。
（例）「合同式 7x20≡34(mod 37）の解」は？
両辺の対数をとり、指数を取り出そう。
I(7)+20 l(x)≡I(34)(mod 36)
指数取り出し表で指数にする。aからI(a)を読む。l(34)=8
32+20 I(x)≡8(mod36)
移項する
20 I(x)≡8-32≡-24+36≡12(mod36)。
係数と法がすべて4の倍数なので、4で合同式を簡約する。
5 I(x)≡3(mod 9)
(1+9)/5=2から、5×2≡10≡1(mod 9)となり、 5の逆元は2。
I(x)≡5-13≡2・3≡6(mod 9)⇒6, 15, 24, 33(mod 36)。
I(x)≡6, 15, 24, 33(mod 36)。
べき表として使う。I(a)からaを読む。
x≡27,23,10,14(mod 37)。