c语言生成随机大素数

要在C语言中生成随机大素数，可以使用以下算法：

1. 随机生成一个大奇数n。
2. 判断n是否为素数，如果是则返回n，否则转到步骤1。
3. 判断n是否为合数，如果是则将n加2，再转到步骤2。

下面是一个示例代码：

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

int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    srand(time(0)); // 初始化随机数种子
    int n = rand() % 10000 + 10000; // 生成10000到19999之间的随机数
    while (1) {
        if (is_prime(n)) {
            printf("%d\n", n);
            break;
        }
        n += 2; // 增加2
    }
    return 0;
}

这个代码会生成一个10000到19999之间的随机数n，然后不断增加2，直到找到一个素数为止。注意，这个算法并不能保证生成的是100%的大素数，但是对于常见的应用场景已经足够了。如果需要更高的安全性，可以使用更加复杂的算法。

相关问题

c语言生成128bit的素数

生成128位素数的一种常见方法是使用Miller-Rabin素性测试。以下是一个示例程序：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

#define MAX_ITERATIONS 64

// 128位正整数结构体
typedef struct {
    uint64_t high;
    uint64_t low;
} uint128_t;

// 将字符串转换为128位正整数
void str_to_uint128(char* str, uint128_t* num) {
    int len = strlen(str);
    num->high = 0;
    num->low = 0;
    for (int i = 0; i < len; i++) {
        num->low = num->low * 10 + (str[i] - '0');
        num->high += num->low / 10000000000000000000ULL;
        num->low %= 10000000000000000000ULL;
    }
}

// 将128位正整数转换为字符串
void uint128_to_str(uint128_t num, char* str) {
    uint64_t tmp;
    int len = 0;
    while (num.high > 0) {
        tmp = num.high % 10;
        str[len++] = '0' + tmp;
        num.high /= 10;
    }
    while (num.low > 0) {
        tmp = num.low % 10;
        str[len++] = '0' + tmp;
        num.low /= 10;
    }
    if (len == 0) {
        str[len++] = '0';
    }
    str[len] = '\0';
    for (int i = 0; i < len / 2; i++) {
        char tmp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = tmp;
    }
}

// 128位正整数加法
uint128_t uint128_add(uint128_t a, uint128_t b) {
    uint128_t res;
    res.high = a.high + b.high;
    res.low = a.low + b.low;
    if (res.low < a.low) {
        res.high++;
    }
    return res;
}

// 128位正整数减法
uint128_t uint128_sub(uint128_t a, uint128_t b) {
    uint128_t res;
    res.high = a.high - b.high;
    res.low = a.low - b.low;
    if (res.low > a.low) {
        res.high--;
    }
    return res;
}

// 128位正整数乘法
uint128_t uint128_mul(uint128_t a, uint128_t b) {
    uint128_t res;
    uint64_t a_high = a.high;
    uint64_t a_low = a.low;
    uint64_t b_high = b.high;
    uint64_t b_low = b.low;
    res.low = a_low * b_low;
    res.high = a_high * b_low + a_low * b_high + (res.low / 10000000000000000000ULL);
    res.low %= 10000000000000000000ULL;
    res.high += a_high * b_high;
    return res;
}

// 128位正整数除以2
uint128_t uint128_div2(uint128_t a) {
    uint128_t res;
    res.high = a.high >> 1;
    res.low = (a.high & 1) * 1000000000000000000ULL + (a.low >> 1);
    return res;
}

// 128位正整数取模
uint128_t uint128_mod(uint128_t a, uint128_t b) {
    while (a.high > 0 || a.low >= b.low) {
        if (a.high < b.high || (a.high == b.high && a.low < b.low)) {
            break;
        }
        uint128_t tmp = b;
        uint128_t mul = { 1, 0 };
        while (tmp.high < a.high || (tmp.high == a.high && tmp.low <= a.low)) {
            tmp = uint128_add(tmp, tmp);
            mul = uint128_add(mul, mul);
        }
        a = uint128_sub(a, tmp);
        b = uint128_sub(b, mul);
    }
    return a;
}

