小编Cod*_*dez的帖子

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

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这样的大数字的原始根.如果有可能设置范围,那将是最好的,因为我现在正在计算整个数组.

因此,我正在寻找一种方法[代码snipet会很棒]从这个给定的数字产生大约100.000个最大的原始根.

我知道Eulerscheφ函数的速度要快得多,但我不知道如何实现它.

非常感谢.