Prime Number

费马小定理： 如果 $p$ 是素数， $a$ 是整数，则 $a^p-a$ 是 $p$ 的倍数。 这个定理可表示为： $$a^p-a\equiv 0(\mathrm{mod}p)$$ 或者表示为： $$a^p\equiv a(\mathrm{mod}p)$$ 比如， $a=2,p=7$ ，则 $a^p-a=2^7-2=126=7\times 18$ ，显然 $126$ 是 $7$ 的倍数。又如， $a=14,p=7$ ，则 $a^p-a={14}^7-14=105413490=7\times 15059070$ ，显然 $105413490$ 是 $7$ 的倍数。

需要说明的是： 费马小定理的逆叙述是不成立的，即假设 $a^p-a$ 是 $p$ 的倍数， $p$ 不一定是素数。 比如， $2^{341}-2$ 是 $341$ 的倍数，但 $341=11\times 31$ ，显然不是素数。

对于素数 $p$ ，如果 $a$ 不是 $p$ 的倍数（注：由于 $p$ 本身就是素数，这相当于说 $a$ 和 $p$ 互素，即满足 $gcd(a,p)=1$ ），则下式一定成立： $$a^{p-1}\equiv 1(\mathrm{mod}p)$$ 这是费马小定理另一种表述。比如， $a=2,p=7$ ，它们显然满足 $gcd(a,p)=1$ ，计算上面式子的左边 $a^{p-1}=2^{7-1}=64=7\times 9+1$ ，显然它除以素数 $p$ 确实余 $1$ 。又比如， $a=3,p=7$ ，它们显然满足 $gcd(a,p)=1$ ，计算上面式子的左边 $a^{p-1}=3^{7-1}=729=7\times 104+1$ ，显然它除以素数 $p$ 确实余 $1$ 。只要 $a$ 不是素数 $p$ 的倍数，上式都会成立。

利用费马小定理可以检验一个数 $n$ 是否是素数，算法如下：

1. 在范围 $[1,n-1]$ 中随机选择 $a$ ，这显然会满足费马小定理另一种表述的要求 $gcd(a,n)=1$ ；
   
2. 测试 $a^{n-1}\equiv 1(\mathrm{mod}n)$ 是否成立；
   
   • 如果不成立，则 $n$ 一定不是素数，即 $n$ 是合数；
     
   • 如果成立，则 $n$ 可能是素数（不能直接确定 $n$ 就是素数，因为费马小定理的逆叙述是不成立的）。
     

如果重复运行上面算法 $k$ 次，每次的结果都是 $n$ 可能是素数，则我们认为 $n$ 极有可能是素数，称为 Probably Prime。

注：很多资料会把 $a$ 的选择范围调整为 $[2,n-2]$ ，这是因为 $a=1$ 或者 $a=n-1$ 时，不管等待测试的数 $n$ 是合数还是素数，费马素性测试一定都会通过。所以，没有必要选择 $a=1$ 或者 $a=n-1$ 进行费马素性测试。

一般来说，增加测试次数 $k$ ，可以提高费马素性测试算法的正确率。但是，也有一些数可以通过任意次数的费马素性测试，但它却不是素数。

比如， $561=3\times 11\times 17$ 不是素数，但不管随机选择的 $a$ 是什么数，它都可以通过费马素性测试，这类数被称为卡迈克尔数（Carmichael Number），也称为“费马伪素数”。 由于 Carmichael Number 的存在，我们在应用时不能只采用费马素性测试算法来判断某个数是否是素数。

Miller-Rabin 测试算法的伪代码如下：

Input #1: n > 2, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: "composite" if n is found to be composite, "probably prime" otherwise

let s > 0 and d odd > 0 such that n − 1 = 2^s * d  # by factoring out powers of 2 from n − 1
repeat k times:
    a ← random(2, n − 2)
    t ← a^d mod n
    if t = 1 then
        return "probably prime"
    repeat s times:
        if t = n - 1 then
            return "probably prime"
        t ← t^2 mod n
    return "composite"

假设 $n=221$ ，我们对它进行 Miller-Rabin 测试。

1. 首先，我们把 $n-1$ 写为 $2^s\cdot d$ 的形式，有 $220=2^2\times 55$ ，所以 $s=2,d=55$ 。
   
2. 随机选择 $a=174$ ，我们计算：
   
   • $a^{d}modn={174}^{55}mod221=47$ ，它不等于 $1$ ，也不等于 $n-1$ ；
     
   • $a^{2^{1}d}modn={174}^{110}mod221=220$ ，它等于 $n-1$ 。
     
3. 我们发现上面的 3 个检测（第 1 个式子要和 $1,n-1$ 两个数进行相等比较，后续式子只用和 $n-1$ 进行相等比较），有一个成立，所以 $221$ 暂时通过了一轮的 Miller-Rabin 测试；
   
4. 再随机选择另一个 $a$ ，比如 $a=137$ ，我们计算：
   
   • $a^{d}modn={137}^{55}mod221=188$ ，它不等于 $1$ ，也不等于 $n-1$ ；
     
   • $a^{2^{1}d}modn={137}^{110}mod221=205$ ，它不等于 $n-1$ 。
     
5. 我们发现当 $a=137$ 时，上面的 3 个检测一个也不成立。所以，我们得到结论： $n=221$ 不是素数，事实上 $221=13\times 17$ 。