JDK-4813149 : BigInteger.isPossiblePrime returns false for large primes
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 1.4.1
  • Priority: P4
  • Status: Closed
  • Resolution: Duplicate
  • OS: windows_2000
  • CPU: x86
  • Submitted: 2003-02-05
  • Updated: 2003-02-05
  • Resolved: 2003-02-05
Related Reports
Duplicate :  
Description

Name: gm110360			Date: 02/05/2003


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

FULL OPERATING SYSTEM VERSION :
Microsoft Windows
2000
5.00.2195
Service Pack 2

ADDITIONAL OPERATING SYSTEMS
:



A DESCRIPTION OF THE PROBLEM :
Using my own implementation of Euler's Criterion for primality testing, i found certain large numbers to be possible primes, even though the isProbablePrime() method, claimed otherwise; i.e. returned false.

I ran these numbers through a primality proving
application:
PRIMO
(http://www.znz.freesurf.fr/pages/primo.html).
Consistently, PRIMO proved those numbers to be indeed primes.

Here is a list of seven PRIMO proven primes that isPossiblePrime clames not to be primes:

1) 888f a43a 2162 ca5c cdcf 7692 bcf5 f7a5 8f74 ff17
2) 9637 bddd 6b61 7916 4abe 971f 5051 6e4c 21de d7fb
3) 9f78 298f 3a49 3f5a 12fa 74b7 8881 61d6 5f01 9943
4) a2e0 44da ff1c f529 f536 66ab 1861 d9c8 4d20 f4af
5) a862 42e7 489d 79f3 153c 561b 5e53 00ab 736b 383f
6) de09 f190 2cf4 84f2 32fe e5d2 7262 372d 1c60 72d7
7) e844 990a 2f38 a72e 6301 97ca 3846 d75d e56e 2e53

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.math.*;

public class PrimeTest {
  public PrimeTest() {
    BigInteger b[] = new
BigInteger[]{
      new
BigInteger("779626057591079617852292862756047675913380626199"),
      new
BigInteger("857591696176672809403750477631580323575362410491"),
      new
BigInteger("910409242326391377348778281801166102059139832131"),
      new
BigInteger("929857869954035706722619989283358182285540127919"),
      new
BigInteger("961301750640481375785983980066592002055764391999"),
      new
BigInteger("1267617700951005189537696547196156120148404630231"),
      new
BigInteger("1326015641149969955786344600146607663033642528339")};
    for(int i=0;
i<b.length; i++) {
      System.out.print("BigInteger.isPossiblePrime(" + b[i] +
")\treturns\t");
      System.out.println(b[i].isProbablePrime(65000) == true ? "true!" :
"false! (should be true)");
    }
  }
  public static void main(String[] args) {
    PrimeTest
primeTest1 = new PrimeTest();
  }
}
---------- END SOURCE ----------
(Review ID: 166320) 
======================================================================

Comments
EVALUATION Submitter is correct, this has been fixed by the fix for 4624738. ###@###.### 2003-02-05
05-02-2003