Java中的素数MillerRabin素性测试

Question

我目前正在研究Project Euler，并认为如果不只是暴力解决所有问题，可能会更有趣（和更好的学习体验）。在问题3中，它要求求一个数的素数因子，我的解决方案是对该数进行因子分解（使用另一种因子分解算法），然后测试素数因子。我为Miller-Rabin素性测试（在彻底研究了素性测试之后）编写了这段代码，对于我输入的所有复合奇数，它返回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;
}

Answer 1

给定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）；否则，Math.pow(a[k],d)-1将始终产生(0)，并且内部循环将永远不会执行

正如其他人指出的，一些简单的跟踪语句或断言可能会发现这些错误。我想你还有其他问题，比如整数溢出。在我看来，针对a[]候选者的测试循环（a-SPRP测试）是完全错误的

也许你已经从Wikipedia得到了算法，我更喜欢The Handbook of Applied Cryptography中更详细的参考：4.2.3:Miller-Rabin测试，算法：4.24