United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-4624738 : BigInteger.isProbablePrime() reports certain primes as composite

Details
Type:
Bug
Submit Date:
2002-01-16
Status:
Closed
Updated Date:
2003-02-11
Project Name:
JDK
Resolved Date:
2003-01-31
Component:
core-libs
OS:
windows_2000
Sub-Component:
java.math
CPU:
x86
Priority:
P3
Resolution:
Fixed
Affected Versions:
1.4.0,1.4.1
Fixed Versions:
1.4.2 (b16)

Related Reports
Backport:
Duplicate:
Duplicate:

Sub Tasks

Description

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

                                    

Comments
EVALUATION

Will investigate.

###@###.### 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.

###@###.### 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. 
###@###.### 2003-01-24
                                     
2003-01-24
CONVERTED DATA

BugTraq+ Release Management Values

COMMIT TO FIX:
mantis-beta
tiger

FIXED IN:
mantis-beta
tiger

INTEGRATED IN:
mantis-b16
mantis-beta
tiger
tiger-b05

VERIFIED IN:
mantis-beta


                                     
2004-06-14



Hardware and Software, Engineered to Work Together