Bug in BigInteger.isProbablePrime

David Hopwood (hopwood@zetnet.co.uk)
Sun, 6 Jul 1997 00:15:00 +0100

Date: Sun, 6 Jul 1997 00:15:00 +0100
To: java-security@web2.javasoft.com
From: David Hopwood <hopwood@zetnet.co.uk>
Subject: Bug in BigInteger.isProbablePrime

There seems to be a bug in the isProbablePrime method of BigInteger:

/**
* Returns true if this BigInteger is probably prime, false if it's
* definitely composite. The certainty parameter is a measure
* of the uncertainty that the caller is willing to tolerate:
* the method returns true if the probability that this number is
* is prime exceeds 1 - 1/2**certainty. The execution time is
* proportional to the value of the certainty parameter.
*/
public boolean isProbablePrime(int certainty) {
/*
* This test is taken from the DSA spec.
*/
int n = certainty/2;
if (n <= 0)
return true;
...

This doesn't meet its specification if certainty == 1 (and possibly
other odd numbers; I haven't checked the DSA spec). Using a certainty
of 1 (several times, in a loop) is sometimes useful when you want to
check the primality of more than one number at once.

It should be something like:

int n = (certainty+1)/2;

David Hopwood
david.hopwood@lmh.ox.ac.uk, hopwood@zetnet.co.uk