用处

在比较短的时间内快速地以较高的可信度判断一个整数是否为质数。

说明

将方程 x^2 \equiv 1 \pmod p 的解称作 1 \pmod p 的平方根。其中与 1 或 -1 对 p 同余的被称作平凡平方根。其它的称作非平凡平方根。

可以证明，对于一个大于 2 的质数来说，不存在 1 \pmod p 的非平凡平方根。

如果存在，假设 x 是非平凡平方根之一，有 (x+1)(x-1)\equiv 0 \pmod p 。即 x \equiv 1 \pmod p 或 x \equiv -1 \pmod p 。x是平凡的平方根。

---

假设 n 是一个大于 2 的质数。有 n-1 是偶数，可以表示为 n-1=2^s*d 的形式。其中 s 和 d 都是整数，且 d 为奇数。

那么，根据费马小定理，对于任何与 n 互质的整数 a 有 \large a^{2^s*d}\equiv 1 \pmod p

如果对 \large a^{2^s*d} 开平方，应当仍然模 p 余 1 或 -1 。

那么，必然存在两种情况之一。

1. 存在一个 r\in [0,s-1] 满足 \large a^{2^{r}* d}\equiv -1 \pmod p，且 \forall i \in [r+1,s] , a^{2^{i}*d}\equiv 1 \pmod p

2. 或 \forall i \in [0,s] , a^{2^{i}*d}\equiv 1 \pmod p

那么，我们倒过来考虑，对于一个待判断的数字 n ,选取一个与 n 互质的整数 a（可以直接选质数）。

如果发现

有 a^{2^{s}*d}\not\equiv 1 \pmod{p} 即违背费马小定理

或 \forall i \in [0,s-1] , a^{2^{i}*d} \not\equiv -1 \pmod{p} 即违背二次探测原理

那就非常有把握 n 不是一个质数。但是反过来，就没有那么确定了。经验法则告诉我们，这个时候大概只有 \frac{3}{4} 的把握确定 n 是质数。

可以多选几个 a 就有把握了。

同时，经过计算可以得知，如果要百分之百确定小于 2^{32} 的数，可以选择 2,7,63 这三个数进行检查。