Fastest algorithm to search if BigInteger is a prime or not?

Question

I am writing a method that determines whether BigInteger is simple or not. I used the following code / algorithm to check if a given number is prime or not. But it is very slow and takes a lot of time if the number allows you to speak 10 digits.

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

Are there any better BigInteger prime algorithms? I could not find a question related to this in Stackoverflow. If you are faced with such a question, please let me know or you have an idea on how to solve, then your ideas are greatly appreciated.

Answer 1

Here's an optimized version that uses testing only up to sqrt (n) and uses the Miller-Rabin test (according to John):

 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

Check if the integer is "probable prime". If you do not know that it is difficult, and you avoid slow factorization.

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

Also you only need to do trial divisions only to the square root of testNumber . If K is composite, you know that its smallest prime coefficient should be at most sqrt (K).

Answer 3

Some other simple improvements are to limit your set of possible numbers to only two and odd numbers in your outer loop, and only iterate to the square root of the “index” (or index / 2, if it's too hard to calculate) in your inner loop .