幂模函数方程组的解法(一)

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)

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>