幂模函数方程组的解法(一)
print(pow(2, e, n))
print(pow(4, e, n))
print(pow(8, e, n))
'''
128509160179202
518818742414340
358553002064450
'''
设c1=128509160179202 c2=518818742414340 c3=358553002064450
由代码得出方程组:
c1=2^e mod n
c2=4^e mod n=2^2e mod n
c3=8^e mod n=2^3e mod n
转换成乘模运算为:
c2=2^2e mod n=(2^e * 2^e) mod n=(2^e mod n)(2^e mod n) mod n=c1^2 mod n=c1^2-kn
同理c3=c1*c2-pn(k和p都是倍数变量,无实际意义)
然后就能用gcd求最大公因数来求解n:
n = gcd(pow(c1,2)-c2,c1*c2-c3)
最后就可以通过离散对数求出e了:
e = sympy.discrete_log(n,c1,2)