# Bug in BigInteger.isProbablePrime

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

- Messages sorted by: [ date ][ thread ][ subject ][ author ]
- Next message: noreply_user30@aol.com: "Attn: Business Owners! Would you like to increase sales and bring in more customers?"
- Previous message: Navindra Umanee: "incomplete export control terms and conditions ?"

    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

- Next message: noreply_user30@aol.com: "Attn: Business Owners! Would you like to increase sales and bring in more customers?"
- Previous message: Navindra Umanee: "incomplete export control terms and conditions ?"