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

Question

我正在编写一种方法来检测BigInteger是否为素数.我使用以下代码/算法来检查给定数字是否为素数.但这是非常缓慢的,如果一个数字可以说长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素数？我在Stackoverflow中找不到与此相关的问题.如果您遇到过这样的问题,请告诉我,或者如果您对如何解决有所了解,那么您的想法将受到高度赞赏.

Answer 1

这是一个优化版本,使用最多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;
}

Answer 2

检查整数是否是“可能的素数”。如果不是，您肯定知道它是复合的，并且您避免了缓慢的因式分解。

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

此外，您只需将试除法划分为 的平方根testNumber。如果 K 是复合的，你就知道它的最小素因数最多是 sqrt(K)。