miller-rabin素性测试算法C语言

Miller-Rabin素性测试是一种概率型算法，用于判断一个大数是否可能是质数。它基于费马小定理，利用随机化的方式减少计算量。以下是基本的C语言实现流程：

1. **选择基**：通常选取小于n的较小整数a作为测试基数。

2. **计算模幂**：将n-1表示为2^r * d，其中d为奇数。然后计算a^d mod n。

3. **循环检验**：如果a^d == 1 或者 a^(2^i * d) == -1 (mod n)，那么n可能是质数。否则进入下一个步骤。

4. **强检查**：对于那些不符合条件的a，继续计算a^(2^(r-1) * d) mod n，直到找到一个满足条件或确定n不是质数。

5. **重复试验**：为了提高可靠性，可以对n进行多次独立的Miller-Rabin测试，如果所有试验都通过，则n被认为是“很可能”是质数。

#include <stdio.h>
#include <math.h>

int power(int a, int n, int p) {
    int res = 1;
    while (n > 0) {
        if (n % 2)
            res = (res * a) % p;
        a = (a * a) % p;
        n /= 2;
    }
    return res;
}

int Miller_Rabin(int n, int k) {
    if (n <= 1 || n == 4) return 0; // 特殊情况
    if (n <= 3) return 1; // 小于等于3的都是质数

    int d = n - 1, s = 0;
    while (!(d % 2)) { // 把d分解为2^s * d'
        d /= 2;
        ++s;
    }

    for (int i = 0; i < k; ++i) {
        int a = rand() % (n - 1) + 1; // 随机选取测试基数
        int x = power(a, d, n);

        if (x == 1 || x == n - 1)
            continue;

        bool isPrime = true;
        for (int j = 1; j < s && isPrime; ++j) {
            x = power(x, 2, n);
            if (x == n - 1)
                break;
        }

        if (x != n - 1)
            isPrime = false;
    }

    return isPrime ? 1 : 0;
}

int main() {
    int n = ... // 待检测的大数
    int k = 5; // 进行k次测试
    int result = Miller_Rabin(n, k);
    if (result)
        printf("%d 可能是质数\n", n);
    else
        printf("%d 可能不是质数\n", n);
    return 0;
}