RSA加密算法五：扩展欧几里得算法计算d
之前的算法中d的值是枚举的，总觉得很奇怪，虽然是为了演示
这次用官方指定算法：扩展欧几里得算法来计算得到d的值
代码只写如何从p,q,e中得到d
def egcd(a, b):
if b == 0:
return a, 1, 0
else:
g, x, y = egcd(b, a%b)
d = x-a/b*y
return g, y, d
def get_d(fn,e):
d = egcd(fn, e)[2]
if d < 0:
d = d+fn
return d
p, q, e = 61, 53, 17
fn = (p-1)*(q-1)
print get_d(fn, e)
计算得到的结果为 2753
