查找 BigInteger 是否为质数的最快算法？

Question

我正在编写一种检测 BigInteger 是否为素数的方法。我使用以下 code/algorithm 来检查给定数字是否为素数。但是如果一个数字是 10 位长的话，这是非常慢的并且需要很长时间。

 public boolean returnPrime(BigInteger testNumber){
        int divisorCounter=1;
        BigInteger index,i ;


        for ( index= new BigInteger("2"); index.compareTo(testNumber) !=1; index=index.add(new BigInteger("1"))){


            System.out.println(index);
            for(i= new BigInteger("2"); i.compareTo(index) != 1; i=i.add(new BigInteger("1"))){
            if((testNumber.mod(i).equals(BigInteger.ZERO) )){
            divisorCounter++;

            }

            if(divisorCounter>2){
            return false;
            }

            }       

        } 
    return true;

    }

有没有更好的算法来处理 BigInteger 素数？我在 Whosebug 中找不到与此相关的问题。如果您遇到过此类问题，请告诉我，或者如果您对如何解决有想法，我们将不胜感激。

Answer 1

检查整数是否为 "probable prime." 如果不是，您可以确定它是合数，并避免缓慢的因式分解。

if (!testNumber.isProbablePrime(5)) return false;

此外，您只需要进行试除直到 testNumber 的平方根。如果 K 是合数，您知道它的最小质因数最多为 sqrt(K)。

Answer 2

其他一些简单的改进是将您的可能数字集限制为外循环中的两个和奇数，并且仅迭代到 "index" 的平方根（或索引 / 2，如果太难计算）在你的内部循环中。

Answer 3

这是一个优化版本，仅使用直到 sqrt(n) 的测试并使用 Miller-Rabin 测试（截至 Joni 的回答）：

public boolean returnPrime(BigInteger number) {
    //check via BigInteger.isProbablePrime(certainty)
    if (!number.isProbablePrime(5))
        return false;

    //check if even
    BigInteger two = new BigInteger("2");
    if (!two.equals(number) && BigInteger.ZERO.equals(number.mod(two)))
        return false;

    //find divisor if any from 3 to 'number'
    for (BigInteger i = new BigInteger("3"); i.multiply(i).compareTo(number) < 1; i = i.add(two)) { //start from 3, 5, etc. the odd number, and look for a divisor if any
        if (BigInteger.ZERO.equals(number.mod(i))) //check if 'i' is divisor of 'number'
            return false;
    }
    return true;
}

查找 BigInteger 是否为质数的最快算法？

Fastest algorithm to find if a BigInteger is a prime number or not?

java

algorithm

biginteger