[size=150][b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][/b][size=100]原始根はべき計算の生成元でした。[br]だから、法ｐの剰余計算が、原始根を使えばべき乗によって、[br]すべての剰余を表現できるので、べき乗の合同方程式を解きたいときにとても役に立つ。[br][br]そうはいっても、べき乗の底は小さい方がいいね。[br]だから、複数ある原始根のうち、できるだけ小さい数を選ぼう。[br][/size][b][br]＜原始根は小さくしよう＞[/b][/size][br]指数計算の桁爆発を避けたいので、できるだけ小さな原始根を選ぼう。[br]原始根、つまり、底[br]法、底[br]3、２[br]5、２[br]7、３[br]11、２[br]13、２[br]17、３[br]19、２[br]23、５[br]29、２[br]31、３[br]37、２[br]41、６[br]43、３[br]47、５[br]53、２[br]59、２[br]61、２[br]67、２[br]71、７[br]73、５[br]79、３[br]83、２[br]89、３[br]91、５[br]97、２

原始根aの意味は、powermod(a,x,p)の値が、xをすべての剰余を入れると、それがバラバラにかぶりなく[br]返ってくる、つまり、全単射（1対1）の写像を作ってくれるということだった。[br]だから、逆関数も全単射できれいに返ってくる。[br][br]たとえば、底を２、法を13として指数計算してみよう。[br]ベキ表[br]2[sup]1[/sup]≡2(mod 13), [br]2[sup]2[/sup]≡4(mod 13), [br]2[sup]3[/sup]≡8(mod 13), [br]2[sup]4[/sup]≡3(mod 13), [br]2[sup]5[/sup]≡6(mod 13), [br]2[sup]6[/sup]≡12(mod 13)[br]2[sup]7[/sup]≡11(mod 13), [br]2[sup]8[/sup]≡9(mod 13), [br]2[sup]9[/sup]≡5(mod 13), [br]2[sup]10[/sup]≡10(mod 13), [br]2[sup]11[/sup]≡7(mod 13), [br]2[sup]12[/sup]≡1(mod 13)[br]2[sup]13[/sup]≡2(mod 13), [br]・これを指数関数として表示することができる。y≡2[sup]x[/sup](mod13)[br]つまり、[br]x={1,2,3,4,5,6,7,8,9,10,11,12}に対して[br]y={2,4,8,3,6,12,11,9,5,10,7,1,2}[br]これが[b]ベキ表[/b]だ。(mod13)[br]もちろん、単調増加関数ではないが、全単射の写像になってはいる。[br][br][color=#0000ff]geogebraでは、p=13[br]x=sequence(p-1)[br]原始根をa=2 , 初期値をb=aとして、a b (mod p)を次のbとする。[br]つまり、[br]y[sub]n[/sub]=a y[sub]n-1[/sub](mod p) , y[sub]1[/sub]=a という漸化式を関数化することでベキ表が作れるはずだね。[br][br][/color][color=#0000ff][b]y=IterationList( Mod(a b,p),b,{a},b)[br][/b]これが[b]ベキ表[/b][br][/color][br]この[color=#0000ff][b]逆関数である対数関数[/b][/color]をｘ≡I(y)とかくことにしよう。 [br]y={2,4,8,3,6,12,11,9,5,10,7,1,2}に対して[br]x={1,2,3,4,5,6,7,8,9,10,11,12}となる。[br]これが[b]指数取り出し表[/b]だ。[br][br][br]2[sup]a[/sup]≡A(mod 13) ならa=I(A)[br]2[sup]b[/sup]≡B(mod 13) ならb=I(B)[br]・2[sup]I(AB)[/sup]≡AB≡2[sup]a[/sup]2[sup]b[/sup]≡2 [sup]a+b[/sup]≡2 [sup]I(A)+I(B)[/sup](mod 13) [br][b][size=150]　2[sup]I(AB)-[/sup][sup]I(A)-I(B)[/sup]≡1(mod13)[br][/size][/b]　フェルマーの小定理から[size=150][b]2[sup]12[/sup]≡1(mod13)[/b][/size][br]　この２式の指数を比較して、I(AB)-I(A)-I(B)は12の倍数。[br]　つまり、[color=#0000ff][b][size=150]I(AB)≡I(A)+I(B)(mod12)[/size][/b][/color][br]・また、B=Aにして、複数かけ算すると、[br] l(AA)≡l(A)+l(A)=2l(A)(mod12)[br] l(AAA)≡3l(A)(mod12)[br]　つまり、[color=#0000ff][b][size=150]I(A[sup]k[/sup])≡k I(A)(mod12)[br][/size][/b][/color][br] [color=#0000ff] (対数法則の一般化）[br][/color][size=150][color=#0000ff][b]mod pの原始根をｇとするとき[br][/b][/color][color=#0000ff]g[sup]a[/sup]≡A(mod p) ならa=I(A)で指数を取り出す対数関数[br][sup]gb[/sup]≡B(mod p) ならb=I(B)で指数を取り出す対数関数[br]I(AB)≡I(A)+I(B) (mod p-1)[br][/color][size=150][color=#0000ff]I(A[/color][sup]k[/sup][color=#0000ff])≡k I(A) (mod p-1)[/color][/size][/size]

[size=150][b]＜対数関数の使い方＞[/b][size=150][size=100][br][color=#0000ff][b][u]原始根を2とし、mod13とする。[br][/u][/b][/color]指数取り出し表はmod13ではなく（mod 12)になる。[br][/size][/size][/size]y={2,4,8,3,6,12,11,9,5,10,7,1,2}に対して[br]x={1,2,3,4,5,6,7,8,9,10,11,12}[br]これを意味が伝わりやすくなるｙ＝a, x=I(a)とかき、aの降順に並べかえ、I(a)も対応させよう。[br]a= { 1, 2, 3, 4, 5, 6, 7, 8, 9 ,10,11,12}に対して[br]I(a)={12,1, 4, 2, 9, 5,11, 3, 8, 10, 7, 6}[br][br][color=#0000ff]geogebraでは、原始根a=2, [color=#0000ff]p=13とするとき[br]x=sequence(p-1)　 [br][/color][color=#0000ff]y=IterationList(Mod(a b,p),b,{a},b)[br]これが[b]ベキ表[/b]だから。[/color][br]id=zip((yy,aa), yy ,y ,aa, x)　と(y,x)の順のタプルのリストを作ることで逆関数にする。[br]idT=sort(id)でyの昇順にすると、yを１からp-1まで並べたときのｘを取り出す[br][b]指数取り出し表[/b]になる。[br][/color][br]a=10=2×5に対して、I(10)はI(2)+I(5)=1+9=10と計算できる。[br]a=8=2[sup]3[/sup]に対して、I(8)はI(2)×3=1×3＝３と計算できる。[br]通常の指数・対数関数のように単調増加ではないにしても、[br]１対１対応だから、[color=#0000ff][b]A≡B(mod p)からI(A)≡I(B)(mod p-1)という指数の関係[/b][/color]に置き換えることができる。[br][color=#0000ff][b]指数にしてしまうことで、A,Bを素因数分解して,[br](mod p)の積とベキの計算を(mod p-1)の和と積に還元できる。[br][/b][/color]もちろん、最終的には指数ではなく、(mod p)のべき表を使った計算に戻そう。[br][br][color=#0000ff]（例）[/color]「ｘ≡11[sup]56[/sup](mod 13)の解」は？[br]両辺の対数をとり、指数を取り出そう。[br]I(x)≡I(11[sup]56[/sup])(mod12)[br]I(x)≡56I(11)＝(12×4+8) I(11)≡8 I(11)(mod12)[br]指数取り出し表で指数にする。aからI(a)を読む。l(11)=7.[br]I(x)≡8 ･7=56≡8(mod 12)[br]べき表でI(a)からaを読む。l(a)=8となるa=9だから、x≡9(mod 13)。[br]つまり、powermod(11,56,13)=9が表の読み取りで求められた。[br][br][color=#0000ff]（例）[/color]「ｘ≡8[sup]1233[/sup](mod 13)の解」は？[br]原始根が2で、8=2[sup]3[/sup][br]両辺の対数をとり、指数を取り出そう。[br]I(x)≡I(2[sup]3・1233[/sup])(mod12)[br]I(x)≡3699 I(2)＝(12×308+3) I(2)≡3 I(2)(mod12)[br]指数取り出し表で指数にする。aからI(a)を読む。I（２）＝1.[br]I(x)≡3･1≡3(mod 12)[br]べき表でI(a)からaを読む。l(a)=3となるa=8.[br]x≡8(mod 13)。[br]つまりpowermod(8, 1233,13)=8が表の読み取りで求められた。[br][br][color=#0000ff]（例）[/color]「1次合同式11x≡9(mod 13)の解」は？[br]原始根が2[br]両辺の対数をとり、指数を取り出そう。[br]I(11x)≡I(9)(mod12)[br]I(11)+l(x)≡I(9)(mod12)[br]指数取り出し表で指数にする。aからI(a)を読む。I（9)=8[br]7+l(x)≡8(mod 12)[br]l(x)≡8-7=1(mod 12)[br]べき表でI(a)からaを読む。l(a)=1 となるa=2. x≡2(mod 13)。[br][color=#0000ff][br]（例）[/color]「1次合同式 19x≡23(mod 37）の解」は？[br]mod37のべき表から[br]mod36の指数取り出し表を作ることから始めよう。[br]a = [br]{ 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}[br][br]I(a)=[br]{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}[br][br]両辺の対数をとり、指数を取り出そう。[br]I(19x)≡I(23)(mod 36)　[br]対数法則[br]I(19)+I(x)≡I(23)(mod36)[br]指数取り出し表で指数にする。aからI(a)を読む。l(23)=15.[br]35+I(x)≡15(mod36)[br]移項する[br]I(x)≡15-35≡-20+36≡16(mod36)。[br]べき表として使う。I(a)からaを読む。I(a)=16から逆にたどると、a=9。[br]x≡9(mod 37)。[br][br][color=#0000ff]（例）[/color]「合同式 7x[sup]20[/sup]≡34(mod 37）の解」は？[br]両辺の対数をとり、指数を取り出そう。[br]I(7)+20 l(x)≡I(34)(mod 36)　[br]指数取り出し表で指数にする。aからI(a)を読む。l(34)=8[br]32+20 I(x)≡8(mod36)[br]移項する[br]20 I(x)≡8-32≡-24+36≡12(mod36)。[br]係数と法がすべて4の倍数なので、4で合同式を簡約する。[br]5 I(x)≡3(mod 9) [br](1+9)/5=2から、5×2≡10≡1(mod 9)となり、　5の逆元は2。[br]I(x)≡5[sup]-1[/sup]3≡2・3≡6(mod 9)⇒6, 15, 24, 33(mod 36)。[br]I(x)≡6, 15, 24, 33(mod 36)。[br]べき表として使う。I(a)からaを読む。[br]x≡27,23,10,14(mod 37)。[br]