// 128位正整数幂取模
uint128_t uint128_powmod(uint128_t a, uint128_t b, uint128_t mod) {
    uint128_t res = { 1, 0 };
    while (b.high > 0 || b.low > 0) {
        if (b.low & 1) {
            res = uint128_mod(uint128_mul(res, a), mod);
        }
        a = uint128_mod(uint128_mul(a, a), mod);
        b = uint128_div2(b);
    }
    return res;
}

// Miller-Rabin素性测试
bool miller_rabin_test(uint128_t n) {
    if (n.high == 0 && n.low < 2) {
        return false;
    }
    if (n.low == 2) {
        return true;
    }
    if ((n.low & 1) == 0) {
        return false;
    }
    uint128_t d = uint128_sub(n, (uint128_t){ 1, 0 });
    while ((d.low & 1) == 0) {
        d = uint128_div2(d);
    }
    for (int i = 0; i < MAX_ITERATIONS; i++) {
        uint128_t a;
        do {
            a.high = rand() | ((uint64_t)rand() << 32);
            a.low = rand() | ((uint64_t)rand() << 32);
        } while (a.high == 0 && a.low == 0);
        uint128_t x = uint128_powmod(a, d, n);
        if (x.high == 0 && x.low == 1) {
            continue;
        }
        bool probable_prime = false;
        while (d.high > 0 || d.low > 0) {
            x = uint128_mod(uint128_mul(x, x), n);
            d = uint128_div2(d);
            if (x.high == 0 && x.low == 1) {
                probable_prime = true;
                break;
            }
            if (x.high == 0 && x.low == n.low - 1) {
                probable_prime = true;
                break;
            }
        }
        if (!probable_prime) {
            return false;
        }
    }
    return true;
}

// 生成随机128位正整数
void random_uint128(uint128_t* num) {
    num->high = rand() | ((uint64_t)rand() << 32);
    num->low = rand() | ((uint64_t)rand() << 32);
}

// 生成128位素数
void generate_prime(uint128_t* num) {
    do {
        random_uint128(num);
        num->low |= 1;
    } while (!miller_rabin_test(*num));
}

int main() {
    srand((unsigned)time(NULL));
    uint128_t num;
    generate_prime(&num);
    char str[40];
    uint128_to_str(num, str);
    printf("%s\n", str);
    return 0;
}

注意：此程序仅供参考，实际应用中应该考虑更多的安全性和效率问题。

c语言生成大素数

生成大素数的一种常见方法是使用 Miller-Rabin 素性测试。其基本思想是利用费马小定理，用随机数进行多次检验，判断一个数是否为素数。

以下是使用 C 语言实现 Miller-Rabin 素性测试的示例代码：

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

bool miller_rabin(int n, int k)
{
    // 如果 n 是偶数，则不可能为素数
    if (n % 2 == 0) {
        return false;
    }

    // 将 n - 1 表示成 2^s * d 的形式
    int s = 0, d = n - 1;
    while (d % 2 == 0) {
        s++;
        d /= 2;
    }

    // 进行 k 次检验
    for (int i = 0; i < k; i++) {
        int a = rand() % (n - 2) + 2; // 随机选取 a，a ∈ [2, n-2]
        int x = pow(a, d) % n;

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

        for (int j = 1; j < s; j++) {
            x = (x * x) % n;
            if (x == n - 1) {
                break;
            }
            if (j == s - 1) {
                return false;
            }
        }
    }

    return true;
}

int main()
{
    srand(time(0));
    int n;
    printf("请输入一个大于 2 的整数：");
    scanf("%d", &n);

    while (!miller_rabin(n, 10)) {
        n++;
    }

    printf("生成的大素数为：%d\n", n);

    return 0;
}

其中，`miller_rabin` 函数用于进行 Miller-Rabin 素性检验，`k` 表示检验次数。在主函数中，输入一个大于 2 的整数 `n`，然后调用 `miller_rabin` 函数进行检验，如果不是素数，则将 `n` 加 1 继续检验，直到生成一个素数。这个例子中，我们只生成了一个大素数，实际应用中需要生成多个素数，并使用更加严谨的方法进行检验。