作者：氯化钡和硫酸银
时间：2014年2月4日 11:05
来源：http://blog.sina.cn/dpool/blog/s/blog_a661ecd50101ax7f.html
素性测试，通俗点说就是判断一个正整数是不是素数。
判断素数最朴素的方法当然是去试除，不过这个方法…如果要判断一个正整数 n是不是质数（有可能有几十位，甚至几百位），试除法要尝试大约根号 n 个正整数，看是不是 n 的约数。这显然太慢了。
我们希望能找出一个关于 n 的位数的多项式的算法。当然，我们并不一定要把待判断的数进行分解。
费马小定理的内容是：若 p 为素数，则对任意正整数 a 有
当然，这与a^(p-1)≡1(mod p) 是等价的（后者要求 a,p 互素）。现在我们假设 p 是任意正整数，如果我们发现对于某个特定的 a，这个式子不成立了，那么 p 不可能是素数。
这无疑为判断素数提供了一个很好的方法：对于待判断的数 p ，我们取一个 a 值（比如说 2 ），计算一下 a^p 与 a 是否模 p同余。如果不同余，那么 p 一定不是素数。
计算a^p mod p （因为我们只需要模 p 的余数）并不会很慢，可以用快速幂的方法计算。先将 p表示成 2k 或 2k+1 的形式，其中 k 为非负整数，然后递归计算出 a^k 的值，再平方，如果 p=2k+1 则需要再乘以一个a ，每次递归时指数减半，所以用时大约与 p 的位数成正比（若考虑每次平方约需要 p位数平方的时间，则用时大约与 p 的位数的三次方成正比），这是可以承受的。计算时可以边算边模 p 避免出现很大的数。
下面我们再看一个问题：如果 a^p≡a(mod p) 成立，那么 p是否一定是素数？如果是的话，那就省事了，可惜事实不是这样的。先举出一个反例：下式
是成立的（很容易计算 2^10=1024=3*341+1 ，于是 2^10 除以 341 的余数是 1 ，再算个 34次方也是除以 341 余 1 的数），但是 341=11*31 并不是素数。这种数告诉我们快速的素性测试并没那么简单。
不过我们还有补救的措施：我们多选择几个底数 a ，只要有一个不满足费马小定理的那个式子，就直接判断 p不是素数。这个方法的前提是，对于每个合数 p 都有足够多的可以证明 p是合数（即不满足费马小定理的那个式子）的“证据”，这样我们才可以在找不到证据时很确定地说 p 就是质数。
令人又一次失望的是，居然就有这样的合数 p ，它没有任何证据！比如说， 561=3*11*17 是个合数，但是对于任意整数 a，下式都是成立的：
（可以根据费马小定理验证 a^561 与 a 模 3,11,17 时都是同余的，从而上式成立）这样用这个式子随机取底数 a是没法确定 561 是合数的。如果用另一个式子，即 a^560≡1(mod 561) ，那么如果 a 与 561互质，这个式子也是成立的。
一般我们把不存在任何“证据”（对任意整数 a ，都有 a^n≡a(mod n) ）的合数 n 称为卡米歇尔数。
如果 a 与561 不互质，当然就可以判定 561 是合数。看起来这个概率也不小，不过这是因为 561这个数太小了，如果换成三个大素数相乘，乘积也是卡米歇尔数，那么随机取的底数恰好与这个数有公共的素因子的概率就太小了。例如《数论概论》第19 章末尾给的例子： 172947529=307*613*919 是卡米歇尔数。
卡米歇尔数虽然很稀有，但是足以让朴素的费马测试不被广泛应用。
在叙述米勒-拉宾素性测试之前，先来看看卡米歇尔数的一个判别法——考塞特判别法：
设 n是合数，则 n 是卡米歇尔数当且仅当：
1. n 为奇数；
2. n 不是任意奇素数平方的倍数；
3. n 的任意素因子减去 1 都是 n-1 的约数。
我们先证明满足这三个条件的合数均为卡米歇尔数，这是比较简单的：假设 n 的某个素因子为 p ，而 a 是任意整数。如果 a 是 p的倍数，则 a^n≡a(mod p) 显然成立；如果a不是p的倍数，由费马小定理得 a^(p-1)≡1(mod p) ，由 p-1 是 n-1的约数，可得 a^(n-1)≡1(mod p) 即 a^n≡a(mod p) 。
总之，对 n的任意素因子 p ，都有 a^n≡a(mod p) 恒成立。又 n 的各个素因子显然互质，把各个素因子相乘（注意这里用到了第 2条，也就是说 n 的分解中每个素因子仅出现一次），于是 a^n≡a(mod n) 成立。
下面证明所有卡米歇尔数都满足这三个条件，证明的思路是在 a^n≡a(mod n) 中取 a 的特殊值。
对于第一条，取a=-1 ，则有 (-1)^n≡-1(mod n) ，于是 n 只能为奇数。
对于第二条，设 p为 n 的一个素因子，再设 p^(t+1) 为整除 n 的最大的 p 的幂（即 p 的 t+1 次方能整除 n ，但 t+2次方不行）。取 a=p^t ，则有
最后一个式子两边约去 p^t ，得到 p^(nt-t)-1 是 p 的倍数，所以只能有 nt-t=0 ，也就是说 t=0 。这就证明了p^2 不是 n 的约数。
对于第三条，设 p为 n 的一个素因子，由于每个素数都有原根（对于大于 1 的整数 m ，若存在与 m 互素的整数 g 使得g^1,g^2,…,g^φ(m) 两两模 m 不同余，则 g 为 m的一个原根。原根的一个性质是，若它的某个非负整数次方模 m 余 1 ，则指数一定是 φ(m)的倍数。关于原根的问题下一篇文章中会详细讨论），设 p 的一个原根为 g ，并取 a=g ，则 g^n≡g(mod n)，进而有 g^n≡g(mod p) ，这样就得到 n-1 一定是 φ(p)（即 p-1 ）的倍数。
现在回到米勒-拉宾素性测试。这种测试在费马小定理的基础上做了个小改进：
验证a^(p-1)≡1(mod p) 之后，将指数 p-1 不断除以 2 ，并计算 a 的幂模 p 的余数，若某一步的余数为 1，但再下一步 后的余数不为正负 1 ，则 p 一定为合数。当指数为奇数或余数变为 -1 时结束。
实际上我们利用了一个小结论：若 x^2 模素数 p 的余数为 1 ，则 x 模素数 p 的余数为 1 或 -1 。证明很简单，因为x^2-1 是 p 的倍数，所以 x+1,x-1 必有一个是 p 的倍数（这里用到了 p 是素数），结论就出来了。
这种改进的测试虽然仍然有判断不出合数的可能性，但是我们可以证明：如果 n 为奇合数，则在 1,2,3,…,n-1 中至少有3/4 的数可以作为 n的“拉宾-米勒证据”。证明过程略。这样每次测试时只需随机选取很多个底数，就可以保证判错的可能性很低。
实际运算时我们通常倒着算，每次指数乘 2 。这样只需逐次平方。设待判断的数为 n ，则先将 n-1 不断除以 2，直到变为奇数，即 n-1=2^k*t ，然后每次在 1,2,3,…,n-1 内选取一个底数 a ，并计算 a^t(mod n)的值，若不为正负 1 则平方。如果先得到 1 （而没有经历 -1 这一步）则可以断定 n 为合数。或者平方到最后发现 a^(n-1)模 n 不等于 1 则由费马小定理也可以断定 n 是合数。
下面不妨举几个例子。
以 2 为底数测试341 时，先计算出 341-1=2^2*85 。运算过程如下：
2^85≡32(mod 341)
2^170≡1(mod 341)
于是可以断定341 不是素数。 2 就是 341 的“拉宾-米勒证据”。
以 2 为底数测试561 时，先计算出 561-1=2^4*35 。运算过程如下：
2^35≡263(mod 561)
2^70≡166(mod 561)
2^140≡67(mod 561)
2^280≡1(mod 561)
所以 561也不是素数。
为了说明问题，借用一下《数论概论》的最后一个例子，判断 172947529是不是素数（这个就是上文提到过的某个卡米歇尔数）。 先计算 172947529-1=2^3*21618441 。
接下来先取底数为17 进行测试：
17^21618441≡1(mod 172947529)
所以 17不是“拉宾-米勒证据”。再换一个底数 3 试一试：
3^21618441≡-1(mod 172947529)
所以 3也不是“拉宾-米勒证据”。再用底数 23 试一试：
23^21618441≡40063806(mod 172947529)
(23^21618441)^2≡2257065(mod 172947529)
(23^21618441)^4≡1(mod 172947529)
这时可以断定172947529 不是素数。