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

@@ -697,10 +697,27 @@
     }
 
     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, adjust numBits to a random value in the interval
+        // [0, numBits].
+        if (numBits < Integer.MAX_VALUE) {
+            final int numBitsOriginal = numBits;
+            numBits = rnd.nextInt(numBits + 1);
+            // Increment the adjusted maximum bit length to help prevent the
+            // very largest numbers from being underrepresented.
+            if (numBits < numBitsOriginal) {
+                numBits++;
+            }
+        }
+
         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) {