C中高数字的模块化指数

所以我最近一直在执行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))

解决方法

Exponentiation by squaring仍然“工作”用于模幂.你的问题不是2 ^ 168277是一个非常大的数字,这是一个中间的结果是一个相当大的数字(大于2 ^ 32),因为673109大于2 ^ 16.

所以我认为以下将会做.可能我错过了一个细节,但是基本思想是有效的,这就是“真正的”密码如何进行大的mod-exponentiation(尽管不是32位和64位数字,而是不必大于2 * log(模量))：

按照你的平均数开始求幂.
>以64位无符号整数进行实际平方.
>像您一样,在每一步减少模数为673109,以恢复到32位范围内.

显然,如果您的C实现没有64位整数,那么这有点尴尬,尽管你总是假的.

这里有一个幻灯片22的例子：http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf,虽然它使用的数字很少(小于2 ^ 16),所以它可能不会说明你还不知道的内容.

您的其他示例,4000111222 ^ 3％1608将适用于您当前的代码,如果您刚刚减少4000111222模1608开始之前. 1608足够小,您可以安全地乘以32位int中的任何两个mod-1608数字.

C中高数字的模块化指数

解决方法

相关文章