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

Question

I am writing a method that detects if a BigInteger is prime or not. I have used the following code/algorithm to check if a given number is prime or not. But this is extremely slow and takes long time if a number is lets say 10 digits long.

 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;

    }

Is there any better algorithms to work with BigInteger prime number? I could not find a question related to this in Stackoverflow. If you have came across such question please let me know or if you have an idea on how to solve then your ideas are much appreciated.

Solution 1

Here's an optimized version using testing only up to sqrt(n) and using the Miller-Rabin test (as of Joni's answer):

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

Solution 2

Check if the integer is a "probable prime." If it's not you know for sure that it's composite and you avoid the slow factorization.

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

Also you only need to make trial divisions only up to the square root of testNumber. If K is composite you know that its least prime factor must be at most sqrt(K).

Comments

[Vishy]

After 2, you only need to check odd numbers. Also you can stop after you reach the sqrt(n).

[Ram]

so before the second loop checking if the number is prime and passing it to second loop? That sounds good to reduce overhead because i would eliminate all even number.

[Vishy]

Also and sqrt(n) is much smaller than n

[Niklas B.]

There's also deterministic variants of the Miller-Rabin test for numbers in a given range

[Ram]

Well I tested your code and I have to say its clean and much simpler! Thank you!

[sunsin1985]

Hi @Juan Lopes, what is the reason for incrementing "i" by "two" instead of just a single step?

[Juan Lopes]

@sunsin1985 Because we are testing for divisibility by two earlier, so we don't have to test for divisibility by even factors. In a most optimized version, we would only test prime factors. But that would require computing and storing up to sqrt(n) primes in memory. However, testing if the number is even earlier allows us to cut the number of divisions by half, so it is worth the optimization.

[Jason S]

This code makes no sense at all. You're using isProbablePrime with a very low level of certainty, and then doing a regular brute force sieve that doesn't stop at sqrt(N), it goes all the way up to N. Why not just use isProbablyPrime with a high level of certainty? It would be much faster.

[Jason S]

why 5? That's not very certain.

[Joni]

"P < 0.05? Let's publish!" :P

[Juan Lopes]

@JasonS It uses isProbablePrime just as a probabilistic optimization step. Miller-Rabin probability test is fast and exact when the answer is negative. You would only have to check when it returns true, meaning it is probably prime. Also, it does stop at sqrt(N), checking whether i*i <= N does that without having to compute the square root explicitly.

[Jason S]

oh, I did miss that second part, for some reason, sorry; for some reason I read i.compareTo(number) < 1). But you're still only using Miller-Rabin with confidence level 1 - (1/4)^5 = 90.2%. That's awful; it's a fast test so you really ought to increase the 5 to something higher like 20 or 30. Also, for what it's worth, calculating sqrt(N) once is much quicker than computing i.multiply(i) repeatedly. There are ways to reduce the number of multiply operations that are faster than both.

[Eugen]

You don't need to check every uneven number up to the root, you could use i = i.nextProbablePrime(), it could falsely increase i to a number which is not a prime, but it can't skip a prime by falsely stepping over it. A bit more complicated way would be by using some primorial base, if you use the base 30 for example, you have only to check 8 of 30 numbers for primality instead of 15 of 30 if you would check every odd number. The bigger base you use, the less numbers you have to check. Using base 210 you only need to check 48 of 210, base 2310 only 480 out of every 2310 numbers, and so on.