互联网使用的先进密码实际上是基于数百年前的一个数学发明——时钟计数器，当时连互联网的影子都没出现呢。在4.12节中，我们将介绍时钟计数器是如何运用在互联网密码中的，现在先来看一下这些计数器的工作原理。

先看一下12个小时的时钟。我们都比较熟悉这类钟表上的加法运算，比如，九点过后再过4个小时就会变成一点。这种算法与把这2个数字相加后，再除以12得余数的算法相同，写法如下：

4+9=1（模12）

之所以写“模12”，因为12是这里的模数，即数字循环的终点。我们不必非得锁定12这个数字，也可以针对小时数不同的时钟来进行相似的运算。比如，对于一个只有10小时的钟表来说：

9+4=3（模10）

那么，应该如何在时钟计数器上做乘法运算呢？所谓乘法运算，就是重复一定次数的加法运算。比如，4×9就是把4个9小时相加在一起。那么在12小时的时钟上，4个9小时相加后，时针停在哪里呢？9+9等于6点。每次加一个9小时，就等于将时针向回拨3个小时，直到最终回到12点。由于0在数学中是一个十分重要的数字，因此我们将时钟计数器的这一位置称为0点。于是，我们便得到了以下这个看似古怪的结果：

4×9=0（模12）

那么幂数要怎么算呢？比如9⁴就是将4个9相乘。我们刚刚学到如何进行模数的乘法运算，现在这个应该难不倒我们了。不过，由于此时数字已经变得相当巨大，更简单的做法应当是计算出十进制结果后再除以12求余数，而不是一圈圈地在12小时的时钟上绕。先来算9×9，结果为81。那么81除以12后的余数是多少呢？换句话说，81点到底是几点？结果还是9点。不论我们把多少个9乘起来，最终得到的依然是9点：

9×9=9×9×9=9×9×9×9=9⁴=9（模12）

时钟计数器的计算方式，就是把一个普通计算器上的计算结果除以该时钟上的小时数后再求余数。但时钟计数器的优势在于，有时我们并不需要事先在传统计算器上进行计算。比如，你能否在一个12小时的时钟计数器上算出7⁹⁹的值？提示：先计算7×7，然后在其基础上再乘以7。这时候，看出什么端倪了吗？

对于小时数为质数（比如p）的时钟计数器上的运算，费马提出了一项根本性发现。他发现，找来该计数器上的一个数字，求其p 次幂，最终计算出的结果总是开始的那个数字。这便是费马小定理，命名中的“小”字是为了将其与著名的费马大定理区分开来。

表4-13中包含了一些质数时钟或非质数时钟上的运算。

表　4-13

比如，5是一个质数，如果我在一个有5小时的时钟计数器上计算2的5次方，所得出的结果依然是2。即2⁵=2（模5）。这种神奇的现象只要当时钟上的小时数为质数时都是成立的。而在非质数时钟上，则不一定会成立。比如，6不是质数，在一个6小时的时钟计算器中计算2⁶所得出的结果就不是2，而是4。

随着时针在时钟上划动，出现了一种模式。经过p-1步，我们便可确定，下一步后时针将返回到起始点，因此，该模式每p-1步重复一次。有时，这种模式也会在p-1步中重复好几次。比如，在一个有13个小时的时钟上，当我们依次计算3¹、3²，一直到3¹³， 可得到以下数列：

3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3

时针并未指向时钟上的每一个时刻，但这种重复模式依然成立，将13个3相乘之后，时针依然会回到3点上面。

我们在第3章介绍扑克游戏中用来作弊的完美洗牌法时，也遇到过相似的数学模式。当时，我们通过改变纸牌的数量，进而来确定需要多少次完美洗牌才能够整副牌完全恢复到初始状态。一幅有2N 张牌的纸牌最多需要2N-2次完美洗牌，但有时远不需要这么多次即可完全恢复到 初始状态。比如，一幅52张的纸牌只需要8次完美洗牌即可，但一幅 54张的纸牌就需要52次完美洗牌才能够恢复到初始状态。

费马从未对这一理论提出完美解释，而是将其作为一项挑战（为何上述运算适用于质数时钟）留给了后世的数学家们。最后由莱昂哈德·欧拉提出相关证据，进而论证了为何上述运算适用于质数时钟。(www.daowen.com)

费马小定理

这里是对费马小定理的一个解释。该定理指出，在一个小时数为质数p 的时钟上面：

A ^p = A（模p）

论证过程十分困难，但专业性并不高，要理解它，只要专心看下去即可。

我们先来看一个简单例子。当A=0时，该定理是成立的，因为不管我们将多少个0乘在一起，最终得到的还是0。那么，我们就先假定A 不是0。接下来我们要开始试着证明在这只时钟上将p-1个A 相乘之后，结果会转到1点的位置。如此一来，该定理即可被证实，因为当我们将1再乘以A 后，结果总会得到A 。

首先，我们列出这只时钟上的除0点以外的所有整点。共有p-1个：

1, 2, …, p-1

然后将以上的每个数字乘以A，可得到

A ×1, A ×2, …, A (p-1)（模p）

下面让我来向你证明为什么这列中的结果必须全部来自于前一个序列，即1, 2, …, p-1，但排列顺序会不一样。如果不是这样，那么或者结果中有一个是0，或者存在两个一样的结果。此外，便不可能出现任何其他情况，因为该时钟上只有p 个小时。

假设在p 小时的时钟上计算出的A·n和A·m的数值相同，其中n 和m 位于1至p-1的区间中（我将证明为何这一点将推导出n=m）。因此，在这个时钟计数器上，A·n-A·m=A·(n-m) 的值等于零，即在普通计算器中，A (n-m) 的计算结果能被p整除。

接下来论证的关键就要围绕p是质数这个事实了。数字A(n-m)就像一个化学分子，它是由数个构成A 和构成n-m 的质数原子相乘得来的。现在，我们已经知道p 是一个质数，因此，p 是其中一个无法拆分的数学原子。由于数字A(n-m) 能够被p 整除，因此，p 一定是构成A(n-m) 的其中一颗原子，因为一个数字拆分后得到的质数只有一种可能性。但是，p 无法被A 整除，因此它必须能被n-m 整除。即p 为构成n-m 的一个质数原子。这又是什么意思呢？这就意味着在这个p 小时的时钟上，n 和m 处于相同时刻。我们也可以用同样的论证证明出A×n 不可能为零，除非A 和n 之中有一个为零。

这里要记住，时钟的小时数是质数这一点是非常重要的，正像我们已知的那样，在一个12小时的时钟计数器上看到过4×9等于0的运算，但是，其中的4和9都不是零。

现在，我们有2个列表——1, 2, …, p-1和A×1, A×2, …, A×(p-1)，均由相同的一套数字组成，只是排列顺序有所不同。此时，我们可借助于一个精妙的技巧，费马本人可能也发现了这个技巧。如果把两列中的数字各自相乘，应该会得到同样的结果，因为在乘法运算中，数字的排列顺序并不会对结果产生影响。第一列数字相乘得1×2×…×(p-1)，我们将之写为(p-1)!第二列数字相乘后，其中的A 乘了p-1次，再乘以同样的从1到p-1的乘积。经过稍微调整后，可得到(p-1)!×A^p-1。而这两列数字的乘积在我们的时钟计数器上所呈现的结果相同，于是：

(p-1)!=(p-1)!×A^_p-1（模p）

这也就是说，(p-1)!×(1-A^p-1)的结果是能被p 整除的。但是，从1到p-1之间的所有数字都无法被p 整除，因此(p-1)!也无法被p 整除。所以，唯一的可能就是1-A^p-1能被p 整除。这就意味着A^p-1在这只时钟计数器上所得的值必须永远为1——这便是费马给后世的数学家们留下的难题。

上述的论证过程十分有趣。例如，如果A×B 能够被一个质数p 整除，那么A 和B 之中必须有一个能够被该质数整除，这一点是由质数的特殊属性决定的。这一推导自然是非常重要的，不过在我看来，其中最美妙的部分则是从两种不同的角度来看待同一条数列1, 2, …, p-1。这简直是横向思考的绝妙案例。