使用c++实现求一个素数本原元的算法

素数$p$的本原元是指一个与$p$互质的数$g$，且满足$g$的阶为$p-1$。下面是一个用C++实现的求一个素数本原元的算法：

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

using namespace std;

int mod_pow(int x, int n, int m) {
    int res = 1;
    while (n > 0) {
        if (n & 1) {
            res = (res * x) % m;
        }
        x = (x * x) % m;
        n >>= 1;
    }
    return res;
}

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

vector<int> prime_factors(int n) {
    vector<int> factors;
    for (int i = 2; i <= sqrt(n); i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

int primitive_root(int p) {
    if (!is_prime(p)) {
        return -1;
    }
    vector<int> factors = prime_factors(p - 1);
    for (int g = 2; g <= p - 1; g++) {
        bool flag = true;
        for (int i = 0; i < factors.size(); i++) {
            if (mod_pow(g, (p - 1) / factors[i], p) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return g;
        }
    }
    return -1;
}

int main() {
    int p;
    cout << "Enter a prime number: ";
    cin >> p;
    int g = primitive_root(p);
    if (g == -1) {
        cout << "No primitive root found for " << p << endl;
    } else {
        cout << "A primitive root of " << p << " is " << g << endl;
    }
    return 0;
}

该算法的思路是：首先判断给定的$p$是否为素数，然后求出$p-1$的所有质因子，并枚举$g$从$2$到$p-1$，判断$g$是否为$p$的本原元。判断$g$是否为$p$的本原元的方法是：对于$p-1$的每个质因子$f$，计算$g^{(p-1)/f} \mod p$的值，如果都不等于1，则$g$是$p$的本原元。如果枚举完所有的$g$都无法找到$p$的本原元，则返回-1。

在求幂的过程中，可以使用快速幂算法来避免超时。