solovary-stassen素性检验算法C语言

Solovay-Strassen 素性检验算法是一种随机化的素性检验算法，它基于欧拉判别准则和Jacobi符号的性质，可以用来判断一个数是否为素数。

以下是使用 Solovay-Strassen 素性检验算法判断一个数是否为素数的 C 语言代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <math.h>

// 计算 a^b mod m 的值
long long pow_mod(long long a, long long b, long long m) {
    long long ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

// 计算 Jacobi 符号 (a/n) 的值
int jacobi(long long a, long long n) {
    int ans = 1;
    while (a) {
        long long t = 0;
        while (!(a & 1)) {
            a >>= 1;
            ++t;
        }
        if (t & 1 && (n % 8 == 3 || n % 8 == 5)) {
            ans = -ans;
        }
        if (a % 4 == 3 && n % 4 == 3) {
            ans = -ans;
        }
        long long tmp = a;
        a = n % a;
        n = tmp;
    }
    if (n == 1) {
        return ans;
    }
    else {
        return 0;
    }
}

// Solovay-Strassen 素性检验算法
bool solovay_strassen_test(long long n, int k) {
    if (n == 2) {
        return true;
    }
    if (n < 2 || !(n & 1)) {
        return false;
    }
    srand(time(NULL));
    for (int i = 0; i < k; ++i) {
        long long a = rand() % (n - 2) + 2; // 随机选取 a，2 <= a <= n-1
        int j = jacobi(a, n);
        if (j == 0 || pow_mod(a, (n - 1) / 2, n) != j % n) {
            return false;
        }
    }
    return true;
}

int main() {
    long long n;
    int k;
    printf("请输入要测试的正整数：");
    scanf("%lld", &n);
    printf("请输入重复测试的次数：");
    scanf("%d", &k);
    if (solovay_strassen_test(n, k)) {
        printf("%lld 是素数。\n", n);
    } else {
        printf("%lld 不是素数。\n", n);
    }
    return 0;
}

该程序先定义了一个用于计算 a^b mod m 的函数 pow_mod 和一个用于计算 Jacobi 符号 (a/n) 的值的函数 jacobi。接着定义了 Solovay-Strassen 素性检验算法的函数 solovay_strassen_test，该函数使用随机化的方法选取 k 个整数进行测试，如果都通过测试，则认为 n 可能是素数，否则认为 n 不是素数。最后在主函数中读入要测试的正整数和重复测试的次数，调用 solovay_strassen_test 函数进行测试，输出测试结果。