前面说到，我们从一个古老的数学创造里无意发现了一个检验素数的方法，可惜这个方法虽然理论上可行，但是实际操作起来工作量太大，我们想要一个轻松点的法子来进行素性检测。今天他来了，费马大法官。
主角登场
话说费马这个业余玩家实际做出的贡献比职业选手还要厉害，先别说费马大定理这个小朋友都知道的数学玩意，就说，费马数，概率论，解析几何……每一项成就都能让费马成为大数学家，他在数论这方面造诣也相当厉害，今天来说说他的一个小成就“费马小定理”。
解析几何是费马大法官的一大创造
费马小定理的定义是：
假如p是素数，那么对任意的自然数n，都有n^p≡n(mod p)，意思是n^p除以p的余数与n除以p的余数相同，或者叫n^p 与n模p同余。
来看个例子，比如p=5，我们来看下5除以n的乘方的余数是多少，先来手算一下费马小定理的正确性。
很显然，这里的n mod 5和 n^5 mod5是完全一致，这也就从一个案例中验证了费马小定理。这样的结论必须要证明，我们才敢放心大胆地用，要不，我们来简单证明一下吧。
上一节，我们在杨辉三角里已经证明了一个不错的结论，那就是：
如果(x+1)^p-x^p-1的展开式（这里已经提前把1和x^p这两项去掉了）中所有的系数都是p的倍数，那么p就是素数。
事实上，费马小定理的陈述是：p是素数时，n^p -n是p的倍数。
通过观察(x+1)^p-x^p-1，n^p -n，这两个式子仿佛有很深的内在联系，我们不妨来处理一下。
到了这个式子时，我们豁然开朗，这根本就是一个式子嘛。我们一下子就想到了数学归纳法，因此上面的问题也就变成了，一个关系对于n成立，对于n+1也是成立的。那么想要完成数学归纳法的严谨证明，我们就必须要证明初项也是成立的，这样才能说明上述命题对于所有自然数n都是成立的。
这里的n初项是1，1^p-1=0满足要求，于是我们就用了这样一个简单的方式证明了费马小定理。
上面都是对素数有效，那么对于合数呢，上面的式子还成不成立了。假设p=6，
这里的n mod 6与n^6 mod 6的值是不相同的，因此是6不是一个素数，我们把这一的过程就叫作费马素性检测，这里的6没有通过费马素性检验。
在这里，我们进行的计算次数要远远小于在杨辉三角里的运算，这是一个不错的进步。如果一个数是素数，那么它一定能通过上面的费马素性检测，反向为之，如果一个数是合数，就一定不会通过吗？
素数的奥秘太深刻
如果数的素性检测能够通过我们上面寥寥几行的证明就能说明到位，那素数就也不值得怎么研究了。事实上，即使有些数通过费马素性检测，就是有些数字p即使能够做到n mod p与n^p mod p完全相等，也不一定就是素数。比如561就能通过素性检验，但是561=3*11*17。 1910年，才由卡迈克尔（Robert Daniel Carmichael）发现第一个卡迈克尔数：561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个，561就是最小的卡迈尔数。
Carmichael 发现了第一个卡迈克尔数561
到了这里大家是不是相当灰心，怎么用到了费马小定理素性检验，到头来还是不能完全直接地判定一个数是否为素数啊。既然这样，那研究又有什么意义呢？当然有意义啊，这些前辈们的工作大大帮我们减少了对一个数做素性检验的时间复杂度！
检验一个数是否是素数是编程基础课
我们回忆一下，少年时代学习过的检验一个数是否为素数的编程方法。就是用p依次从1开始除，一直到p的平方根为止，假如都是不能整除的，那么就判定是p是素数。这里的大概要计算p平方根次。如果这里的p是一个300位的超级大数，那计算机算到冒烟也很难有结果的。后面有人在费马素性检验的基础上改进了算法，使得算法时间复杂度降低到了能够触摸的地步。
AKS算法作者之一 Manindra Agrawal
由三个来自印度坎普尔理工学院的计算机科学家，Manindra Agrawal、Neeraj Kayal和Nitin Saxena，在2002年8月6日发表于一篇题为素数属于P的论文。他们使用的方法叫作AKS素性检测，运用此种方法他们成功地将素性检测的时间复杂度降低到Ο(log12n)。这个成果使得那些本来用超级计算机算到宇宙毁灭也不会有结果的数学问题一下子就变得触手可及了。2005年，这个算法又被改进到Ο(log6n)，这个就更加放了人们在茫茫数海捞出素数的进程了。
下一场 欧拉又要出马了
现在我们又一次作了关于现代基于素数的加密系统的基础知识，下一篇，我们又将迎来我们亲爱的大神--欧拉大师了，我们都很怀念他。
