■指数合同式(その2)

指数合同式:a^x=b  (mod m)

はmが原始根gをもてば、指標をとって

  x・indg(a)=indg(b)  (mod φ(m))

のようにして解くことができる。

===================================

3^0=1、3^1=3,3^2=9,3^3=10,3^4=13,

3^5=5,3^6=15,3^7=11,3^8=16,

3^9=14,3^10=8,3^11=7,3^12=4,

3^13=12,3^14=2,3^15=6,3^16=1

であるから、m=17,g=3に対し

ind3(1)=0,ind3(2)=14,ind3(3)=1,ind3(4)=12

ind3(5)=5,ind3(6)=15,ind3(7)=11,ind3(8)=10

ind3(9)=2,ind3(10)=3,ind3(11)=7,ind3(12)=13

ind3(13)=4,ind3(14)=9,ind3(15)=6,ind3(16)=8

===================================

7^x=5 (mod 17)の場合

  x・ind3(7)=ind3(5)  (mod 16)

が成り立つ。

11x=5  (mod 16)

x=15

===================================