BigInteger .isProbablePrime() Part 1 Tutorial

boolean isProbablePrime(int certainty)

In this tutorial I am going to discuss the .isProbablePrime() method. It returns false if the BigInteger object value is definitely composite. It returns true if the BigInteger object value is probably prime. This method is extremely fast for determining if a number is composite - maybe they should have named this method isComposite() instead ;) So why did they name it isProbablePrime() anyway???

Miller-Rabin Primality Test

The reason this method is so fast is because it utilizes the Miller-Rabin primality test. The math and proofs behind the Miller-Rabin primality test is way beyond the scope of this tutorial, but I will do my best to describe the general idea of how it works. A multiple (the int certainty parameter) of tests (algorithms) are performed on random numbers that are less than number we are trying to determine the primality of. The more tests that you perform, the higher the probability that a true result will actually be a prime number. Setting the certainty parameter to 80 or more will almost always indicate that a number is prime if the result is true. Because of the way the algorithm works, if the result is false, then the number is composite. It is important to note that when a M-R test returns false, we will have no idea what any of the factors are. Let's get started...



Open the command prompt (CMD - see the Getting Started ) and type in the following commands.

C:\Windows\System32>cd \
C:\>md Java
C:\>cd Java
C:\Java>
C:\Java>md PrimeOne
C:\Java>cd PrimeOne
C:\Java\PrimeOne>Notepad PrimeOne.java

Copy and Paste, or type the following code into Notepad and be sure to save the file when you are done.


import java.math.*;
import java.util.*;

class PrimeOne {

    private static final int NTH_PRIME = 10;

    public static void main(String args[]) {
		
        BigInteger TWO = new BigInteger("2");
        BigInteger bi = new BigInteger("1");

        System.out.println("2"); // 2 is the first prime number
        int i = 1;
		
        long startTime = System.currentTimeMillis();
        while(i < NTH_PRIME) {
            bi = bi.add(TWO);
            if (bi.isProbablePrime(80)) {
                i++;
                System.out.println(bi);
            }
        }
		
        System.out.println("The " + NTH_PRIME + "th prime number is: " + bi);
        System.out.println("Time to calc was: " + (System.currentTimeMillis() - startTime) + " milliseconds");

        /*BigInteger randomOne = new BigInteger(1023, 80, new Random());
        BigInteger randomTwo = new BigInteger(1026, 80, new Random());
        System.out.println("randomOne= " + randomOne);
        System.out.println("\nrandomTwo= " + randomTwo);
		
        BigInteger product = randomOne.multiply(randomTwo);
        System.out.println("\nproduct= " + product);
        System.out.println(product.bitLength());
        System.out.println(product.isProbablePrime(10));*/
    }
}


Now switch back to the command prompt (CMD) and type in javac PrimeOne.java and press Enter.
Now type in java PrimeOne and press Enter.


C:\Java\PrimeOne>javac PrimeOne.java
C:\Java\PrimeOne>java PrimeOne
See video for results and more...


Final thoughts

Stay tuned for my next tutorial where I will discuss some concepts about RSA encryption and how the isProbablePrime() method can be used to try to determine prime factors of large public keys.


Tutorials