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 :

 customer  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) 
======================================================================

N/A

Will investigate.

  xxxxx@xxxxx   2002-05-14

The initial investigation shows that the Miller-Rabin implementation included by the bug reporter and the Miller-Rabin code used in BigInteger actually both agree on the primality of the Mersenne primes listed in the description section.  In addition to a Miller-Rabin test, the BigInteger code includes a Lucas-Lehmer code; that other primality test seems to be the cause of the bug.

  xxxxx@xxxxx   2002-06-20

The code that applies the Jacobi symbol to determine an input to the Lucas-Lehmer code does so incorrectly. The current Jacobi(a, n) code only accepts positive values of a; this needs to be fixed because the correct algorithm requires the calculation for negative values of a. 
  xxxxx@xxxxx   2003-01-24

The funny thing is that source code for Java 1.3.1  is
correct. If you just run the given source code, it works
fine. I wonder how could this be possible.

A smaller example which produces the error is 
120000000000000000000000000000000019 = 12*10^34+19. 
I certified this as prime using a program called Certifix (which 
is an old version of a program currently called Primo). I 
noticed the problem using JDK1.4.0 on a program which (if I 
remember correctly) worked fine under JDK1.2. My code to 
reproduce the problem is:

 BigInteger bi = new BigInteger
("120000000000000000000000000000000019");
    if (!(bi.isProbablePrime(10))) {
      System.out.println("Java declares "+bi+" composite");
    }
No easy workaround.

633825300114114700748351603131 or
80000000000000000000001BBh or
just a tad above 100 bits, seems to be the lowest prime 
number rejected by the Sun implementation. For numbers 
above 100 bits, the error seems to appear fairly regularly.

Since the Lucas-Lehmer test is only run on numbers over 100 
bits, this would indicate that the LL test is buggy.

I don't know if it's the right place, but this code for Miller-
Rabin primality test work properly, it's created as a separated 
function, but it's easyly to transfer to a BigInteger class 
operation.

	private static boolean MillerRabin(BigInteger p, int k)
{

		boolean retorn = true;
		
		int aa = p.bitLength();
		SecureRandom rnd = new SecureRandom();
		BigInteger bigs[] = new BigInteger[k];
		int i = 1;
		BigInteger pmenosuno = p.subtract
(BigInteger.ONE);
		bigs[0] = new BigInteger("2");
		while(i < k && retorn){
			bigs[i] = new BigInteger(aa, rnd);
			if (p.compareTo(bigs[i]) == 1){
				if (mcd(p, bigs
[i]).compareTo(BigInteger.ONE) != 0){
					retorn = false;
				}
				else if(!bigs[i].modPow
(pmenosuno, p).equals(BigInteger.ONE)) {
					retorn = false;
				}
				i++;
			}
		}

		i = 0;
		int b = pmenosuno.getLowestSetBit();
		BigInteger m = pmenosuno.shiftRight(b);
		int j = 0;
		while (retorn && (i < k)){
			BigInteger z = bigs[i].modPow(m, 
p);
			if (!z.equals(BigInteger.ONE)){
				while (j < b && retorn){
					if (z.equals
(pmenosuno)) {
						j = b 
+ 1;
					}
					if (z.equals
(BigInteger.ONE)){
					
	retorn = false;
					}
					z = z.multiply
(z).mod(p);	 				
		
					j++;
				}
				if (j == b) {
					retorn= false;
				}
			}
			i++;
		}
		return retorn;
	} 

I use secureRandom, to accelerate this algorithm it's possible 
to change SecureRandom for another random generator.

I also stumbled on this problem, with the prime
1461501637330902918203684832716283019651637554291 (from the
SEC1 standard).
I did take the primality check code from JDK 1.3.1, and run
it in my own program, and the Lucas-Lehmer test was
responsible for the wrong answer. I don't know how
muratkantarcioglu tested it, but what I did was to copy &
paste just the MR & LL functions into my code, and modify
them to run as non-BigInteger-methods.

I first noticed this with the prime (2^101+1)/3 - HOWEVER
_only_ with the Linux (sic) version of JDK1.3.1 - identical
(application) code [isProbablePrime(1000)] in the Windows
version doesn't appear to have this problem