五二小说网

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

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

麻烦的地方在于，除非你知道p和q中至少一个，否则不可能准确地找到那个要解的方程。

这便是挡在伊芙道路上的障碍。

我们可以再进一步解释，以上涉及的数如何在这个系统中各司其职。

首先，很明显鲍勃一开始就面临着一个大问题，m很大，n更是可怕（在200位数字这个量级上）。

即便e的值不像那样夸张，me也是极其大的。

计算出它之后，我们还得将me除以n来得到余数r，这代表了被加密的文本。

这些计算太过繁杂，以至于看起来也许并不可行。

我们需要意识到，即使现代计算机异常强大，它们还是有能力极限。

当计算涉及很高次的幂，就可能会超过任何计算机处理能力的极限。

我们不能假设电脑可以在短时间内完成任何我们交给它们的计算任务。

鲍勃有根救命稻草是，他完全可以不做很长的除法就找到要求的余数r。

实际上，余数仅仅取决于余数。

这里我们举一个例子来说明，739的最后两位是多少？（换句话说，当这个数被100除后余多少？）为了回答这个问题，我们可以从计算7的前几次幂开始：71=7，72=49，73=343，74=2401，75=16807，…。

不过很快我们就清楚地发现，离739还远着的时候，这些数已经变得相当大，我们都处理不过来了。

另一方面，随着我们算出一个又一个幂次，一个关键的规律出现了。

当计算连续的幂次时，结果的最后两位数字仅依赖于前一个数的最后两位。

这是因为我们做乘法时，百位及以上的数字并不会影响到结果在个位和十位上的数字。

同时，因为74末尾两位是01，所以接下来四个幂的末尾依次是07，49，43，接着又是01。

因此，随着我们挨个计算幂次，末尾两位的数字只会一遍又一遍地重复这个长度为4的循环。

回到我们手上的问题，由于39=4×9+3，我们会经历这个循环九次，然后还需要三步来计算739的最后两位数，因此结果一定是43。

这样的技巧是相当普适的。

比方说，为了找到某个幂次ab除以n所得的余数，我们只需要取a除以n所得的余数r，并追踪r的各次幂除以n之后的余数。

余数r一定是大于或等于0、小于或等于n-1之间的一个数。

在我们只关心r的时候，数学家们说我们是在求模（modulo）n。

我们舍弃了所有n的整数倍，因为它们除以n余0，所以不会对最终的余数r有任何贡献。

你可能还是在怀疑，我是不是通过选择特殊的例子操纵了证据，这个例子里一个很小的幂次就给出了余数1——这里74比100的某个整数倍大1。

然而，你怀疑的情况只在部分程度上成立。

事实上，如果我们取任意两个数，a和n，它们的最大公因数为1，我们说这些数是互素的（e），那么总存在一个指数t，使得幂at等于1模n——也就是说被n除时余1。

从这个角度说，连续次幂的余数会构成周期为t的循环。

但是，预测t的值却很难。

不过人们知道t总等于一个特殊的数或是它的某个因数。

这个数传统上被写作φ（n），代表欧拉φ函数（phifun）的值。

这跟我们直接从定义得到的结果是一样的。

使用这个方法，你可以自己验证φ（100）=40。

因此，可以推出740同余于1模100。