3

我目前正在从事Project Euler并认为如果不只是蛮力解决所有问题，它可能会更有趣（和更好的学习体验）。在问题 3 中，它要求一个数的素因数，我的解决方案是对数进行因式分解（使用另一种因式分解算法），然后测试这些因数的素数。我为米勒-拉宾素数测试提出了这段代码（在彻底研究素数测试之后），它对我输入的所有复合奇数返回 true。有人能帮我找出原因吗？我以为我已经正确编码了算法。

    public static boolean isPrime(long num)
{
if(num % 2 == 0)
    return false;
else
{
    double d;
    int r=0;
    while((num-1) % Math.pow(2,r+1) == 0)
        r++;
    d = (num-1) % Math.pow(2,r);
    int[] a = {2,3,5,7,11,13,17,23,31,62,73,1662803};
    boolean primality = true;
    for(int k = 0; k < a.length; k++)
    {
        if((Math.pow(a[k],d)-1) % num != 0)
        {
            for(int s = 0; s < r-1; s++)
            {
                if((Math.pow(a[k],Math.pow(2,s)*d)+1) % num != 0)
                    primality = false;

            }
        }
    }
    return primality;
}
4

1 回答 1

4

给定num > 3，你想要：d, r s.t. pow(2,r) * d = num - 1, where d is odd。

您正在有效地计算 , 中的尾随零num - 1，以删除 的因子2。然而，在那个循环之后，你知道pow(2,r)是 的一个因素num - 1。因此： 

d = (num-1) % Math.pow(2,r);

将始终产生：d = 0。我怀疑您打算在这里用（div% ）替换（mod ） ；否则，将始终 yield ，并且永远不会执行内部循环。/Math.pow(a[k],d)-1(0)

正如其他人指出的那样，一些简单的跟踪语句或断言会发现这些错误。我认为您还有其他问题，例如整数溢出。对a[]候选人进行测试的循环（a-SPRP测试）在我看来完全错误。

也许您从Wikipedia获得了算法，我更喜欢The Handbook of Applied Cryptography中更详细的参考：4.2.3: Miller-Rabin test, Algorithm: 4.24。

于 2013-06-13T11:41:34.670 回答