Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-4017450

java.lang.Bignum.isProbablePrime() specification is not correct

    XMLWordPrintable

Details

    • 1.1
    • sparc
    • solaris_2.5
    • Not verified

    Description

      Specification for this method is:
         "public boolean isProbablePrime()

          This method tests for primality, first by attempting to divide
          by a few small primes, then by using the Rabin probabilistic
          primality test 50 times. The probability of failing this test
          is less than 1 / (4^n).
          Returns:
           a boolean, true if this Bignum is probably prime, false otherwise."

      It is not clear from specification what "n" is.
      It can't be this Bignum or number of binary/decimal places in it.

      Here is the example which tests primality for prime number 97,
      failure rate is rather high (about 0.1):

      import java.lang.Bignum;
      class java_lang_Bignum_isProbablePrime {
        public static void main(String args[]) {
          Bignum b1=new Bignum(97);
          int count=0;
          for (int i=1; i<=1000; i++) {
            if (!b1.isProbablePrime()) {
              System.out.print(i+" ");
              count++;
            }
          }
          System.out.println();
          System.out.println(count+" failures");
        }
      }

      ==== Here is the possible output of the test ====
      18 45 49 52 65 85 90 108 120 121 130 132 143 151 172 177 180 210 211 218 224 244 247 251 266 286 294 298 303 307 310 321 333 341 346 349 359 369 378 394 406 409 415 420 425 439 449 468 506 533 554 555 559 602 613 625 661 673 675 678 688 698 704 705 711 713 740 771 773 784 787 801 806 815 829 840 841 852 854 872 882 893 903 906 908 916 929 941 946 948 958 961 970 973 1000
      95 failures

      Attachments

        Issue Links

          Activity

            People

              mhapnersunw Mark Hapner (Inactive)
              mgorshen Mikhail Gorshenev (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:
                Imported:
                Indexed: