Java 中的 Miller-Rabin Primality 测试 [英] Miller-Rabin Primality test in Java

问题描述

我目前正在从事 Project Euler 并认为如果不这样做可能会更有趣(和更好的学习体验)不只是蛮力解决所有问题.在问题 3 上，它要求求一个数的质因数，我的解决方案是对这个数进行因数分解(使用另一种分解算法)，然后测试这些因数的素数.我想出了这个用于 Miller-Rabin 素性测试的代码(在彻底研究了素性测试之后)，它对于我输入的所有复合奇数都返回 true.有人能帮我找出原因吗?我以为我已经正确编码了算法.

I am currently working on Project Euler and thought that it might be more interesting (and a better learning experience) if don't just brute force all of the questions. On question 3 it asks for prime factors of a number and my solution will be to factor the number (using another factoring algorithm) and then test the factors for primality. I came up with this code for a Miller-Rabin Primality test (after thoroughly researching primality test) and it returns true for all the composite odd number I have put in. Can anybody help me to figure out why? I thought I had coded the algorithm correctly.

    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;
}

推荐答案

Given num >3，你想要:d, r s.t.pow(2,r) * d = num - 1，其中 d 为奇数.

Given num > 3, you want: d, r s.t. pow(2,r) * d = num - 1, where d is odd.

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

You are effectively counting trailing zeroes from num - 1, to remove factors of 2. However, after that loop, you know pow(2,r) is a factor of num - 1. Hence:

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

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

will always yield: d = 0. I suspect you meant to replace % (mod) with / (div) here; otherwise, Math.pow(a[k],d)-1 will always yield (0), and the inner loop will never be executed.

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

As others pointed out, some simple trace statements or assertions would have found these errors. I think you have other issues, such as integer overflow. The loop for testing against the a[] candidates (the a-SPRP test) looks completely wrong to me.

也许您已经从 维基百科 获得了算法，我更喜欢 The Handbook of Applied Cryptography 中更详细的参考:4.2.3:Miller-Rabin 测试，算法:4.24.

Perhaps you've got the algorithm from Wikipedia, I prefer the more detailed reference in The Handbook of Applied Cryptography: 4.2.3: Miller-Rabin test, Algorithm: 4.24.

这篇关于Java 中的 Miller-Rabin Primality 测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！