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

The failure rate for method java.lang.Bignum.isProbablePrime() is too high

    XMLWordPrintable

    Details

    • Subcomponent:
    • CPU:
      sparc
    • OS:
      solaris_2.5

      Description

      It seems that failure rate and specified failure probability
      differ dramatically.
      ==== Here is the part of specification ====
         public boolean isProbablePrime()
           * This method tests for primality, first by attempting to divide
           * by a few small primes, then by using Algorithm P from
           * Knuth (The Art of Computer Programming - Seminumerical Alogrithms
           * pp 379 - 380)
           * The test is run for 15 trials. The probability of failing this test
           * is less than 1 / (4^15).
           *
           * @return a boolean, true if this Bignum is probably prime, false
           * otherwise.
      ==== Here is the minimized test demonstrating the bug ====
      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 ====
      4 9 12 17 21 26 31 49 53 57 78 90 121 130 139 148 156 166 177 199 202 232 238 249 286 313 320 325 344 372 385 392 406 415 420 422 440 445 452 473 475 483 494 503 507 523 526 529 535 546 558 563 567 572 583 627 630 645 657 663 665 706 713 718 734 743 768 797 802 804 809 816 818 825 836 846 852 854 867 870 878 883 885 890 894 901 922 924 930 939 941 946 959 978
      94 failures

        Attachments

          Issue Links

            Activity

              People

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

                Dates

                Created:
                Updated:
                Resolved:
                Imported:
                Indexed: