费马小定理

p p p 为质数, a a a 为任意自然数, 则
a p ≡ a ( m o d p )       a p − 1 ≡ 1 ( m o d p ) a^{p} \equiv a\pmod p \iff a^{p-1} \equiv 1 \pmod p ap≡a(modp)ap−1≡1(modp)

证明略。

二次探测定理

p p p 为质数，则 x 2 ≡ 1 ( m o d p ) x^2 \equiv 1 \pmod p x2≡1(modp) 的解为 x 1 = 1 , x 2 = p − 1 x_1 = 1, x_2 = p-1 x1​=1,x2​=p−1。

略证：

x 2 ≡ 1 ( m o d p ) x 2 − 1 ≡ 0 ( m o d p ) ( x + 1 ) ( x − 1 ) ≡ 0 ( m o d p ) p ∣ ( x − 1 ) × ( x + 1 ) x^2 \equiv 1 \pmod p \\ x^2 - 1 \equiv 0 \pmod p \\ (x +1)(x-1) \equiv 0 \pmod p \\ p | (x - 1)\times (x+1) x2≡1(modp)x2−1≡0(modp)(x+1)(x−1)≡0(modp)p∣(x−1)×(x+1)

Miller-Rabin

我们都知道，如果 p p p 为质数那么有 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p ap−1≡1(modp)。但反命题不一定成立，比如令 a = 2 a=2 a=2，那么有 2 340   m o d   341 = 1 2^{340} \bmod 341 = 1 2340mod341=1，但是 341 = 11 × 31 341 = 11 \times 31 341=11×31。那么再试一下 a = 3 a=3 a=3，发现 3 340   m o d   341 = 56 3^{340} \bmod 341 = 56 3340mod341=56，所以 341 341 341 不是质数。

那么能不能多选几个质数去做检测呢？但是有一些合数，叫做 Carmichael 数，比如 561 = 3 × 11 × 17 561 = 3\times11 \times17 561=3×11×17，所有合法的底数都无法将它检测出来。

那么接下来就是正题了——Miller-Rabin 素性测试算法。先拿 341 341 341 举个栗子，看看这个算法在干什么。

先说明一个显而易见的命题，对于任意质数 p p p 有 2 ∣ p − 1 2| p -1 2∣p−1。那么看看 Miller-Rabin 干了什么。

因为 2 340 ≡ 1 ( m o d 341 ) 2^{340} \equiv 1 \pmod {341} 2340≡1(mod341)，那么有 2 170 2 ≡ 1 ( m o d 341 ) 2^{{170}^2} \equiv 1 \pmod {341} 21702≡1(mod341)，若将 2 170 2^{170} 2170 看作一个整体，根据二次探测定理，如果 341 341 341 是一个质数，那么 2 170   m o d   341 = 1 / 340 2^{170} \bmod 341 = 1 / 340 2170mod341=1/340。可以发现 2 170   m o d   341 2^{170} \bmod 341 2170mod341 为 1 1 1。那么还适用二次探测定理，再看看 2 85   m o d   341 2^{85} \bmod 341 285mod341，发现它为 32 32 32，所以 341 341 341 不是质数。

int ksm(int a, int k, int p) {
  	int res = 1;
  	while (k) {
    	if (k & 1) res = res * a % p;
    	a = a * a % p;
    	k >>= 1;
  	}
  	return res % p;
}
int MR(int x, int p) {
	if (ksm(x, p-1, p) != 1) return 0;
	int k = p - 1;
	while (!k & 1) {
		k >>= 1;
		int t = ksm(x, k, p);
		if (t == p - 1) return 1;
		if (t != 1) return 0;
	}
	return 1;
}
int RP(int p) {
	if (p == 2 || p == 3 || p == 5 || p == 7 || p == 11) return 1;
	if (p == 0) return 0;
	return MR(2, p) && MR(3, p) && MR(5, p) && MR(7, p) && MR(11, p);
}
int main() {
	while (1) {
		int x = read();
		printf("%d\n", RP(x));
	}
	return 0;
}

可以发现 Miller-Rabin 的时间按复杂度为 O ( k log ⁡ 2 n ) O(k \log^2 n) O(klog2n)，其中 k k k 为测试次数，通常五次就够了。