Name: jk109818 Date: 01/16/2002


FULL PRODUCT VERSION :
java version "1.3.1"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1-b24)
Java HotSpot(TM) Client VM (build 1.3.1-b24, mixed mode)

FULL OPERATING SYSTEM VERSION :

Microsoft Windows 2000 [Version 5.00.2195]



A DESCRIPTION OF THE PROBLEM :
BigInteger.isProbablePrime(int) should return true if
_this_ is probably prime, and false if it is definitely
composite.

For certain Mersenne primes and generalised Mersenne
primes, it returns false. The simplest example is 2**521-1.
Further examples are shown in the sample code below.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. Run the program below.



EXPECTED VERSUS ACTUAL BEHAVIOR :
The library method isProbablePrime() and my method mr()
should agree. For random test cases, they do agree. For the
Mersenne prime mentioned above, and for two of the three
generalised Mersenne primes, they disagree. My code is
inefficient but seems to be correct. The library code
attempts to do the same thing as my code, but is heavily
optimised (and unreadable) and clearly it gets into trouble
under some conditions.

  To confirm the primality of the Mersenne numbers, you may
refer to Johnson & Menezes, "The elliptic curve digital
signature algorithm (ECDSA)", available from
www.cacr.math.uwaterloo.ca. The Mersenne prime 2**521-1 is
well-known and a web search on "Mersenne" will turn up many
references to it.

This bug can be reproduced always.

---------- BEGIN SOURCE ----------

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

public final class Primality extends Object {

private static final Random rng = new Random();
private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = BigInteger.valueOf(2);

public static void main(String[] args) throws Exception {
for ( int i = 0; i < 20; ++ i ) {
BigInteger x = new BigInteger(128, rng);
test(x);
x = new BigInteger(128, 20, rng);
test(x);
System.err.println();
}
BigInteger m521 = ONE.shiftLeft(521).subtract(ONE);
test(m521);
BigInteger m192_64 = ONE.shiftLeft(192).subtract(ONE.shiftLeft
(64)).subtract(ONE);
test(m192_64);
BigInteger m224_96 = ONE.shiftLeft(224).subtract(ONE.shiftLeft
(96)).add(ONE);
test(m224_96);
BigInteger m256_224_192_96 = ONE.shiftLeft(256).subtract
(ONE.shiftLeft(224)).add(ONE.shiftLeft(192)).add(ONE.shiftLeft(96)).subtract
(ONE);
test(m256_224_192_96);
}

private static void test(BigInteger n) {
boolean b1 = n.isProbablePrime(20);
boolean b2 = mr(n, 20);
System.err.println(b1 + " " + b2 + (b1 != b2 ? " " + n.toString
(16) : ""));
}

private static boolean mr(BigInteger n, int t) {
if ( n.signum() <= 0 ) throw new IllegalArgumentException();
if ( n.equals(ONE) ) return false;
if ( n.equals(TWO) ) return true;
if ( ! n.testBit(0) ) return false;
BigInteger r = n.subtract(BigInteger.ONE);
int s = 0;
while ( ! r.testBit(0) ) {
++ s;
r = r.shiftRight(1);
}
for ( int i = 0; i < t; ++ i ) {
BigInteger a;
for ( ;; ) {
a = new BigInteger(n.bitLength(), rng);
if ( a.compareTo(TWO) >= 0 && a.compareTo
(n.subtract(TWO)) <= 0 ) break;
}
BigInteger y = a.modPow(r, n);
if ( y.compareTo(ONE) != 0 && y.compareTo(n.subtract
(ONE)) != 0 ) {
int j = 1;
while ( j < s && y.compareTo(n.subtract(ONE)) !
= 0 ) {
y = y.multiply(y).mod(n);
if ( y.equals(ONE) ) return false;
++ j;
}
if ( ! y.equals(n.subtract(ONE)) ) return false;
}
}
return true;
}

}

---------- END SOURCE ----------
(Review ID: 138352)
======================================================================