Miller-Rabin 学习笔记

Miller-Rabin 算法用于判断一个数是否为质数,所谓「素数测试」是也。

算法介绍及过程

费马小定理:若 pp 为质数,则有 xpx  (modp)x^p \equiv x \; (\bmod p)

由费马小定理得:

  • nn 为质数,则 xn11  (modn)x^{n - 1} \equiv 1 \; (\bmod n)
  • xn1≢1  (modn)x^{n - 1} \not \equiv 1 \; (\bmod n) ,则 nn 不是质数

如果我们多次随机 xx 进行判断,大概率地会得出正确的结果。

但是!有一种东西叫卡迈克尔(Carmichael)数

卡迈克尔数:一个数 nn 为卡迈克尔数,当且仅当对于所有与 nn 互质的数 xx 都有 xn11  (modn)x^{n - 1} \equiv 1 \; (\bmod n),且 nn 为和数。

最小的卡迈克尔数是 561561

[wiki] [OEIS:A002997]

就是这个 561561,把随机的方法卡了。。。(于是这篇博文是重写的,感谢 VW 学长)

于是我们需要一个准确的算法。

如果对于一定范围内的 aa 都有 an11  (modn)a^{n - 1} \equiv 1 \; (\bmod n) 时可以保证 nn 是质数,那就很不错了。从 wiki 上我们知道,这是对的(证明就不要管了。。。),而且对于 unsigned long long 范围内的数,只要让 aa 等于前 1212 个质数即可(来自 wiki,已验证)。

对 an−1≢1  ( mod n)a^{n - 1} \not\equiv 1 \; (\bmod n)an−1​≡1(modn) 判断的一般写法

一般不是直接计算的。。。

n1n - 1 分解为 2sd2^s ddd 为奇数),用平方差公式分解为:

an1a2sd(ad1)r=0s1(a2rd+1)  (modn)a^{n - 1} \equiv a^{2^s d} \equiv (a^d - 1) \prod_{r = 0}^{s - 1} (a^{2^r d} + 1) \; (\bmod n)

nn 是合数 \Leftrightarrow 存在 aa 使得:

  • ad≢1  (modn)a^d \not\equiv 1\; (\bmod n)
  • a2rd≢1  (modn)r[0,s1]a^{2^r d} \not\equiv -1\; (\bmod n) \qquad r \in [0, s - 1]

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
long long mul(long long a, long long b, long long mod) {
long long res = 0;
for (; b; b >>= 1, a = (a + a) % mod) if (b & 1) res = (res + a) % mod;
return res;
}
long long pow(long long a, long long n, long long mod) {
long long res = 1;
for (; n; n >>= 1, a = mul(a, a, mod)) if (n & 1) res = mul(res, a, mod);
return res;
}

bool isPrime(long long n) {
static int primes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
long long s = 0, d = n - 1;
while (d % 2 == 0) d /= 2, s++;
if (s == 0) return n == 2;
for (int i = 0; i < 12 && primes[i] < n; i++) {
long long a = primes[i];
if (pow(a, d, n) != 1) {
bool flag = true;
for (int r = 0; r < s; r++)
if (flag && pow(a, d * (1 << r), n) == n - 1) flag = false;
if (flag) return false;
}
}
return true;
}