如果13 * D = 1 mod 60则D = 37怎么样？

Question

我正在解决一个示例问题，RSA algorithm我得到了两个质数7和11。假设p=7和q=11我必须为某些加密密钥d计算解密密钥e。

首先我计算了n=p*q，这意味着n=77。

假设e=13，为了计算d，我使用了公式d*e = 1 mod fi，fi=(p-1)(q-1)，等等fi=60

最终方程变为13*d = 1 mod fi

根据一些已解决的示例d被计算为37，如何获得此结果？

任何帮助将不胜感激。

Answer 1

我认为这是您想要的

验证答案很容易，首先找到答案，还有更多工作。验证：

13 * 37 = 481 
481 = 8 * 60 + 1

因此，如果将13 * 37除以60，就剩下1。替代答案：（k + 60 k）形式的任何整数（其中k是任何整数）也是一个解决方案。 （97，-23等）要找到解决方案，您可以按照以下步骤操作：解决：

13 d = 1 + 60 k 
mod 13:
0 = 1 + 8k (mod 13) 
8k = -1 (mod 13) 
Add 13's until a multiple of 8 is found: 
8k = 12 or 25 or 38 or 51 or 64 .... aha a multiple of 8! 
k = 64 / 8 = 8 
Substitute k = 8 back into 13 d = 1 + 60 k 
13 d = 1 + 8 * 60 = 481 
481 /13 = 37 

这就是答案。

Answer 2

使用extended Euclidean algorithm计算整数x和y，使得>

13*x+60*y=1
然后x是您正在寻找的答案，mod 60。