求 a 的 b 次方对 p 取模的值。c++

可以使用快速幂算法来求解，具体步骤如下：

1. 将 b 转化为二进制表示，例如，如果 b = 13，二进制表示为 1101。

2. 从最低位（即右侧）开始，依次考虑每一位。如果这一位为 1，就将 a 的对应幂次乘起来，否则不做处理。

3. 每乘一次就对 p 取模，避免数值溢出。

4. 在每一步中，都将 a 的幂次平方，以便在下一步中使用。

5. 最终得到的结果即为所求。

下面给出 Python 代码实现：

def power_mod(a, b, p):
    res = 1
    while b > 0:
        if b & 1 == 1:
            res = (res * a) % p
        a = (a * a) % p
        b = b >> 1
    return res

其中，& 表示按位与运算，>> 表示右移运算。

相关问题

c++求大素数原根的代码函数

以下是一个 C++ 函数，它可以用于计算大素数的原根：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 判断一个数是否为素数
bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    int sqr = sqrt(n);
    for (int i = 2; i <= sqr; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 计算 a 的 b 次方对 p 取模的结果
int power_mod(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = (long long)res * a % p;
        }
        a = (long long)a * a % p;
        b >>= 1;
    }
    return res;
}

// 获取大素数 p 的原根
int get_primitive_root(int p) {
    if (!is_prime(p)) {
        return -1;
    }
    vector<int> factors;
    int phi = p - 1;
    int tmp = phi;
    for (int i = 2; i <= tmp / i; i++) {
        if (tmp % i == 0) {
            factors.push_back(i);
            while (tmp % i == 0) {
                tmp /= i;
            }
        }
    }
    if (tmp > 1) {
        factors.push_back(tmp);
    }
    for (int g = 2; g <= p; g++) {
        bool flag = true;
        for (int i = 0; i < factors.size(); i++) {
            if (power_mod(g, phi / factors[i], p) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return g;
        }
    }
    return -1;
}

int main() {
    int p;
    cout << "请输入一个大素数 p：" << endl;
    cin >> p;
    int g = get_primitive_root(p);
    if (g == -1) {
        cout << "无法找到 " << p << " 的原根！" << endl;
    } else {
        cout << p << " 的一个原根为：" << g << endl;
    }
    return 0;
}

该函数首先判断输入的 p 是否为素数，如果不是，则输出错误信息并返回 -1。接着，它将 p - 1 分解为质因数的积，并逐个尝试每个可能的原根。对于每个可能的原根 g，它计算 g 的 phi(p) / factors[i] 次方对 p 取模的结果，并检查是否等于 1。如果对于所有质因子 i，g 的 phi(p) / factors[i] 次方对 p 取模的结果都不等于 1，则 g 是 p 的原根。如果无法找到 p 的原根，则输出错误信息并返回 -1。

注意，计算原根的时间复杂度为 O(p log^2 p)，因此该函数对于较大的素数可能需要较长的计算时间。

c++实现ElGamal

ElGamal算法是一种公钥密码体制，可以用于加密和数字签名。下面是C++实现ElGamal算法的示例代码：

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

//计算a的b次方取模p的结果
int modpow(int a, int b, int p) {
    int ans = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            ans = (ans * a) % p;
        }
        a = (a * a) % p;
        b /= 2;
    }
    return ans;
}

//计算a的逆元
int modinv(int a, int p) {
    return modpow(a, p - 2, p);
}

int main() {
    //选取一个大素数p
    int p = 2147483647;

    //选取一个原根g
    int g = 2;

    //选取一个私钥x
    int x = rand() % (p - 2) + 1;

    //计算公钥y
    int y = modpow(g, x, p);

    //加密明文m
    int m = 100;
    int k = rand() % (p - 2) + 1;
    int a = modpow(g, k, p);
    int b = (modpow(y, k, p) * m) % p;

    //解密密文c
    int c = modpow(a, p - 1 - x, p);
    int dm = (b * c) % p;

    cout << "p = " << p << endl;
    cout << "g = " << g << endl;
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;
    cout << "m = " << m << endl;
    cout << "k = " << k << endl;
    cout << "a = " << a << endl;
    cout << "b = " << b << endl;
    cout << "c = " << c << endl;
    cout << "decrypt m = " << dm << endl;

    return 0;
}

在这个示例代码中，我们选取了一个大素数p和一个原根g作为ElGamal算法的参数。首先，我们选取一个私钥x，并计算出公钥y。然后，我们选取一个随机数k，并将明文m加密成密文a和b。最后，我们解密密文c，得到明文dm。

需要注意的是，ElGamal算法的安全性依赖于离散对数问题的困难性，因此选取p和g的时候需要特别小心，以确保算法的安全性。