天才一秒记住【狂风中文网】地址：https://www.kfzw.net
同时，因为74末尾两位是01，所以接下来四个幂的末尾依次是07，49，43，接着又是01。
因此，随着我们挨个计算幂次，末尾两位的数字只会一遍又一遍地重复这个长度为4的循环。
回到我们手上的问题，由于39=4×9＋3，我们会经历这个循环9次，然后还需要三步来计算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），代表欧拉φ函数（Eulerphifun）的值。
这跟我们直接从定义得到的结果是一样的。
使用这个方法，你可以自己验证φ（100）=40。
因此，可以推出740同余于1模100。
当然，就像我们已经看到的，余1的7的最小幂次不是40，而是它的因数4。
以上这些都是为了表明，鲍勃确实可以求出发送给爱丽丝的数me模n，同时不需要鲍勃的计算机做出太多努力。
不过，在实际操作中涉及的数依然大到可怕，因此我们有必要进一步说明如何处理它们。
计算me所涉及的高次幂可以分阶段进行，这个过程叫作快速求幂（fastexpoion）。
简而言之，这一方法运用连续求平方以及幂的相乘来得出me模n。
我们可以用二进制形式的e引导算法，从而在相对少的步数里快速找到想要的余数。
欧几里得教爱丽丝找到她的解密数
为了找到d，爱丽丝的电脑可以利用一个代数工具——欧几里得算法，这一工具已经有2300多岁了。
稍后我们就来介绍它。
如果伊芙的计算机知道去解哪个方程，那它当然也能做到同样的事情。
然而，因为p和q是爱丽丝私有的，（p-1）（q-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，我们现在面对的是跟之前一样的问题，不过是相对于两个更小的数。
重复应用这个方法，最终会得到一对数，它们的最大公因数可以一眼看出。
（实际上，最后手中的两个数会变成相等的，因为如果不是这样，我们可以继续多做一步。
这对数共同的值就是我们找的那个数。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！