1.编写程序实现RSA算法 2.由键盘输入p、q、随机数e及明文m 3.输出私钥d、加密后的密文，解密后的明文 1.判断素数代码

在编写程序实现RSA（Rivest-Shamir-Adleman）算法之前，我们首先需要创建一些辅助功能，如生成大素数、检测素数以及计算模逆等。以下是基础步骤：

1. **生成大素数**：
使用随机数生成器生成足够大的数字，并通过质数测试（例如Miller-Rabin测试）来确认它是否是素数。

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

bool is_prime(int n, int k) { /* 使用 Miller-Rabin 测试 */
    if (n <= 1 || n == 4)
        return false;

    // 处理特殊情况
    if (n % 2 == 0)
        return n == 2;

    for (int i = 0; i < k; ++i) {
        int a = rand() % (n - 3) + 2;  // 随机选取 [2, n-2]
        int x = pow(a, n - 1) % n;
        if (x != 1 && x != n - 1)
            while (x != n - 1)
                x = (x * x) % n;
        if (x != n - 1)
            return false;
    }

    return true;
}

int generate_large_prime(int min_size) {
    srand(time(NULL));
    while (true) {
        int candidate = rand() % (min_size * 10) + min_size;
        if (is_prime(candidate))
            return candidate;
    }
}

2. **生成公钥和私钥**：
根据用户输入的两个大素数p和q，计算n=p*q，然后选择一个公共指数e（通常取一个大于1且与(p-1)*(q-1)互质的数）。接着找到e关于模(n-1)的逆元d作为私钥。

void generate_keys(int p, int q) {
    int n = p * q;
    int phi_n = (p - 1) * (q - 1);
    int e = 65537;  // 常见的公共指数

    int d;
    if (!find_mod_inv(e, phi_n, &d)) {
        printf("无法找到模逆数，退出。\n");
        return;
    }

    printf("Public Key (n, e): (%d, %d)\n", n, e);
    printf("Private Key (n, d): (%d, %d)\n", n, d);
}

3. **加密和解密**：
使用欧拉定理（a^(phi(n)) ≡ 1 (mod n)），加密过程是 m^e mod n，解密则是 c^d mod n，其中m是明文，c是密文。

int encrypt(int message, int public_key_e, int modulus_n) {
    return pow(message, public_key_e) % modulus_n;
}

int decrypt(int ciphertext, int private_key_d, int modulus_n) {
    return pow(ciphertext, private_key_d) % modulus_n;
}

**完整代码示例**：

#include <stdio.h>

// ... 其他素数相关和加密函数

int main() {
    int p, q;
    printf("Enter two distinct prime numbers (p and q): ");
    scanf("%d %d", &p, &q);

    // ... 判断素数和生成大素数代码 ...

    int e;
    printf("Enter an encryption exponent e: ");
    scanf("%d", &e);

    generate_keys(p, q);
    int message;
    printf("Enter the plaintext message (m): ");
    scanf("%d", &message);

    int encrypted = encrypt(message, e, p * q);
    printf("Encrypted message (c): %d\n", encrypted);

    int decrypted = decrypt(encrypted, d, p * q);
    printf("Decrypted message (m'): %d\n", decrypted);

    return 0;
}