Primality Testing - Introduction to Cryptography with Java Applets - page 217

using the Solovay-Strassen primality test, which uses what are called Jacobi symbols; there
is no reason for us to learn it, since Rabin-Miller does just as well, and provides higher
probability with fewer trials.) We will write a method called primeProbability() to perform
Rabin-Miller's test on an integer

n . It will return the probability that n is prime, given a cer-

tain number of passes requested. If n fails any pass, primeProbability() will return 0.

import java.math.BigInteger;
import java.security.SecureRandom;
public class BigIntegerMath {
//...
static final BigInteger TWO=new BigInteger(929);
//...
//Implements the Rabin-Miller test.
//Number of different bases to try is passed in as an int
//If the BigInteger passes all tests, returns the probability it is prime as a
//double.
//Returns zero if the BigInteger is determined to be composite.
public static double primeProbability(BigInteger n,int numPasses) {
if (numPasses<=0) throw new IllegalArgumentException
(“Number of bases must be positive!”);
BigInteger b,x;
SecureRandom sr=new SecureRandom();
BigInteger nMinusOne=n.subtract(ONE);
for (int i=0;i<numPasses;i++) {
//Choose a random base smaller than n
b=new BigInteger(n.bitLength()-1,sr);
//Check Fermat's condition first
x=b.modPow(nMinusOne,n);
if (!x.equals(ONE)) return 0.0;//not prime
//Divide n-1 by 2
BigInteger[] dr=nMinusOne.divideAndRemainder(TWO);
//Perform the root tests
while (dr[1].equals(ZERO)) {
x=b.modPow(dr[0],n);
//if you get -1, this is a PASS; get out
if (x.equals(nMinusOne)) break;//pass
//Now, if its not -1 or 1, this is a FAIL, return 0
if (!x.equals(ONE)) return 0.0;//not prime
//If its 1, so far its a pass
//We can continue with the test; divide by 2
dr=dr[0].divideAndRemainder(TWO);

}

}
//Only way to get here is by passing all tests
return 1.0-Math.pow(0.25,numPasses);

}

}