java - 无法解释伪代码行(RSA 乘法逆)

Question

我一直在研究如何使用扩展欧几里得算法实现 RSA 加密来查找私钥 d。我读到的每一篇关于它的文章都会引导人们访问 Wikipedia's website on the topic .

这很棒，而且非常有帮助，除了一件事:我无法理解维基百科的伪代码在说什么。

我在使用以下行时遇到问题:“模整数”部分中的(t, newt) := (newt, t - 商 * newt)。这是我的解释:

int tempT = newt;
newt = t - quotient * newt;
t = tempT;

这是正确的吗？感谢您的宝贵时间!

Answer 1

这是解释此伪代码的正确方法。这是一个元组到另一个元组的分配。每个元组的元素被分配到各自的位置，并且值同时改变。

最好用一个例子来解释这一点。如果开始时 t=5、quotient=4 和 newt=6，则 (t, newt) := (newt, t - quotient * newt) 执行以下操作:

t 被赋予 newt 的初始值 (6)。然后 newt 被分配，就好像 t 不只是被重新分配一样。 newt 变为 5-4*6=-19。最后，t=6，newt=-19(商不变)。

为了在 java 中实现这一点，必须将 newt 的原始值存储在临时变量(代码中的 tempT)中。