c++ - 查找原始根的更快算法

我正在尝试使用此算法找到素数根:

std::vector<unsigned long long> Keyexchange::primroot(unsigned long long val) {

    std::vector<unsigned long long> res;

    for (unsigned long long i = 2; i<val - 1; i++) {

        unsigned long long start = 1;
        bool flag = 1;

        for (unsigned long long j = 0; j<val / 2; j++) {
            start = (start * i) % val;
            if (start % val == 1) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            res.push_back(i);
        }
    }
    return res;
}

它的效果很好，但是非常慢。
我想计算像1073741789这样的大数字的原始根。如果可以设置范围，那将是最好的选择，因为我现在正在计算整个集合。

因此，从根本上讲，我正在寻找一种方法(代码片段很棒)，以便从给定的大数字中生成大约100.000的最大原始根。

我知道使用Eulerscheφ函数会更快，但是我不知道如何实现它。

非常感谢。

最佳答案

首先，如果您选择一个从2到p-1的随机整数，那么它很有可能成为原始根。因此，您选择一个随机整数(或以2开头)，检查它，如果失败，则选择下一个整数，依此类推。

要检查x是原始根，请执行以下操作:这意味着x ^(p-1)= 1(模p)，但p的幂不小于。例如，p = 31，p-1 = 30 = 2 x 3 x5。如果p不是原始根，则x ^(30/2)，x ^(30/3)和x ^(30 / 5)必须为1(模p)。

将p-1因子作为其素因子，为每个素因子f计算x ^((p-1)/ f)(模p)，如果所有结果都不为1，则x为原始根。

当然，需要使用重复平方/乘法来计算x ^ y(模p)。例如，要计算x ^ 10，您将按该顺序计算x ^ 2，x ^ 4，x ^ 5，x ^ 10。

一旦找到原始根g，如果gcd(k，p-1)= 1，则g ^ k是原始根。但是在少数情况下，您需要多个原始根。