无法解读RSA乘法逆元相关伪代码行（扩展欧几里得算法）

嘿，我完全明白你盯着那行伪代码抓耳挠腮的感觉——扩展欧几里得算法的变量更新逻辑一开始确实有点绕，尤其是结合RSA求私钥d的场景时。让我一步步拆解给你看：

核心问题：并行赋值 vs 分步赋值 #

你看到的伪代码：

(t, newt) := (newt, t - quotient * newt)

这是并行赋值，和你尝试的分步写法完全等价，但要注意：赋值是同时完成的，右边的所有表达式都是用赋值前的原始t和newt计算的。你的分步写法完全正确：

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

两者没有功能差异，只是伪代码用并行赋值更简洁地表达了“同时更新两个变量”的逻辑。

为什么要这么更新？结合RSA场景解释 #

扩展欧几里得算法的核心是：找到整数x和y，使得a*x + b*y = gcd(a,b)。在RSA中，我们需要求私钥d，本质是找e的模φ(n)逆元——也就是满足e*d ≡ 1 mod φ(n)，这等价于找到d使得e*d + φ(n)*k = 1（k是整数），刚好对应扩展欧几里得算法中a=φ(n)、b=e时的线性组合系数。

算法中维护的t和newt，是用来跟踪当前余数对应的线性组合系数的：

• 每一步我们通过欧几里得算法更新余数：(old_remainder, new_remainder) = (new_remainder, old_remainder - quotient * new_remainder)
• 同步更新t和newt，是为了保证new_remainder = s*φ(n) + t*e（s是另一组对应φ(n)的系数）

举个实际RSA例子 #

假设e=7，φ(n)=20（满足gcd(7,20)=1，符合RSA要求），我们一步步算d：

1. 初始状态：
   • 余数：rem1=20，rem2=7
   • 系数：s=1，news=0；t=0，newt=1
   • 对应关系：20=1*20+0*7，7=0*20+1*7
2. 第一步：
   • quotient=20//7=2
   • 更新余数：rem1=7，rem2=20-2*7=6
   • 更新系数：(s, news)=(0,1-2*0)=(0,1)；(t, newt)=(1,0-2*1)=(1,-2)
   • 对应关系：6=1*20 + (-2)*7（验证：20-14=6，正确）
3. 第二步：
   • quotient=7//6=1
   • 更新余数：rem1=6，rem2=7-1*6=1
   • 更新系数：(s, news)=(1,0-1*1)=(1,-1)；(t, newt)=(-2,1-1*(-2))=(-2,3)
   • 对应关系：1=(-1)*20 +3*7（验证：-20+21=1，正确）

此时余数为1，对应的t=3就是我们要的私钥d——因为7*3=21≡1 mod20，完美符合逆元的要求。如果最终得到的t是负数，只需要加上φ(n)就能转成正的合法私钥。

关键总结 #

• 那行伪代码的本质是同步更新线性组合系数，保证每一步的余数都能表示为φ(n)和e的整数组合；
• 你的分步赋值理解完全正确，只是伪代码用并行写法更简洁；
• 当算法运行到余数为1时，对应的t（调整正负后）就是RSA的私钥d。

内容的提问来源于stack exchange，提问作者retrovius