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