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

标签 math rsa modulo

我正在解决一个示例问题,RSA algorithm
我得到了两个素数 7 和 11。比如说 p=7q=11
我必须为某个加密 key e 计算解密 key d

首先我计算了 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,这个结果是怎么得到的?

任何帮助将不胜感激。

最佳答案

我想这就是你要找的东西

验证答案很容易,首先找到它,然后再做一些工作。

验证:

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 

这就是答案。

关于math - 如果 13* D = 1 mod 60 那么 D = 37 如何?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19888186/

相关文章:

c# - 如何四舍五入到特定的小数精度?

java - 为 float[] 中的值生成与 long 相同的唯一 ID/Hash 的算法

node.js - nodeJS 引用错误 : navigator is not defined.

c++ - 编译时(constexpr)浮点模?

java - C 中的 eval 函数结果为负

java - 如何在 Java 中对数字进行四舍五入?

javascript - Rsaencrypt 和奇怪的 Javascript 函数(e,t,r,n,c,a,l)

math - 部分密文的RSA加密和解密?

c++ - 你为什么要将 10^9+7 加到一个数字上,然后用 10^9+7 求模

c# - 从 long 中截断 0 代替 % 10 的更快方法