src/java.base/share/classes/java/math/BigInteger.java

*** 697,706 ****
--- 697,717 ----
      }
  
      private static byte[] randomBits(int numBits, Random rnd) {
          if (numBits < 0)
              throw new IllegalArgumentException("numBits must be non-negative");
+ 
+         // It is highly likely that the first, or one of the first few bytes
+         // generated by Random.nextBytes() will be non-zero thereby making the
+         // distribution highly non-uniform by skewing it to the upper end of
+         // the interval [0, 2^numBits). To improve the uniformity of the
+         // distribution, reset numBits to a random value in the interval
+         // [0, numBits].
+         if (numBits < Integer.MAX_VALUE) {
+             numBits = rnd.nextInt(numBits + 1);
+         }
+ 
          int numBytes = (int)(((long)numBits+7)/8); // avoid overflow
          byte[] randomBits = new byte[numBytes];
  
          // Generate random bytes and mask out any excess bits
          if (numBytes > 0) {