java - Java 中的 Miller-Rabin 素数测试

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，其中 d 为奇数。

您正在有效地计算 num - 1 中的尾随零，以移除 2 的因数。但是，在该循环之后，您知道 pow(2,r) 是 num - 1 的因数。因此:

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

将始终产生:d = 0。我怀疑您打算在此处将 % (mod) 替换为 / (div)；否则，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.