Euclid’s lemma
若素数$p$为$ab$的约数，那么$p$至少是$a$，$b$这两个数中的一个数的约数。也就是说，$p\mid ab,p\not\mid a \Rightarrow p\mid b$。
它还有一个推广：
如果$n$为$ab$的约数，并且$n$与$a$互质，那么$n\mid b$。
一种证明的方法，是用Bézout’s lemma，即，若$x \bot y$，那么一定存在整数$r$，$s$，使得$rx + sy = 1$成立。
那么倘若$a\bot n$（如果$n$是质数，这等价于$n\not\mid a$），那么一定存在这样的$s$，$r$，使得$sa+rn = 1$。
等式两边同时乘$b$，得到$sab + rnb = b$。由于$n\mid ab$，所以$n\mid sab+rnb$，而等式左右两边相等，所以$n\mid b$。定理得证。
二次探测定理
对于方程$x^2 \equiv 1 \mod p$，显然无论$p$取何值，这个方程一定有两个解，分别为$1$和$-1$。我们称$\pm 1$为$1$的平凡平方根（trivial square roots）。二次探测定理就是说，对于素数$p$，在模$p$的意义下不存在$1$的非平凡平方根。即，若$p$是素数，那么有$x^2 \equiv 1 \mod p \Rightarrow x\equiv 1 \text{ or } x\equiv -1 \mod p$。反之，倘若存在一个$x\not\equiv \pm 1 \mod p$并且$x^2 \equiv 1 \mod p$，那么$p$就不是素数。
证明如下：$x^2 \equiv 1 \mod p$，移项可以得到$x^2 -1 \equiv 0 \mod p$，也就是$(x-1)(x+1) \equiv 0\mod p$。换言之，$p\mid (x-1)(x+1)$。
由前面的Euclid’s lemma得到，$p\mid (x-1)$和$p\mid (x+1)$这两个式子中至少有一个成立。如果第一个成立的话，$x-1\equiv 0 \mod p \Rightarrow x\equiv 1\mod p$，而如果第二个成立，则$x+1\equiv 0\mod p \Rightarrow x\equiv -1 \mod p$。
综上，对于任意素数$p$，在模$p$的意义下不存在$1$的非平凡平方根。
Miller-Rabin primality test
这个算法就是基于前面的二次探测定理和费马小定理工作的。
过程如下：假设我们要检测的数为$p$。我们选取一个底数$a$，首先判断$a^{p-1}\equiv 1\mod p$是否成立，如果不成立直接返回false。否则，我们把$n-1$表示成$2^s\cdot d$的形式，其中$d$为奇数。如果$a^d\not \equiv 1$并且$[0,s)$中不存在$r$，使得$a^{d\cdot 2^r}\equiv -1 \mod p$成立，那么$p$一定不是质数。此时我们称$a$是$p$的一个 witness；否则，我们称$a$是$p$的一个 strong liar ，$p$是$a$的一个 strong probable prime。
也可以这样描述：选取底数$a$，首先判断$a^{p-1}\equiv 1\mod p$是否成立，不成立返回false。然后我们令$b=p-1$，我们判断$a^{b\over 2}\equiv \pm 1 \mod p$是否成立，不成立返回false。然后看此时的$a^{b\over 2}$，如果为$-1$就返回true（因为检查是否存在$-1$的非平凡平方根是没有意义的qwq），否则就继续检测$a^{b\over 4}\equiv \pm 1 \mod p$是否成立……
据说这样做，选择$k$个数作为底数，出错的概率是$4^{-k}$。
关于底数的选取：最好选择质数。如果选择$2,3,7,61,24251$，那么$10^{16}$以内唯一的强伪素数就是46856248255981。不过很多时候随机就已经够了。
模板
1 | // Miller-Rabin primality test |
这里有生成64位随机数的代码：
1 | ull Rand() |