一、算法简介
Miller-Rabin算法是一种基于费马小定理的素性测试（Primality Test）算法，主要用于判断一个数是否为素数。算法时间复杂度为O(k*log^3(n))，其中k为测试次数，n为待测试的数。 与其它素性测试算法相比，Miller-Rabin算法不需要计算大数的因子，因此在实际应用中更加高效。同时，Miller-Rabin算法也被广泛应用于RSA算法和密码学领域中的其它问题。
二、算法思路
Miller-Rabin算法的核心思想是利用费马小定理：如果p是素数，a是p的任意正整数且a < p，则a^(p-1) mod p ≡ 1。 我们可以使用上述式子来判断一个数是否为素数：首先随机选择一个小于该数的正整数a，将a^(n-1) mod n计算出来，若该值不等于1，则说明n为合数；反之，则继续进行下一轮测试。若经过多轮测试，n仍然没有被认定为合数，则说明n很可能是素数。
三、算法实现
在实现Miller-Rabin算法时，主要包括两个步骤：随机选择值a和测试n是否为素数。
// 随机选择a
int rand_a(int n) {
return rand() % (n - 2) + 2;
}
// 计算x的k次幂，并取模运算
int pow_mod(int x, int k, int p) {
int ans = 1;
while (k) {
if (k & 1)
ans = ans * x % p;
x = x * x % p;
k >>= 1;
}
return ans;
}
// Miller-Rabin算法
bool is_prime(int n, int test_cnt) {
if (n < 2)
return false;
if (n == 2)
return true;
if (n % 2 == 0)
return false;
int m = n - 1;
int k = 0;
while (m % 2 == 0) {
m >>= 1;
k++;
}
for (int i = 0; i < test_cnt; i++) {
int a = rand_a(n);
int x = pow_mod(a, m, n);
if (x == 1)
continue;
for (int j = 0; j < k; j++) {
if (x == n - 1)
break;
x = pow_mod(x, 2, n);
}
if (x != n - 1)
return false;
}
return true;
}
四、算法分析
Miller-Rabin算法的正确性是基于费马小定理，即如果n为素数，则对于任意的a (1 < a < n)，都有a^(n-1) mod n = 1，而对于合数可能仅在a^(n-1) mod n ≠ 1时被检测出来（发生概率极小），因此在测试次数足够多的情况下，Miller-Rabin算法的错误率可以被控制在极小范围内。 在实际应用中，Miller-Rabin算法的测试次数通常为15~20次，可以满足绝大部分情况下的精度要求。同时，与其它素性测试算法相比，Miller-Rabin算法更为高效，因此被广泛应用于密码学领域。但需要指出的是，Miller-Rabin算法并不是完全精确的，仍然有可能出现误判的情况，因此在实际应用中需要进行综合评估和分析。
