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

Mark J Roberts mjr@anarcast.net
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)



More information about the Java mailing list