c++ 1~p-1的逆元

如果p是一个质数，那么可以使用费马小定理求解1~p-1的逆元。费马小定理是指如果p是一个质数，a是一个整数，那么a^(p-1) mod p = 1。因此，对于a，a^(p-2) mod p就是a的逆元。

以下是使用费马小定理求解1~p-1的逆元的C++代码：

#include <iostream>
using namespace std;

int pow(int a, int b, int p) {
    int ans = 1 % p;
    for (; b; b >>= 1) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
    }
    return ans;
}

int inv(int a, int p) {
    return pow(a, p - 2, p);
}

int main() {
    int p = 1000000007;
    for (int i = 1; i < p; ++i) {
        cout << i << " 的逆元是 " << inv(i, p) << endl;
    }
    return 0;
}

在这个例子中，我们使用了快速幂来计算a的乘方，然后将其除以p并取模。我们使用inv函数来计算a的逆元，该函数使用费马小定理计算a^(p-2) mod p。在主函数中，我们循环计算1~p-1的逆元，其中p是一个质数。

相关问题

辗转相除法求模乘逆元的c++代码

辗转相除法求模乘逆元的 C 代码如下：

#include <stdio.h>
int extgcd(int a, int b, int &x, int &y)
{
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}
int mod_inverse(int a, int m)
{
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}
int main()
{
    int a = 3, m = 11;
    printf("%d 的模 %d 乘逆元为 %d\n", a, m, mod_inverse(a, m));
    return 0;
}

以上代码使用了扩展欧几里得算法求解模乘逆元。其中，`extgcd` 函数可以求解任意两个整数的最大公约数，并返回其值，同时通过引用返回参数 `x` 和 `y` 的值，满足 $ax + by = \gcd(a, b)$。`mod_inverse` 函数则使用 `extgcd` 求解模乘逆元，即 $a$ 模 $m$ 的乘法逆元 $x$，满足 $ax \equiv 1 \pmod m$，并返回其值。

rsa-3072 算法C++

以下 C++ 中使用 RSA-3072 算法进行加密和解密的示例代码：

#include <iostream>
#include <string>
#include <random>
#include <ctime>
#include <cmath>
#include <bitset>
#include <sstream>

using namespace std;

const int RSA_KEY_SIZE = 3072; // RSA 密钥位数

class RSA
{
public:
    RSA()
    {
        // 生成 RSA 密钥对
        generateRSAKeys();
    }

    // 加密函数
    string encrypt(string plaintext)
    {
        // 将明文转换为整数
        int m = stringToInteger(plaintext);

        // 计算密文
        int c = powerMod(m, e, n);

        // 将密文转换为字符串
        return integerToString(c);
    }

    // 解密函数
    string decrypt(string ciphertext)
    {
        // 将密文转换为整数
        int c = stringToInteger(ciphertext);

        // 计算明文
        int m = powerMod(c, d, n);

        // 将明文转换为字符串
        return integerToString(m);
    }

private:
    int n; // RSA 模数
    int e; // RSA 公钥指数
    int d; // RSA 私钥指数

    // 生成 RSA 密钥对
    void generateRSAKeys()
    {
        // 生成两个大素数 p 和 q
        int p = generateLargePrime();
        int q = generateLargePrime();

        // 计算 RSA 模数 n = p * q
        n = p * q;

        // 计算欧拉函数 φ(n) = (p-1)*(q-1)
        int phi_n = (p - 1) * (q - 1);

        // 选择 RSA 公钥指数 e，要求 1 < e < φ(n) 且 e 和 φ(n) 互质
        e = generateCoPrime(phi_n);

        // 计算 RSA 私钥指数 d，要求 d * e ≡ 1 (mod φ(n))
        d = findModularInverse(e, phi_n);
    }

    // 生成一个大素数
    int generateLargePrime()
    {
        // 设置随机数生成器的种子为当前时间
        mt19937 rng(time(nullptr));

        // 生成一个大于 2^(RSA_KEY_SIZE-1) 的奇数
        uniform_int_distribution<int> dist(pow(2, RSA_KEY_SIZE - 1) + 1, pow(2, RSA_KEY_SIZE) - 1);
        int n = dist(rng);

        while (!isPrime(n))
        {
            // 如果不是素数，则继续生成下一个奇数
            n += 2;
        }

        return n;
    }

    // 判断一个数是否为素数
    bool isPrime(int n)
    {
        if (n == 2 || n == 3)
        {
            return true;
        }

        if (n == 1 || n % 2 == 0)
        {
            return false;
        }

        int s = 0;
        int d = n - 1;

        while (d % 2 == 0)
        {
            s++;
            d /= 2;
        }

        for (int i = 0; i < 128; i++)
        {
            int a = rand() % (n - 3) + 2;
            int x = powerMod(a, d, n);

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

            for (int j = 0; j < s - 1; j++)
            {
                x = (x * x) % n;

                if (x == 1)
                {
                    return false;
                }

                if (x == n - 1)
                {
                    break;
                }
            }

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

        return true;
    }

    // 生成一个与 φ(n) 互质的数
    int generateCoPrime(int phi_n)
    {
        // 设置随机数生成器的种子为当前时间
        mt19937 rng(time(nullptr));

        int e;

        do
        {
            // 生成一个范围在 [2, φ(n)-1] 之间的整数
            uniform_int_distribution<int> dist(2, phi_n - 1);
            e = dist(rng);
        } while (gcd(e, phi_n) != 1);

        return e;
    }

    // 计算 a 和 b 的最大公约数
    int gcd(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }

        return gcd(b, a % b);
    }

    // 计算 a 的 b 次方对 m 取模的结果
    int powerMod(int a, int b, int m)
    {
        int result = 1;

        while (b > 0)
        {
            if (b % 2 == 1)
            {
                result = (result * a) % m;
            }

            a = (a * a) % m;
            b /= 2;
        }

        return result;
    }

    // 计算 a 在模 n 意义下的乘法逆元
    int findModularInverse(int a, int n)
    {
        int t = 0, new_t = 1;
        int r = n, new_r = a;

        while (new_r != 0)
        {
            int quotient = r / new_r;

            int temp_t = t;
            t = new_t;
            new_t = temp_t - quotient * new_t;

            int temp_r = r;
            r = new_r;
            new_r = temp_r - quotient * new_r;
        }

        if (r > 1)
        {
            throw runtime_error("a is not invertible");
        }

        if (t < 0)
        {
            t += n;
        }

        return t;
    }

    // 将字符串转换为整数
    int stringToInteger(const string& s)
    {
        int result = 0;

        for (char c : s)
        {
            result = result * 256 + static_cast<unsigned char>(c);
        }

        return result;
    }

    // 将整数转换为字符串
    string integerToString(int n)
    {
        stringstream ss;

        while (n > 0)
        {
            ss.put(n % 256);
            n /= 256;
        }

        string result = ss.str();
        reverse(result.begin(), result.end());

        return result;
    }
};

int main()
{
    RSA rsa;

    string plaintext = "Hello, RSA!";
    string ciphertext = rsa.encrypt(plaintext);
    string decryptedtext = rsa.decrypt(ciphertext);

    cout << "明文：" << plaintext << endl;
    cout << "密文：" << ciphertext << endl;
    cout << "解密后的明文：" << decryptedtext << endl;

    return 0;
}

注意：RSA-3072 是一个非常大的密钥，运行此代码可能需要较长时间。如果需要更快的运行速度，可以将 RSA_KEY_SIZE 设置为较小的值，例如 1024 或 2048。