计算RSA中的d值
Calculating d value in RSA
我看到了几个关于此的问题，但其中大部分的回答都没有帮助，或者根本没有得到正确的答案。
我有这些变量：
- p = 31
- q = 23
- e - public 关键指数 = 223
- phi - (p-1)*(q-1) = 660
现在我需要计算 d 变量（我知道它等于 367）。问题是我不知道怎么做。我在互联网上找到了这个方程式，但它不起作用（或者我不能使用它）：
e⋅d=1modϕ(n)
当我看到那个等式时，我认为它的意思是：
d=(1modϕ(n))/e
但显然不是，因为 367 (1modϕ(n))/e = 1%660/223 = 1/223 != 367
可能我不明白，我做错了什么 - 这就是我问的原因。
我做了更多研究，发现了第二个等式：
d=1/e mod ϕ(n)
or
d=e^-1 mod ϕ(n)
但最后它给出了相同的结果：
1/e mod ϕ(n) = 1/223 % 660 = 1/223 != 367
然后我看到有人说要解那个方程你需要extended Euclidean algorithm如果有人知道如何用它来解决那个问题那么如果你能帮助我我将不胜感激。
如果你想计算像 a / b mod p 这样的东西，你不能只除以它并从中取余数。相反，你必须找到这样的 b-1 使得 b-1 = 1/b mod p (b-1 是 b mod p) 的 mod 元乘法逆元。如果p是素数，可以用Fermat's little theorem。它指出对于任何素数 p，ap = a mod p <=> a(p - 2) = 1/一个 mod 页。因此，您必须计算类似 a * b(p - 2) mod p 的内容，而不是 a / b mod p。 b(p - 2) 可以在 O(log(p)) 中计算
使用 exponentiation by squaring. If p is not a prime, modular multiplicative inverse exists if and only if GCD(b, p) = 1. Here, we can use extended euclidean algorithm 在对数时间内求解方程 bx + py = 1。当我们有 bx + py = 1 时，我们可以取 mod p 并且我们有 bx = 1 mod p <=> x = 1/b mod p，所以 x 是我们的b-1。如果GCD(b, p) ≠ 1, b-1 mod p不存在.
使用费马定理或欧几里得算法在相同的时间复杂度下得到相同的结果，但欧几里得算法也可以用于计算 modulo 不是素数的数（但它必须与要除以的数字互质）。
我看到了几个关于此的问题，但其中大部分的回答都没有帮助，或者根本没有得到正确的答案。
我有这些变量：
- p = 31
- q = 23
- e - public 关键指数 = 223
- phi - (p-1)*(q-1) = 660
现在我需要计算 d 变量（我知道它等于 367）。问题是我不知道怎么做。我在互联网上找到了这个方程式，但它不起作用（或者我不能使用它）：
e⋅d=1modϕ(n)
当我看到那个等式时，我认为它的意思是：
d=(1modϕ(n))/e
但显然不是，因为 367 (1modϕ(n))/e = 1%660/223 = 1/223 != 367
可能我不明白，我做错了什么 - 这就是我问的原因。
我做了更多研究，发现了第二个等式：
d=1/e mod ϕ(n)
or
d=e^-1 mod ϕ(n)
但最后它给出了相同的结果： 1/e mod ϕ(n) = 1/223 % 660 = 1/223 != 367
然后我看到有人说要解那个方程你需要extended Euclidean algorithm如果有人知道如何用它来解决那个问题那么如果你能帮助我我将不胜感激。
如果你想计算像 a / b mod p 这样的东西，你不能只除以它并从中取余数。相反，你必须找到这样的 b-1 使得 b-1 = 1/b mod p (b-1 是 b mod p) 的 mod 元乘法逆元。如果p是素数，可以用Fermat's little theorem。它指出对于任何素数 p，ap = a mod p <=> a(p - 2) = 1/一个 mod 页。因此，您必须计算类似 a * b(p - 2) mod p 的内容，而不是 a / b mod p。 b(p - 2) 可以在 O(log(p)) 中计算 使用 exponentiation by squaring. If p is not a prime, modular multiplicative inverse exists if and only if GCD(b, p) = 1. Here, we can use extended euclidean algorithm 在对数时间内求解方程 bx + py = 1。当我们有 bx + py = 1 时，我们可以取 mod p 并且我们有 bx = 1 mod p <=> x = 1/b mod p，所以 x 是我们的b-1。如果GCD(b, p) ≠ 1, b-1 mod p不存在.
使用费马定理或欧几里得算法在相同的时间复杂度下得到相同的结果，但欧几里得算法也可以用于计算 modulo 不是素数的数（但它必须与要除以的数字互质）。