求一个数模逆元的c++代码

以下是求一个数的模逆元的C++代码：

#include <iostream>
using namespace std;

int modInverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1) return 0;

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0) x1 += m0;

    return x1;
}

int main() {
    int a = 5, m = 7;
    cout << "The modulo inverse of " << a << " under " << m << " is " << modInverse(a, m) << endl;
    return 0;
}

输出结果为：

The modulo inverse of 5 under 7 is 3

其中，`modInverse(a, m)` 函数用于计算 a 在模 m 意义下的逆元。

相关问题

用c++写一个用辗转相除法求任意数的模乘逆元的代码

以下是用辗转相除法求任意数的模乘逆元的C代码：

#include <stdio.h>

int extended_gcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }

    int r = extended_gcd(b, a % b, y, x);
    *y -= (a / b) * (*x);

    return r;
}

int mod_inverse(int a, int m) {
    int x, y;
    int gcd = extended_gcd(a, m, &x, &y);

    if (gcd != 1) {
        printf("The inverse of %d does not exist modulo %d.\n", a, m);
        return -1;
    } else {
        return (x % m + m) % m;
    }
}

int main() {
    int a, m;
    printf("Enter a and m (separated by a space): ");
    scanf("%d %d", &a, &m);

    int inv = mod_inverse(a, m);
    if (inv != -1) {
        printf("The inverse of %d modulo %d is %d.\n", a, m, inv);
    }

    return 0;
}

该程序中的 `extended_gcd` 函数实现了扩展欧几里得算法，用于计算最大公约数和模乘逆元。 `mod_inverse` 函数则利用 `extended_gcd` 函数求出模乘逆元（如果存在）并返回。在主函数中，程序要求用户输入要求模乘逆元的数和模数，并输出计算结果。

RSA算法c++代码

RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，用于数据加密和数字签名。以下是RSA算法的一个简单C++代码示例，它包含了密钥生成、加密和解密的基本步骤。请注意，这只是一个基础版本，实际应用中需要更完善的错误处理和安全性考虑：

#include <iostream>
#include <string>

// 导入模数和欧拉函数计算
long long modpow(long long base, long long exp, long long modulus) {
    if (exp == 0)
        return 1;
    else if (exp % 2 == 0)
        return modpow(base * base % modulus, exp / 2, modulus);
    else
        return base * modpow(base, exp - 1, modulus) % modulus;
}

// 计算欧拉函数phi(n)
long long phi(long long n) {
    long long result = n;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}

// RSA密钥生成
void generateKeys(int p, int q) {
    // p*q是模数n
    long long n = p * q;
    
    // 欧拉函数phi(n)
    long long phi_n = phi(n);
    
    // 选择e，满足gcd(e,phi(n))=1
    int e = 65537;
    long long gcd = __gcd(e, phi_n);
    while (gcd != 1) {
        e++;
        gcd = __gcd(e, phi_n);
    }
    
    // 计算d，d是e关于模phi(n)的逆元
    long long d = modinv(e, phi_n);

    std::cout << "Public Key (e, n): (" << e << ", " << n << ")\n";
    std::cout << "Private Key (d, n): (" << d << ", " << n << ")\n";
}

// 明文加密
std::string encrypt(std::string message, int e, long long n) {
    std::string encrypted = "";
    for (char c : message) {
        encrypted += static_cast<char>((static_cast<int>(c) + e) % n);
    }
    return encrypted;
}

// 明文解密
std::string decrypt(std::string cipher, int d, long long n) {
    std::string decrypted = "";
    for (char c : cipher) {
        decrypted += static_cast<char>((static_cast<int>(c) - d) % n);
    }
    return decrypted;
}

int main() {
    int p = 61, q = 53; // 这里只是示例，实际使用时应从足够大的素数开始
    generateKeys(p, q);
    std::string plaintext = "Hello, RSA!";
    std::string ciphertext = encrypt(plaintext, 5, p * q);
    std::cout << "Ciphertext: " << ciphertext << "\n";
    std::string decryptedtext = decrypt(ciphertext, 13, p * q); // 使用私钥d解密
    std::cout << "Decrypted text: " << decryptedtext << "\n";

    return 0;
}