Miller-Rabin算法详解

一、算法简介

Miller-Rabin算法是一种基于费马小定理的素性测试（Primality Test）算法，主要用于判断一个数是否为素数。算法时间复杂度为O(k*log^3(n))，其中k为测试次数，n为待测试的数。

与其它素性测试算法相比，Miller-Rabin算法不需要计算大数的因子，因此在实际应用中更加高效。同时，Miller-Rabin算法也被广泛应用于RSA算法和密码学领域中的其它问题。

二、算法思路

Miller-Rabin算法的核心思想是利用费马小定理：如果p是素数，a是p的任意正整数且a

我们可以使用上述式子来判断一个数是否为素数：首先随机选择一个小于该数的正整数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

在实际应用中，Miller-Rabin算法的测试次数通常为15~20次，可以满足绝大部分情况下的精度要求。同时，与其它素性测试算法相比，Miller-Rabin算法更为高效，因此被广泛应用于密码学领域。但需要指出的是，Miller-Rabin算法并不是完全精确的，仍然有可能出现误判的情况，因此在实际应用中需要进行综合评估和分析。