相关疑难解决方法(0)

所以我最近一直在努力实施Miller-Rabin素性测试.我将它限制在所有32位数字的范围内,因为这是一个非常有趣的项目,我正在做的是熟悉c ++,我不想使用64位的任何东西.一会儿.另外一个好处是该算法对于所有32位数字都是确定性的,因此我可以显着提高效率,因为我确切知道要测试的证人.

因此对于较低的数字,该算法工作得非常好.但是,该过程的一部分依赖于模幂运算,即(num ^ pow)%mod.所以,例如,

3 ^ 2 % 5 = 
9 % 5 = 
4

这是我用于此模幂运算的代码:

unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
    unsigned test;
    for(test = 1; pow; pow >>= 1)
    {
        if (pow & 1)
            test = (test * num) % mod;
        num = (num * num) % mod;
    }

    return test;

}

正如您可能已经猜到的那样,当参数都是特别大的数字时会出现问题.例如,如果我想测试数字673109的素数,我将在某一点上必须找到:

(2 ^ 168277)%673109

现在2 ^ 168277是一个特别大的数字,并且在过程的某个地方它溢出测试,这导致不正确的评估.

在反面,诸如的论点

4000111222 ^ 3%1608

由于同样的原因,也评估不正确.

有没有人对模块取幂有一些建议,可以防止这种溢出和/或操纵它产生正确的结果？(我看到它的方式,溢出只是模数的另一种形式,即num%(UINT_MAX + 1))