我可以计算$ \ varphi （N）= 40 $，但是我的讲师随后说使用扩展的欧几里得算法来计算$ d $。这就是我被卡住的地方。
到目前为止，这是我的工作：
首先，我使用Euclid算法进行计算：
40 = 2(17) + 6
17 = 2(6) + 5
6 = 1(5) + 1 = gcd
所以我知道GCD为1。应用算法的“扩展”部分：
，但我不知道如何使用扩展的Euclidean算法到达那里。我不知道为什么我得到$ 3（40）-3（17）$时我知道答案应该包含$ 33 $。
#1 楼
扩展的Euclidean算法本质上是Euclidean算法（针对GCD）。您的目标是找到$ d $，使$ ed \ equiv 1 \ pmod {\ varphi {（n）}} $。
回想一下EED计算$ x $和$ y $使得$ ax + by = \ gcd {（a，b）} $。现在让$ a = e $，$ b = \ varphi {（n）} $，因此$ \ gcd {（e，\ varphi {（n）}）} = 1 $（对于它们，它们需要互质存在的倒数）。然后您有：
$$ ex + \ varphi {（n）} y = 1 $$
取模$ \ varphi {（n）} $，然后您会得到：
$$ ex \ equiv 1 \ pmod {\ varphi {（n）}} $$
在这种情况下，很容易看到$ x = d $。 $ y $的值实际上并不重要，因为无论其值如何，都将以$ \ varphi {（n）} $取模来消除$ y $的值。 EED将为您提供该值，但您可以放心地将其丢弃。现在，我们有$ e = 17 $和$ \ varphi {（n）} = 40 $。写下我们的主要方程式：
$$ 17x + 40y = 1 $$
我们需要为$ x $求解。因此，应用普通的欧几里德算法：
$$ 40 = 2 \ times 17 + 6 $$
$$ 17 = 2 \ times 6 + 5 $$
$$ 6 = 1 \ times 5 + 1 $$
将最后一个写为：
$$ 6-1-\ times 5 = 1 $$
现在将第二个等式替换为$ 5 $：
$$ 6-1 \ times（17-2 \ times 6）= 1 $$
现在替换将第一个方程转换为$ 6 $：
$$（40-2 \ times 17）-1 \ times（17-2 \ times（40-2 \ times 17））= 1 $$
请注意，这是$ 17 $和$ 40 $的线性组合，经过简化，您可以得到：
$$（-7）\ times 17 + 3 \ times 40 = 1 $$
我们得出$ d = -7 $，实际上是$ 33 $模$ 40 $（因为$ -7 + 40 = 33 $）。
您可以看到，其基本思想是使用GCD计算的连续余数将初始整数代入最终方程式（等于$ 1 $的方程式），从而得出所需的线性组合。
对于您的错误，看来您刚刚进行了计算错误在这里：
3（40-2（17））-1（17）
错误地变为：
3（40）-3（17）
似乎您忘记了左侧17的3因子，正确的结果将是：
3（40-2（17））-1（17）= 3 * 40-3 * 2 * 17-1 * 17 = 3 * 40 +（-7）* 17
期望值是-7。
评论
$ \ begingroup $
错误已经在前面的行中，除非等号应为减号，并且他在左侧省略了$ 1 = $。否则，该行显示为$ 17 = 18 $。
$ \ endgroup $
– tylo
2015年5月6日14:19
#2 楼
另一个答案中的方法是说教性的，但需要回溯较早的计算，因此要保留这些计算或使用递归，这在经常用于加密的受限环境中是不希望的。另一种常用的方法是完全扩展的欧几里得算法，无需递归即可找到Bézout系数。但是，这需要跟踪输入之外的6个数量，而对于模逆，我们可以对4个数量进行处理。需要最终更正符号；并利用同时双重赋值或变量交换，这在某些计算机语言中是不直接可用的。
这是一种分步方法来计算$ e ^ {-1} \ bmod m $（并进行测试（如果已定义）非负整数$ e $和正整数$ m $。它使用半扩展的欧几里得算法，经过修改后只能处理非负数（始终最多是最大的输入）和简单赋值。
$ a \ gets e $，$ b \得到m $，$ x \ gets0 $和$ y \ gets1 $。
注意：$ ax + by = m $将继续保持，且模数为$ m $。
如果$ a = 1 $，然后输出“所需的$ e $模$ m $的逆是$ y $”并停止。
如果$ a = 0 $，则输出“所需的$ e $模数$ m $的逆。不存在”并停止（$ b $是GCD）。
$ q \ gets \ lfloor b / a \ rfloor $。
$ b \ gets b- aq $和$ x \得到x + qy $。
如果$ b = 1 $，则输出“期望的$ e $模$ m $的逆为$ mx $”并停止。
如果$ b = 0 $，然后输出“所需的$ e $模$ m $的逆不存在”并停止（$ a $是GCD）。
$ q \ gets \ lfloor a / b \ rfloor $。
$ a \得到a-bq $和$ y \得到y + qx $。
继续到2.
该问题要求将$ a = e = 17 $和$ m = \ varphi（N）= 40 $一起应用。
在步骤1上：$ a = 17 $，$ b = 40 $，$ x = 0 $， $ y = 1 $。
在步骤4/5：$ q = 2 $，$ b = 6 $，$ x = 2 $，（$ a = 17 $和$ y = 1 $不变）
在步骤8/9中：$ q = 2 $，$ a = 5 $，$ y = 5 $（（$ b = 6 $和$ x = 2 $不变）
在步骤4/5：$ q = 1 $，$ b = 1 $，$ x = 7 $，（$ a = 5 $和$ y = 5 $不变）
在步骤6中，我们输出“所需的$ 17 $模$ 40 $的逆是“ $ mx = 33 $。
#3 楼
了解扩展的欧几里得算法的一种有用方法是关于线性代数。（这对于fgrieu的答案有些多余，但是我还是决定发表这篇文章，因为我是在fgrieu扩大他们的答案之前开始写这篇文章的。希望稍有不同的观点可能仍然有用。）
假设我们试图找到$ e $取模$ \ varphi $的逆数，即一个数字$ d $使得$$ de \ equiv 1 \ pmod \ varphi。$$换句话说，给定$ e $和$ \ varphi $，我们希望找到线性方程$$ de + k \ varphi = 1的整数解$（d，k）$。 $$当然，我们知道只有$ \ gcd（e，\ varphi）= 1 $时，该方程才可解。更一般而言，如果不是这种情况，我们可以期望的最好办法是解决广义方程$$ de + k \ varphi = r，$$，其中$ r = \ gcd（e，\ varphi）$是最小的正整数，存在这样的解决方案。
碰巧，我们已经对此方程有几个平凡的解决方案，包括$$ \ begin {aligned} d_0＆= 0，＆k_0＆= 1， ＆r_0＆= \ varphi，＆\ text {and} \\ d_1＆= 1，＆k_1＆= 0，＆r_1＆= e。\ end {aligned} $$
如上所述，我们对最小化$ r $的解决方案特别感兴趣，而这些琐碎的解决方案通常不会这样做。但是，我们希望从高中代数中记住，从另一个有效方程式的相应两侧减去一个有效方程式的两侧，还会得出另一个有效方程式：如果$ x = y $和$ p = q $，则$ x-p = y-q $。
因此，假设$ r_0 = \ varphi> r_1 = e> 0 $，我们可以通过反复减去等式$ d_1e + k_1 \ varphi的两边来获得具有甚至更小（但仍为非负）的$ r $的另一种解决方案。 =从$ d_0e + k_0 \ varphi = r_0 $的对应边开始r_1 $，直到得到的结果$$ \ begin {aligned} d_2＆= d_0-a_1d_1，＆k_2＆= k_0-a_1k_1，＆r_2＆= r_0-a_1r_1 ，\ end {aligned} $$其中$ a_1 $是我们从较大的解决方案中减去较小的解决方案的次数，满足$ r_2
在这两个平凡的初始解中，我们可以使用重复的$$ \ begin {aligned} d_ {i + 1}＆= d_ {i-1} -a_i d_i，＆k_ { i + 1}＆= k_ {i-1} -a_i k_i，＆r_ {i + 1}＆= r_ {i-1} -a_i r_i，\ end {aligned} $$其中$ a_i = \ left \ lfloor \ frac {r_ {i-1}} {r_i} \ right \ rfloor $。
我们可以继续重复此过程，直到最终发现$ r_i $均匀地将$ r_ {i- 1} $（这意味着$ r_ {i + 1} $将为零，这是我们不希望的）。到那时，如果$ r_i = 1 $，则相应的系数$ d_i $（减少的模$ \ varphi $）就是我们想要的$ e $的模逆。
否则，不难证明$ r_i $实际上将所有$ r_j $均等为$ 0 \ le j
Ps。正如fgrieu在他们的答案中指出的那样，如果我们仅对$ d $（和$ r $）感兴趣，则实际上不必跟踪$ k_i $系数。因此，该算法的实现只需要存储$ r_i $，$ d_i $，$ r_ {i-1} $，$ d_ {i-1} $和临时值$ a_i $。 （在实践中，可能还需要一些其他临时值，尽管应注意，一般不需要将$ r_ {i + 1} $和$ d_ {i + 1} $分别存储，因为它们可以立即覆盖$ r_ {i-1} $和$ d_ {i-1} $。）
这是Python中的一个简单实现（方便地内置了任意精度整数）：
def modinv(e, phi):
d_old = 0; r_old = phi
d_new = 1; r_new = e
while r_new > 0:
a = r_old // r_new
(d_old, d_new) = (d_new, d_old - a * d_new)
(r_old, r_new) = (r_new, r_old - a * r_new)
return d_old % phi if r_old == 1 else None
在线尝试！
评论
查看“扩展的欧几里得算法”维基百科文章的“在有限域中计算乘法逆”部分。不幸的是，它必须手工计算。我已经编辑了问题，以包括更多我的工作。
这个YouTube视频以一种非常容易理解的方式展示了这一点。
这段YouTube视频很好地说明了如何计算RSA的公钥和私钥：youtube.com/watch?v=kYasb426Yjk。它还说明了扩展的欧几里得算法。