c++ - 寻找原根的更快算法

Question

我试图用这个算法找到质根:

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这样的大数的原根。如果可以设置一个范围是最好的，因为我现在正在计算整个集合。

所以基本上我正在寻找一种方法 [code snipet would be great] 从给定的大数中生成大约 100.000 个最大的原根。

我知道使用 Eulersche φ 函数要快得多，但我不知道如何实现它。

非常感谢。

Answer 1

首先，如果您从 2 到 p-1 中随机选择一个整数，那么它很有可能成为原根。所以你选择一个随机整数(或者你从 2 开始)，检查它，如果失败，你选择下一个等等。

检查 x 是否为原根:这意味着 x^(p-1) = 1(模 p)，但不小于 p 的幂。例如 p = 31，p-1 = 30 = 2 x 3 x 5。如果 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 是原根。但是，您关心多个原根的情况很少见。