五二小说网

手机浏览器扫描二维码访问

04 密码学 素数的秘密生活 Cryptography the Secret Life of Primes（第6页）

当然，就像我们已经看到的，余1的7的最小幂次不是40，而是它的因数4。

以上这些都是为了表明，鲍勃确实可以求出发送给爱丽丝的数，me模n，同时不需要鲍勃的计算机做出太多努力。

不过，在实际操作中涉及的数依然大到可怕，因此我们有必要进一步说明如何处理它们。

计算me所涉及的高次幂可以分阶段进行，这个过程叫作快速求幂（fastexpoion）。

简而言之，这一方法运用连续求平方以及幂的相乘来得出me模n，我们可以用二进制形式的e引导算法，从而在相对少的步数里快速找到想要的余数。

欧几里得教爱丽丝找到她的解密数

为了找到d，爱丽丝的电脑可以利用一个代数工具——欧几里得算法，这一工具已经有2300多岁了。

稍后我们就来介绍它。

如果伊芙的计算机知道去解哪个方程，那它当然也能做到同样的事情。

然而，因为p和q是爱丽丝私有的，（p-1）（q-1）也是，因此伊芙并不知道从哪里着手。

加密数（公开的）e需要满足一个温和的限制条件，才能保证d的存在。

爱丽丝必须确保e与φ（n）没有公因数。

这很容易做到，爱丽丝可以检验用不同的素数除φ（n）的结果，从而保证既不泄露p和q的值也让e满足限制条件。

实际应用中，e的值常常使用第四个所谓的费马素数（Fermatprime）e=65537=216+1。

这个值，224+1，具有一个尤其稀有的性质，即可以用直尺和圆规（straightedgeandpass）作出一个有e条边的正多边形。

不过，它在密码学中的用处在于它是一个很大的（恰好比某个2的幂大1的）素数，这非常适合运用之前提到的快速求幂过程。

回到欧几里得算法。

这个算法是通过推广以下的观察结果得到的，即对于两个数a＞b，可以通过连续的相减来找到最大公因数（highestonfactor），最大公因数也叫作最大公约数（greatestondivisor）。

我们注意到r=a-b有一项性质：a，b，r中任意两者的公因数也是第三个数的因数。

例如，如果c是a和b的公因数，于是a=ca1并且b=cb1，我们看到r=a-b=ca1-cb1=c（a1-b1），这就得出了r包含c的一个因数分解。

于是，a和b的最大公因数等于b和r的最大公因数。

因为这两个数都小于a，我们现在面对的是跟之前一样的问题，不过是相对于两个更小的数。

重复应用这个方法，最终会得到一对数，它们的最大公因数可以一眼看出。

（实际上，最后手中的两个数会变成相等的，因为如果不是这样，我们可以继续多做一步。

这对数共同的值就是我们找的那个数。

）

比如，要找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；取两个分解中各个素数的共同次幂，我们得最大公因数为2×32=18。

然而，对于大数而言，使用欧几里得算法需要的工作量少得多，因为一般执行减法运算比寻找素因数分解更简单。

欧几里得算法的另一项优点是总可以倒着做，这样便可以将最大公因数用原始的两个数来表示。

为了更好地看清楚这是怎么做到的，我们在刚才这个例子里将计算压缩。