[PATCH] BigInteger(int numBits, Random rnd) distribution not uniform

Mon Aug 13 14:24:00 GMT 2001

Our DSA code uses a few loops like this:
 do {
 x = new BigInteger(160, random);
 } while (x.compareTo(some constant) > -1);
The generated BigIntegers were consistently too large, so the loop never
exited. With this patch, our code works, and the distribution seems even:
2^160 =わ 1461501637330902918203684832716283019655932542976
average = 725121081666001954241024497382577621463235643079
Index: BigInteger.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/math/BigInteger.java,v
retrieving revision 1.12
diff -u -r1.12 BigInteger.java

--- BigInteger.java	2001年06月19日 11:42:03	1.12
+++ BigInteger.java	2001年08月13日 21:03:57
@@ -142,23 +142,19 @@
 setNegative();
 }
 
- public BigInteger(int numBits, Random rnd)
- {
+ public BigInteger(int numBits, Random rnd) {
+ this(1, randBytes(numBits, rnd));
+ }
+ 
+ private static byte[] randBytes(int numBits, Random rnd) {
 if (numBits < 0)
 throw new IllegalArgumentException();
-
- // Result is always positive so tack on an extra zero word, it will be
- // canonicalized out later if necessary.
- int nwords = numBits / 32 + 2;
- words = new int[nwords];
- words[--nwords] = 0;
- words[--nwords] = rnd.nextInt() >>> (numBits % 32);
- while (--nwords >= 0)
- words[nwords] = rnd.nextInt();
-
- BigInteger result = make(words, words.length);
- this.ival = result.ival;
- this.words = result.words;
+ int extra = numBits % 8;
+ byte[] b = new byte[numBits/8 + (extra > 0 ? 1 : 0)];
+ rnd.nextBytes(b);
+ if (extra > 0)
+ b[0] &= ~((~0) << (8-extra));
+ return b;
 }
 
 public BigInteger(int bitLength, int certainty, Random rnd)
