求一个模素数整数群的生成元的c++代码

以下是求一个模素数整数群的生成元的 C++ 代码：

#include <iostream>
#include <vector>
#include <random>
#include <chrono>

using namespace std;

// 求 a^b mod m 的值
int mod_pow(int a, int b, int m) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (long long)res * a % m;
        }
        a = (long long)a * a % m;
        b >>= 1;
    }
    return res;
}

// 判断 x 是否是 n 的质因子
bool is_prime_factor(int x, int n) {
    return n % x == 0 && mod_pow(x, (n - 1) / x, n) == 1;
}

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

// 求模素数整数群的生成元
int get_generator(int p) {
    // 求 phi(p)
    int phi = p - 1;
    int n = phi;
    vector<int> factors;
    // 分解 phi(p) 的质因子
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            factors.push_back(i);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    // 随机选取一个数作为基
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> uni(2, p - 1);
    int g = uni(rng);
    // 检查 g 是否为生成元
    for (int factor : factors) {
        if (mod_pow(g, phi / factor, p) == 1) {
            bool ok = false;
            for (int i = 0; i < factor; i++) {
                if (mod_pow(g, phi / factor / factor * i, p) != 1) {
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                return -1;
            }
        }
    }
    return g;
}

int main() {
    int p;
    cin >> p;
    if (!is_prime(p)) {
        cout << "p is not a prime number" << endl;
        return 0;
    }
    int g = get_generator(p);
    if (g == -1) {
        cout << "no generator exists" << endl;
    } else {
        cout << "generator is " << g << endl;
    }
    return 0;
}

该代码使用了欧拉定理和质因数分解的知识来求模素数整数群的生成元。具体地，首先求出 p-1 的质因数分解，然后随机选取一个数 g，检查它是否为生成元。如果 g 不是生成元，则继续随机选取一个数，直到找到一个生成元或者所有随机数都被尝试过。