天才一秒记住【狂风中文网】地址：https://www.kfzw.net
）
比如，要找a=558和b=396的最大公因数，第一次减法后我们得到r=558-396=162，因此新数对是396和162。
由于396-162=234，所以我们的第三对数是234和162。
随着我们继续下去，完整的数对依次是：
（558，396）→（396，162）→（234，162）
→（162，72）→（90，72）→（72，18）→（54，18）
→（36，18）→（18，18）。
因此558和396的最大公因数是18。
还可以根据待考察的数对各自的素因数分解来写出它们的最大公因数。
在这个例子里，558=2×32×31，而396=22×32×11；取两个分解中各个素数的共同次幂，我们得最大公因数为22×32=18。
然而，对于大数而言，使用欧几里得算法需要的工作量少得多，因为一般执行减法运算比寻找素因数分解更简单。
欧几里得算法的另一项优点是总可以倒着做，这样便可以将最大公因数用原始的两个数来表示。
为了更好地看清楚这是怎么做到的，我们在刚才这个例子里将计算压缩。
在依次相减的过程中，同样的数重复出现了好几次，我们可以把它们表达在一个方程里。
这样我们就得到以下几个等式：
558=396＋162；
396=2×162＋72；
162=2×72＋18；
72=4×18。
从第二行开始到最后一行，我们可以用各个等式逐个消去中间余数。
在这个例子中，先利用倒数第二个等式，然后是它上面的那个，我们得到：
18=162-2×72=162-2×（396-2×162）
=5×162-2×396。
最后我们再用第一个等式，把第一个中间余数162也消去：
5×162-2×396=5×（558-396）-2×396
=5×558-7×396=18。
无论是对于实践还是理论，可以倒过来执行这一程序都是很重要的。
特别是在解密里，为了找出爱丽丝的解密数d，我们想要d满足de除以φ（n）余1的条件。
为了简洁，我们用一个单独的符号k来代表φ（n）。
现在就可以看出我们坚持要e和k互素的原因了。
因为如果它们的最大公因数是1，当我们对e和k执行欧几里得算法时，最终出现的余数自然是1。
倒过来执行这一算法，我们就能最终把1表示成e和k的组合。
特别地，我们会找到整数c和d，它们满足ck＋de=1，或者换句话说de=1-ck。
因此de除以k会余1。
这个相对简单的过程将给出爱丽丝的解密数d：直接从方程里得出的d的值可能不在1到k的范围内；倘若不在，通过加上或减去合适的k的倍数，我们最终可以找到那个d，在给定范围内，它是唯一具有de除以k余1这个神奇性质的数。
（我们可以轻松证明d的唯一性，不过这里还是不要离题太远了。
）这便是如何计算解密数d的方法。
我们可以回到前面的例子来说明，这里p=5，q=13，于是n=pq=5×13=65。
我们有φ（n）=（p-1）（q-1）=4×12=48。
爱丽丝设定e=11，由于11与48互素，这在游戏规则所允许的范围内。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！