math - 如果 13* D = 1 mod 60 那么 D = 37 如何？

Question

我正在解决一个示例问题，RSA 算法我得到了两个素数 7和
11。假设 我必须计算解密密钥，对于某些加密密钥，。p=7q=11
de

首先，我计算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。

替代答案：

(37 + 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

使用扩展欧几里得算法计算整数 x 和 y，使得

13*x+60*y=1

那么 x 就是你要找的答案，mod 60。