JDK-4624738 : BigInteger.isProbablePrime() reports certain primes as composite
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.math
  • Affected Version: 1.4.0,1.4.1
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: windows_2000
  • CPU: x86
  • Submitted: 2002-01-16
  • Updated: 2003-02-11
  • Resolved: 2003-01-31
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
Other
1.4.2 b16Fixed
Related Reports
Duplicate :  
Duplicate :  
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
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
14-06-2004

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
24-01-2003