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

BigInteger random constructor does not produce a uniform distribution

    Details

    • Subcomponent:
    • CPU:
      generic
    • OS:
      generic

      Description

      FULL PRODUCT VERSION :
      java version "1.8.0_45"
      Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
      Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)

      ADDITIONAL OS VERSION INFORMATION :
      Darwin .local 13.2.0 Darwin Kernel Version 13.2.0: Thu Apr 17 23:03:13 PDT 2014; root:xnu-2422.100.13~1/RELEASE_X86_64 x86_64

      A DESCRIPTION OF THE PROBLEM :
      The results from the constructor for BigInteger that accepts the number of bits and an instance of Random does not produce uniform results. Numbers smaller than a very high limit are never generated.

      A "workaround" that produces a better distribution of random numbers is to use
      int nBits = random.nextInt(vMax);
      BigInteger randomlyChosen = new BigInteger(nBits, random);
      but those results also show a bias - the largest of numbers are not generated as often as the nearly uniform distribution of all numbers below them.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      SecureRandom sr = SecureRandom.getInstance("SHA1PRNG");
      int nBits = 4096;
      for (int i = 0; i < 10000; ++i) {
          // biased towards high numbers. never chooses below a high limit
          BigInteger number = new BigInteger(nBits, sr);
          System.out.println(number.toString());
      }

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      A uniform distribution of numbers between 0 to (2^numBits - 1), inclusive.
      ACTUAL -
      The results are numbers above a very high limit.

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      import java.security.SecureRandom;
      import java.math.BigInteger;

      public class T {

          public void test() throws Exception {

              SecureRandom sr = SecureRandom.getInstance("SHA1PRNG");
              int nBits = 4096;
              for (int i = 0; i < 1000; ++i) {
                  // biased towards high numbers. never chooses below a high limit
                  BigInteger number = new BigInteger(nBits, sr);
                  System.out.println(number.toString());
              }
          }
      }
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      A "workaround" that produces a better distribution of random numbers is to use
      int nBits = random.nextInt(vMax);
      BigInteger randomlyChosen = new BigInteger(nBits, random);
      but those results also show a bias - the largest of numbers are not generated as often as the nearly uniform distribution of all numbers below them.


        Attachments

        1. out.log
          1.18 MB
          Pallavi Sonal
        2. out8u66.log
          1.18 MB
          Pallavi Sonal
        3. TestBigIntegerRandom.java
          0.5 kB
          Pallavi Sonal

          Issue Links

            Activity

              People

              • Assignee:
                bpb Brian Burkhalter
                Reporter:
                webbuggrp Webbug Group
              • Votes:
                0 Vote for this issue
                Watchers:
                4 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: