推理過程

費馬小定理

p是素數(shù)

a^p-1%p=1

a^p%p=a%p

k1 =pow(g,a1*(p-1),n)

k1 =g^(a1*(p-1))%n

k1 =g^(a1*(p-1))+kn

#兩邊同時模上p

k1%p=g^(a1*(p-1))%p+kn%p

k1%p=g^(a1*(p-1))%p

k1%p=(g^a1)^(p-1)%p

#根據(jù)費馬小定理

k1%p=1

k1-1=kp

#利用公約數(shù)的原理

p=gcd(k1-1,n)

q=n//p

c1 = (pow(k1,b1,n)*flag)%n

c1=(k1^b1%n*flag)%n

c1=(k1^b1%n*flag%n)%n

c1=(k1^b1*flag)%n

c1=(k1^b1*flag)+kn

#兩邊同時模上p

c1%p=(k1^b1*flag)%p

c1%p=(k1^b1%p*flag%p)%p

#k1%p=1

c1%p=((k1%p)^b1)%p*flag%p)%p

c1%p=(1^b1)%p*flag%p)%p

c1%p=(1*flag%p)%p

c1%p=flag%p

c1%p=flag