1 /*
   2  * Copyright (c) 1998, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test
  26  * @library ..
  27  * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460
  28  * @summary tests methods in BigInteger (use -Dseed=X to set PRNG seed)
  29  * @run main/timeout=400 BigIntegerTest
  30  * @author madbot
  31  * @key randomness
  32  */
  33 
  34 import java.io.File;
  35 import java.io.FileInputStream;
  36 import java.io.FileOutputStream;
  37 import java.io.ObjectInputStream;
  38 import java.io.ObjectOutputStream;
  39 import java.math.BigInteger;
  40 
  41 /**
  42  * This is a simple test class created to ensure that the results
  43  * generated by BigInteger adhere to certain identities. Passing
  44  * this test is a strong assurance that the BigInteger operations
  45  * are working correctly.
  46  *
  47  * Four arguments may be specified which give the number of
  48  * decimal digits you desire in the four batches of test numbers.
  49  *
  50  * The tests are performed on arrays of random numbers which are
  51  * generated by a Random class as well as special cases which
  52  * throw in boundary numbers such as 0, 1, maximum sized, etc.
  53  *
  54  */
  55 public class BigIntegerTest {
  56     //
  57     // Bit large number thresholds based on the int thresholds
  58     // defined in BigInteger itself:
  59     //
  60     // KARATSUBA_THRESHOLD        = 80  ints = 2560 bits
  61     // TOOM_COOK_THRESHOLD        = 240 ints = 7680 bits
  62     // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits
  63     // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits
  64     //
  65     // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits
  66     //
  67     // BURNIKEL_ZIEGLER_THRESHOLD = 80  ints = 2560 bits
  68     //
  69     static final int BITS_KARATSUBA = 2560;
  70     static final int BITS_TOOM_COOK = 7680;
  71     static final int BITS_KARATSUBA_SQUARE = 4096;
  72     static final int BITS_TOOM_COOK_SQUARE = 6912;
  73     static final int BITS_SCHOENHAGE_BASE = 640;
  74     static final int BITS_BURNIKEL_ZIEGLER = 2560;
  75     static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280;
  76 
  77     static final int ORDER_SMALL = 60;
  78     static final int ORDER_MEDIUM = 100;
  79     // #bits for testing Karatsuba
  80     static final int ORDER_KARATSUBA = 2760;
  81     // #bits for testing Toom-Cook and Burnikel-Ziegler
  82     static final int ORDER_TOOM_COOK = 8000;
  83     // #bits for testing Karatsuba squaring
  84     static final int ORDER_KARATSUBA_SQUARE = 4200;
  85     // #bits for testing Toom-Cook squaring
  86     static final int ORDER_TOOM_COOK_SQUARE = 7000;
  87 
  88     static final int SIZE = 1000; // numbers per batch
  89 
  90     private static RandomSeed rndSeed = new RandomSeed(false);
  91 
  92     static boolean failure = false;
  93 
  94     public static void constructor() {
  95         int failCount = 0;
  96 
  97         // --- guard condition tests for array indexing ---
  98 
  99         int arrayLength = 23;
 100         int halfLength = arrayLength/2;
 101         byte[] array = new byte[arrayLength];
 102         rndSeed.getRandom().nextBytes(array);
 103 
 104         int[][] offLen = new int[][] { // offset, length, num exceptions
 105             {-1, arrayLength, 1},                         // negative offset
 106             {0, arrayLength, 0},                          // OK
 107             {1, arrayLength, 1},                          // length overflow
 108             {arrayLength - 1, 1, 0},                      // OK
 109             {arrayLength, 1, 1},                          // offset overflow
 110             {0, -1, 1},                                   // negative length
 111             {halfLength, arrayLength - halfLength + 1, 1} // length overflow
 112         };
 113 
 114         // two's complement
 115         for (int[] ol : offLen) {
 116             int numExceptions = 0;
 117             try {
 118                 BigInteger bi = new BigInteger(array, ol[0], ol[1]);
 119             } catch (IndexOutOfBoundsException e) {
 120                 numExceptions++;
 121             }
 122             if (numExceptions != ol[2]) {
 123                 System.err.println("IndexOutOfBoundsException did not occur for "
 124                     + " two's complement constructor with parameters offset "
 125                     + ol[0] + " and length " + ol[1]);
 126                 failCount++;
 127             }
 128         }
 129 
 130         // sign-magnitude
 131         for (int[] ol : offLen) {
 132             int numExceptions = 0;
 133             try {
 134                 BigInteger bi = new BigInteger(1, array, ol[0], ol[1]);
 135             } catch (IndexOutOfBoundsException e) {
 136                 numExceptions++;
 137             }
 138             if (numExceptions != ol[2]) {
 139                 System.err.println("IndexOutOfBoundsException did not occur for "
 140                     + " sign-magnitude constructor with parameters offset "
 141                     + ol[0] + " and length " + ol[1]);
 142                 failCount++;
 143             }
 144         }
 145 
 146         // --- tests for creation of zero-valued BigIntegers ---
 147 
 148         byte[] magZeroLength = new byte[0];
 149         for (int signum = -1; signum <= 1; signum++) {
 150             BigInteger bi = new BigInteger(signum, magZeroLength);
 151             if (bi.compareTo(BigInteger.ZERO) != 0) {
 152                 System.err.println("A: Zero length BigInteger != 0 for signum " + signum);
 153                 failCount++;
 154             }
 155         }
 156 
 157         for (int signum = -1; signum <= 1; signum++) {
 158             BigInteger bi = new BigInteger(signum, magZeroLength, 0, 0);
 159             if (bi.compareTo(BigInteger.ZERO) != 0) {
 160                 System.err.println("B: Zero length BigInteger != 0 for signum " + signum);
 161                 failCount++;
 162             }
 163         }
 164 
 165         byte[] magNonZeroLength = new byte[42];
 166         rndSeed.getRandom().nextBytes(magNonZeroLength);
 167         for (int signum = -1; signum <= 1; signum++) {
 168             BigInteger bi = new BigInteger(signum, magNonZeroLength, 0, 0);
 169             if (bi.compareTo(BigInteger.ZERO) != 0) {
 170                 System.err.println("C: Zero length BigInteger != 0 for signum " + signum);
 171                 failCount++;
 172             }
 173         }
 174 
 175         // --- tests for accurate creation of non-zero BigIntegers ---
 176 
 177         for (int i = 0; i < SIZE; i++) {
 178             // create reference value via a different code path from those tested
 179             BigInteger reference = new BigInteger(2 + rndSeed.getRandom().nextInt(336), 4, rndSeed.getRandom());
 180 
 181             byte[] refArray = reference.toByteArray();
 182             int refLen = refArray.length;
 183             int factor = rndSeed.getRandom().nextInt(5);
 184             int objLen = refArray.length + factor*rndSeed.getRandom().nextInt(refArray.length) + 1;
 185             int offset = rndSeed.getRandom().nextInt(objLen - refLen);
 186             byte[] objArray = new byte[objLen];
 187             System.arraycopy(refArray, 0, objArray, offset, refLen);
 188 
 189             BigInteger twosComp = new BigInteger(objArray, offset, refLen);
 190             if (twosComp.compareTo(reference) != 0) {
 191                 System.err.println("Two's-complement BigInteger not equal for offset " +
 192                         offset + " and length " + refLen);
 193                 failCount++;
 194             }
 195 
 196             boolean isNegative = rndSeed.getRandom().nextBoolean();
 197             BigInteger signMag = new BigInteger(isNegative ? -1 : 1, objArray, offset, refLen);
 198             if (signMag.compareTo(isNegative ? reference.negate() : reference) != 0) {
 199                 System.err.println("Sign-magnitude BigInteger not equal for offset " +
 200                         offset + " and length " + refLen);
 201                 failCount++;
 202             }
 203         }
 204 
 205         report("Constructor", failCount);
 206     }
 207 
 208     public static void pow(int order) {
 209         int failCount1 = 0;
 210 
 211         for (int i=0; i<SIZE; i++) {
 212             // Test identity x^power == x*x*x ... *x
 213             int power = rndSeed.getRandom().nextInt(6) + 2;
 214             BigInteger x = fetchNumber(order);
 215             BigInteger y = x.pow(power);
 216             BigInteger z = x;
 217 
 218             for (int j=1; j<power; j++)
 219                 z = z.multiply(x);
 220 
 221             if (!y.equals(z))
 222                 failCount1++;
 223         }
 224         report("pow for " + order + " bits", failCount1);
 225     }
 226 
 227     public static void square(int order) {
 228         int failCount1 = 0;
 229 
 230         for (int i=0; i<SIZE; i++) {
 231             // Test identity x^2 == x*x
 232             BigInteger x  = fetchNumber(order);
 233             BigInteger xx = x.multiply(x);
 234             BigInteger x2 = x.pow(2);
 235 
 236             if (!x2.equals(xx))
 237                 failCount1++;
 238         }
 239         report("square for " + order + " bits", failCount1);
 240     }
 241 
 242     public static void arithmetic(int order) {
 243         int failCount = 0;
 244 
 245         for (int i=0; i<SIZE; i++) {
 246             BigInteger x = fetchNumber(order);
 247             while(x.compareTo(BigInteger.ZERO) != 1)
 248                 x = fetchNumber(order);
 249             BigInteger y = fetchNumber(order/2);
 250             while(x.compareTo(y) == -1)
 251                 y = fetchNumber(order/2);
 252             if (y.equals(BigInteger.ZERO))
 253                 y = y.add(BigInteger.ONE);
 254 
 255             // Test identity ((x/y))*y + x%y - x == 0
 256             // using separate divide() and remainder()
 257             BigInteger baz = x.divide(y);
 258             baz = baz.multiply(y);
 259             baz = baz.add(x.remainder(y));
 260             baz = baz.subtract(x);
 261             if (!baz.equals(BigInteger.ZERO))
 262                 failCount++;
 263         }
 264         report("Arithmetic I for " + order + " bits", failCount);
 265 
 266         failCount = 0;
 267         for (int i=0; i<100; i++) {
 268             BigInteger x = fetchNumber(order);
 269             while(x.compareTo(BigInteger.ZERO) != 1)
 270                 x = fetchNumber(order);
 271             BigInteger y = fetchNumber(order/2);
 272             while(x.compareTo(y) == -1)
 273                 y = fetchNumber(order/2);
 274             if (y.equals(BigInteger.ZERO))
 275                 y = y.add(BigInteger.ONE);
 276 
 277             // Test identity ((x/y))*y + x%y - x == 0
 278             // using divideAndRemainder()
 279             BigInteger baz[] = x.divideAndRemainder(y);
 280             baz[0] = baz[0].multiply(y);
 281             baz[0] = baz[0].add(baz[1]);
 282             baz[0] = baz[0].subtract(x);
 283             if (!baz[0].equals(BigInteger.ZERO))
 284                 failCount++;
 285         }
 286         report("Arithmetic II for " + order + " bits", failCount);
 287     }
 288 
 289     /**
 290      * Sanity test for Karatsuba and 3-way Toom-Cook multiplication.
 291      * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,
 292      * construct two factors each with a mag array one element shorter than the
 293      * threshold, and with the most significant bit set and the rest of the bits
 294      * random. Each of these numbers will therefore be below the threshold but
 295      * if shifted left be above the threshold. Call the numbers 'u' and 'v' and
 296      * define random shifts 'a' and 'b' in the range [1,32]. Then we have the
 297      * identity
 298      * <pre>
 299      * (u << a)*(v << b) = (u*v) << (a + b)
 300      * </pre>
 301      * For Karatsuba multiplication, the right hand expression will be evaluated
 302      * using the standard naive algorithm, and the left hand expression using
 303      * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right
 304      * hand expression will be evaluated using Karatsuba multiplication, and the
 305      * left hand expression using 3-way Toom-Cook multiplication.
 306      */
 307     public static void multiplyLarge() {
 308         int failCount = 0;
 309 
 310         BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
 311         for (int i=0; i<SIZE; i++) {
 312             BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
 313             BigInteger u = base.add(x);
 314             int a = 1 + rndSeed.getRandom().nextInt(31);
 315             BigInteger w = u.shiftLeft(a);
 316 
 317             BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);
 318             BigInteger v = base.add(y);
 319             int b = 1 + rndSeed.getRandom().nextInt(32);
 320             BigInteger z = v.shiftLeft(b);
 321 
 322             BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);
 323             BigInteger karatsubaMultiplyResult = w.multiply(z);
 324 
 325             if (!multiplyResult.equals(karatsubaMultiplyResult)) {
 326                 failCount++;
 327             }
 328         }
 329 
 330         report("multiplyLarge Karatsuba", failCount);
 331 
 332         failCount = 0;
 333         base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
 334         for (int i=0; i<SIZE; i++) {
 335             BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
 336             BigInteger u = base.add(x);
 337             BigInteger u2 = u.shiftLeft(1);
 338             BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
 339             BigInteger v = base.add(y);
 340             BigInteger v2 = v.shiftLeft(1);
 341 
 342             BigInteger multiplyResult = u.multiply(v).shiftLeft(2);
 343             BigInteger toomCookMultiplyResult = u2.multiply(v2);
 344 
 345             if (!multiplyResult.equals(toomCookMultiplyResult)) {
 346                 failCount++;
 347             }
 348         }
 349 
 350         report("multiplyLarge Toom-Cook", failCount);
 351     }
 352 
 353     /**
 354      * Sanity test for Karatsuba and 3-way Toom-Cook squaring.
 355      * This test is analogous to {@link AbstractMethodError#multiplyLarge}
 356      * with both factors being equal. The squaring methods will not be tested
 357      * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether
 358      * the parameter is the same instance on which the method is being invoked
 359      * and calls <code>square()</code> accordingly.
 360      */
 361     public static void squareLarge() {
 362         int failCount = 0;
 363 
 364         BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
 365         for (int i=0; i<SIZE; i++) {
 366             BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
 367             BigInteger u = base.add(x);
 368             int a = 1 + rndSeed.getRandom().nextInt(31);
 369             BigInteger w = u.shiftLeft(a);
 370 
 371             BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
 372             BigInteger karatsubaSquareResult = w.multiply(w);
 373 
 374             if (!squareResult.equals(karatsubaSquareResult)) {
 375                 failCount++;
 376             }
 377         }
 378 
 379         report("squareLarge Karatsuba", failCount);
 380 
 381         failCount = 0;
 382         base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
 383         for (int i=0; i<SIZE; i++) {
 384             BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
 385             BigInteger u = base.add(x);
 386             int a = 1 + rndSeed.getRandom().nextInt(31);
 387             BigInteger w = u.shiftLeft(a);
 388 
 389             BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
 390             BigInteger toomCookSquareResult = w.multiply(w);
 391 
 392             if (!squareResult.equals(toomCookSquareResult)) {
 393                 failCount++;
 394             }
 395         }
 396 
 397         report("squareLarge Toom-Cook", failCount);
 398     }
 399 
 400     /**
 401      * Sanity test for Burnikel-Ziegler division.  The Burnikel-Ziegler division
 402      * algorithm is used when each of the dividend and the divisor has at least
 403      * a specified number of ints in its representation.  This test is based on
 404      * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
 405      * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if
 406      * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then
 407      * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}.  The test
 408      * ensures that {@code v} is just under the B-Z threshold, that {@code z} is
 409      * over the threshold and {@code w} is much larger than {@code z}. This
 410      * implies that {@code u/v} uses the standard division algorithm and
 411      * {@code w/z} uses the B-Z algorithm.  The results of the two algorithms
 412      * are then compared using the observation described in the foregoing and
 413      * if they are not equal a failure is logged.
 414      */
 415     public static void divideLarge() {
 416         int failCount = 0;
 417 
 418         BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33);
 419         for (int i=0; i<SIZE; i++) {
 420             BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, rndSeed.getRandom());
 421             BigInteger v = base.add(addend);
 422 
 423             BigInteger u = v.multiply(BigInteger.valueOf(2 + rndSeed.getRandom().nextInt(Short.MAX_VALUE - 1)));
 424 
 425             if(rndSeed.getRandom().nextBoolean()) {
 426                 u = u.negate();
 427             }
 428             if(rndSeed.getRandom().nextBoolean()) {
 429                 v = v.negate();
 430             }
 431 
 432             int a = BITS_BURNIKEL_ZIEGLER_OFFSET + rndSeed.getRandom().nextInt(16);
 433             int b = 1 + rndSeed.getRandom().nextInt(16);
 434             BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a));
 435             BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b));
 436 
 437             BigInteger[] divideResult = u.divideAndRemainder(v);
 438             divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b));
 439             divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b));
 440             BigInteger[] bzResult = w.divideAndRemainder(z);
 441 
 442             if (divideResult[0].compareTo(bzResult[0]) != 0 ||
 443                     divideResult[1].compareTo(bzResult[1]) != 0) {
 444                 failCount++;
 445             }
 446         }
 447 
 448         report("divideLarge", failCount);
 449     }
 450 
 451     public static void bitCount() {
 452         int failCount = 0;
 453 
 454         for (int i=0; i<SIZE*10; i++) {
 455             int x = rndSeed.getRandom().nextInt();
 456             BigInteger bigX = BigInteger.valueOf((long)x);
 457             int bit = (x < 0 ? 0 : 1);
 458             int tmp = x, bitCount = 0;
 459             for (int j=0; j<32; j++) {
 460                 bitCount += ((tmp & 1) == bit ? 1 : 0);
 461                 tmp >>= 1;
 462             }
 463 
 464             if (bigX.bitCount() != bitCount) {
 465                 //System.err.println(x+": "+bitCount+", "+bigX.bitCount());
 466                 failCount++;
 467             }
 468         }
 469         report("Bit Count", failCount);
 470     }
 471 
 472     public static void bitLength() {
 473         int failCount = 0;
 474 
 475         for (int i=0; i<SIZE*10; i++) {
 476             int x = rndSeed.getRandom().nextInt();
 477             BigInteger bigX = BigInteger.valueOf((long)x);
 478             int signBit = (x < 0 ? 0x80000000 : 0);
 479             int tmp = x, bitLength, j;
 480             for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
 481                 tmp <<= 1;
 482             bitLength = 32 - j;
 483 
 484             if (bigX.bitLength() != bitLength) {
 485                 //System.err.println(x+": "+bitLength+", "+bigX.bitLength());
 486                 failCount++;
 487             }
 488         }
 489 
 490         report("BitLength", failCount);
 491     }
 492 
 493     public static void bitOps(int order) {
 494         int failCount1 = 0, failCount2 = 0, failCount3 = 0;
 495 
 496         for (int i=0; i<SIZE*5; i++) {
 497             BigInteger x = fetchNumber(order);
 498             BigInteger y;
 499 
 500             // Test setBit and clearBit (and testBit)
 501             if (x.signum() < 0) {
 502                 y = BigInteger.valueOf(-1);
 503                 for (int j=0; j<x.bitLength(); j++)
 504                     if (!x.testBit(j))
 505                         y = y.clearBit(j);
 506             } else {
 507                 y = BigInteger.ZERO;
 508                 for (int j=0; j<x.bitLength(); j++)
 509                     if (x.testBit(j))
 510                         y = y.setBit(j);
 511             }
 512             if (!x.equals(y))
 513                 failCount1++;
 514 
 515             // Test flipBit (and testBit)
 516             y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
 517             for (int j=0; j<x.bitLength(); j++)
 518                 if (x.signum()<0  ^  x.testBit(j))
 519                     y = y.flipBit(j);
 520             if (!x.equals(y))
 521                 failCount2++;
 522         }
 523         report("clearBit/testBit for " + order + " bits", failCount1);
 524         report("flipBit/testBit for " + order + " bits", failCount2);
 525 
 526         for (int i=0; i<SIZE*5; i++) {
 527             BigInteger x = fetchNumber(order);
 528 
 529             // Test getLowestSetBit()
 530             int k = x.getLowestSetBit();
 531             if (x.signum() == 0) {
 532                 if (k != -1)
 533                     failCount3++;
 534             } else {
 535                 BigInteger z = x.and(x.negate());
 536                 int j;
 537                 for (j=0; j<z.bitLength() && !z.testBit(j); j++)
 538                     ;
 539                 if (k != j)
 540                     failCount3++;
 541             }
 542         }
 543         report("getLowestSetBit for " + order + " bits", failCount3);
 544     }
 545 
 546     public static void bitwise(int order) {
 547 
 548         // Test identity x^y == x|y &~ x&y
 549         int failCount = 0;
 550         for (int i=0; i<SIZE; i++) {
 551             BigInteger x = fetchNumber(order);
 552             BigInteger y = fetchNumber(order);
 553             BigInteger z = x.xor(y);
 554             BigInteger w = x.or(y).andNot(x.and(y));
 555             if (!z.equals(w))
 556                 failCount++;
 557         }
 558         report("Logic (^ | & ~) for " + order + " bits", failCount);
 559 
 560         // Test identity x &~ y == ~(~x | y)
 561         failCount = 0;
 562         for (int i=0; i<SIZE; i++) {
 563             BigInteger x = fetchNumber(order);
 564             BigInteger y = fetchNumber(order);
 565             BigInteger z = x.andNot(y);
 566             BigInteger w = x.not().or(y).not();
 567             if (!z.equals(w))
 568                 failCount++;
 569         }
 570         report("Logic (&~ | ~) for " + order + " bits", failCount);
 571     }
 572 
 573     public static void shift(int order) {
 574         int failCount1 = 0;
 575         int failCount2 = 0;
 576         int failCount3 = 0;
 577 
 578         for (int i=0; i<100; i++) {
 579             BigInteger x = fetchNumber(order);
 580             int n = Math.abs(rndSeed.getRandom().nextInt()%200);
 581 
 582             if (!x.shiftLeft(n).equals
 583                 (x.multiply(BigInteger.valueOf(2L).pow(n))))
 584                 failCount1++;
 585 
 586             BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n));
 587             BigInteger z = (x.signum()<0 && y[1].signum()!=0
 588                             ? y[0].subtract(BigInteger.ONE)
 589                             : y[0]);
 590 
 591             BigInteger b = x.shiftRight(n);
 592 
 593             if (!b.equals(z)) {
 594                 System.err.println("Input is "+x.toString(2));
 595                 System.err.println("shift is "+n);
 596 
 597                 System.err.println("Divided "+z.toString(2));
 598                 System.err.println("Shifted is "+b.toString(2));
 599                 if (b.toString().equals(z.toString()))
 600                     System.err.println("Houston, we have a problem.");
 601                 failCount2++;
 602             }
 603 
 604             if (!x.shiftLeft(n).shiftRight(n).equals(x))
 605                 failCount3++;
 606         }
 607         report("baz shiftLeft for " + order + " bits", failCount1);
 608         report("baz shiftRight for " + order + " bits", failCount2);
 609         report("baz shiftLeft/Right for " + order + " bits", failCount3);
 610     }
 611 
 612     public static void divideAndRemainder(int order) {
 613         int failCount1 = 0;
 614 
 615         for (int i=0; i<SIZE; i++) {
 616             BigInteger x = fetchNumber(order).abs();
 617             while(x.compareTo(BigInteger.valueOf(3L)) != 1)
 618                 x = fetchNumber(order).abs();
 619             BigInteger z = x.divide(BigInteger.valueOf(2L));
 620             BigInteger y[] = x.divideAndRemainder(x);
 621             if (!y[0].equals(BigInteger.ONE)) {
 622                 failCount1++;
 623                 System.err.println("fail1 x :"+x);
 624                 System.err.println("      y :"+y);
 625             }
 626             else if (!y[1].equals(BigInteger.ZERO)) {
 627                 failCount1++;
 628                 System.err.println("fail2 x :"+x);
 629                 System.err.println("      y :"+y);
 630             }
 631 
 632             y = x.divideAndRemainder(z);
 633             if (!y[0].equals(BigInteger.valueOf(2))) {
 634                 failCount1++;
 635                 System.err.println("fail3 x :"+x);
 636                 System.err.println("      y :"+y);
 637             }
 638         }
 639         report("divideAndRemainder for " + order + " bits", failCount1);
 640     }
 641 
 642     public static void stringConv() {
 643         int failCount = 0;
 644 
 645         // Generic string conversion.
 646         for (int i=0; i<100; i++) {
 647             byte xBytes[] = new byte[Math.abs(rndSeed.getRandom().nextInt())%100+1];
 648             rndSeed.getRandom().nextBytes(xBytes);
 649             BigInteger x = new BigInteger(xBytes);
 650 
 651             for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
 652                 String result = x.toString(radix);
 653                 BigInteger test = new BigInteger(result, radix);
 654                 if (!test.equals(x)) {
 655                     failCount++;
 656                     System.err.println("BigInteger toString: "+x);
 657                     System.err.println("Test: "+test);
 658                     System.err.println(radix);
 659                 }
 660             }
 661         }
 662 
 663         // String conversion straddling the Schoenhage algorithm crossover
 664         // threshold, and at twice and four times the threshold.
 665         for (int k = 0; k <= 2; k++) {
 666             int factor = 1 << k;
 667             int upper = factor * BITS_SCHOENHAGE_BASE + 33;
 668             int lower = upper - 35;
 669 
 670             for (int bits = upper; bits >= lower; bits--) {
 671                 for (int i = 0; i < 50; i++) {
 672                     BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, rndSeed.getRandom()));
 673 
 674                     for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
 675                         String result = x.toString(radix);
 676                         BigInteger test = new BigInteger(result, radix);
 677                         if (!test.equals(x)) {
 678                             failCount++;
 679                             System.err.println("BigInteger toString: " + x);
 680                             System.err.println("Test: " + test);
 681                             System.err.println(radix);
 682                         }
 683                     }
 684                 }
 685             }
 686         }
 687 
 688         report("String Conversion", failCount);
 689     }
 690 
 691     public static void byteArrayConv(int order) {
 692         int failCount = 0;
 693 
 694         for (int i=0; i<SIZE; i++) {
 695             BigInteger x = fetchNumber(order);
 696             while (x.equals(BigInteger.ZERO))
 697                 x = fetchNumber(order);
 698             BigInteger y = new BigInteger(x.toByteArray());
 699             if (!x.equals(y)) {
 700                 failCount++;
 701                 System.err.println("orig is "+x);
 702                 System.err.println("new is "+y);
 703             }
 704         }
 705         report("Array Conversion for " + order + " bits", failCount);
 706     }
 707 
 708     public static void modInv(int order) {
 709         int failCount = 0, successCount = 0, nonInvCount = 0;
 710 
 711         for (int i=0; i<SIZE; i++) {
 712             BigInteger x = fetchNumber(order);
 713             while(x.equals(BigInteger.ZERO))
 714                 x = fetchNumber(order);
 715             BigInteger m = fetchNumber(order).abs();
 716             while(m.compareTo(BigInteger.ONE) != 1)
 717                 m = fetchNumber(order).abs();
 718 
 719             try {
 720                 BigInteger inv = x.modInverse(m);
 721                 BigInteger prod = inv.multiply(x).remainder(m);
 722 
 723                 if (prod.signum() == -1)
 724                     prod = prod.add(m);
 725 
 726                 if (prod.equals(BigInteger.ONE))
 727                     successCount++;
 728                 else
 729                     failCount++;
 730             } catch(ArithmeticException e) {
 731                 nonInvCount++;
 732             }
 733         }
 734         report("Modular Inverse for " + order + " bits", failCount);
 735     }
 736 
 737     public static void modExp(int order1, int order2) {
 738         int failCount = 0;
 739 
 740         for (int i=0; i<SIZE/10; i++) {
 741             BigInteger m = fetchNumber(order1).abs();
 742             while(m.compareTo(BigInteger.ONE) != 1)
 743                 m = fetchNumber(order1).abs();
 744             BigInteger base = fetchNumber(order2);
 745             BigInteger exp = fetchNumber(8).abs();
 746 
 747             BigInteger z = base.modPow(exp, m);
 748             BigInteger w = base.pow(exp.intValue()).mod(m);
 749             if (!z.equals(w)) {
 750                 System.err.println("z is "+z);
 751                 System.err.println("w is "+w);
 752                 System.err.println("mod is "+m);
 753                 System.err.println("base is "+base);
 754                 System.err.println("exp is "+exp);
 755                 failCount++;
 756             }
 757         }
 758         report("Exponentiation I for " + order1 + " and " +
 759                order2 + " bits", failCount);
 760     }
 761 
 762     // This test is based on Fermat's theorem
 763     // which is not ideal because base must not be multiple of modulus
 764     // and modulus must be a prime or pseudoprime (Carmichael number)
 765     public static void modExp2(int order) {
 766         int failCount = 0;
 767 
 768         for (int i=0; i<10; i++) {
 769             BigInteger m = new BigInteger(100, 5, rndSeed.getRandom());
 770             while(m.compareTo(BigInteger.ONE) != 1)
 771                 m = new BigInteger(100, 5, rndSeed.getRandom());
 772             BigInteger exp = m.subtract(BigInteger.ONE);
 773             BigInteger base = fetchNumber(order).abs();
 774             while(base.compareTo(m) != -1)
 775                 base = fetchNumber(order).abs();
 776             while(base.equals(BigInteger.ZERO))
 777                 base = fetchNumber(order).abs();
 778 
 779             BigInteger one = base.modPow(exp, m);
 780             if (!one.equals(BigInteger.ONE)) {
 781                 System.err.println("m is "+m);
 782                 System.err.println("base is "+base);
 783                 System.err.println("exp is "+exp);
 784                 failCount++;
 785             }
 786         }
 787         report("Exponentiation II for " + order + " bits", failCount);
 788     }
 789 
 790     private static final int[] mersenne_powers = {
 791         521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
 792         21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
 793         1257787, 1398269, 2976221, 3021377, 6972593, 13466917 };
 794 
 795     private static final long[] carmichaels = {
 796       561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,
 797       62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,
 798       278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,
 799       225593397919L };
 800 
 801     // Note: testing the larger ones takes too long.
 802     private static final int NUM_MERSENNES_TO_TEST = 7;
 803     // Note: this constant used for computed Carmichaels, not the array above
 804     private static final int NUM_CARMICHAELS_TO_TEST = 5;
 805 
 806     private static final String[] customer_primes = {
 807         "120000000000000000000000000000000019",
 808         "633825300114114700748351603131",
 809         "1461501637330902918203684832716283019651637554291",
 810         "779626057591079617852292862756047675913380626199",
 811         "857591696176672809403750477631580323575362410491",
 812         "910409242326391377348778281801166102059139832131",
 813         "929857869954035706722619989283358182285540127919",
 814         "961301750640481375785983980066592002055764391999",
 815         "1267617700951005189537696547196156120148404630231",
 816         "1326015641149969955786344600146607663033642528339" };
 817 
 818     private static final BigInteger ZERO = BigInteger.ZERO;
 819     private static final BigInteger ONE = BigInteger.ONE;
 820     private static final BigInteger TWO = new BigInteger("2");
 821     private static final BigInteger SIX = new BigInteger("6");
 822     private static final BigInteger TWELVE = new BigInteger("12");
 823     private static final BigInteger EIGHTEEN = new BigInteger("18");
 824 
 825     public static void prime() {
 826         BigInteger p1, p2, c1;
 827         int failCount = 0;
 828 
 829         // Test consistency
 830         for(int i=0; i<10; i++) {
 831             p1 = BigInteger.probablePrime(100, rndSeed.getRandom());
 832             if (!p1.isProbablePrime(100)) {
 833                 System.err.println("Consistency "+p1.toString(16));
 834                 failCount++;
 835             }
 836         }
 837 
 838         // Test some known Mersenne primes (2^n)-1
 839         // The array holds the exponents, not the numbers being tested
 840         for (int i=0; i<NUM_MERSENNES_TO_TEST; i++) {
 841             p1 = new BigInteger("2");
 842             p1 = p1.pow(mersenne_powers[i]);
 843             p1 = p1.subtract(BigInteger.ONE);
 844             if (!p1.isProbablePrime(100)) {
 845                 System.err.println("Mersenne prime "+i+ " failed.");
 846                 failCount++;
 847             }
 848         }
 849 
 850         // Test some primes reported by customers as failing in the past
 851         for (int i=0; i<customer_primes.length; i++) {
 852             p1 = new BigInteger(customer_primes[i]);
 853             if (!p1.isProbablePrime(100)) {
 854                 System.err.println("Customer prime "+i+ " failed.");
 855                 failCount++;
 856             }
 857         }
 858 
 859         // Test some known Carmichael numbers.
 860         for (int i=0; i<carmichaels.length; i++) {
 861             c1 = BigInteger.valueOf(carmichaels[i]);
 862             if(c1.isProbablePrime(100)) {
 863                 System.err.println("Carmichael "+i+ " reported as prime.");
 864                 failCount++;
 865             }
 866         }
 867 
 868         // Test some computed Carmichael numbers.
 869         // Numbers of the form (6k+1)(12k+1)(18k+1) are Carmichael numbers if
 870         // each of the factors is prime
 871         int found = 0;
 872         BigInteger f1 = new BigInteger(40, 100, rndSeed.getRandom());
 873         while (found < NUM_CARMICHAELS_TO_TEST) {
 874             BigInteger k = null;
 875             BigInteger f2, f3;
 876             f1 = f1.nextProbablePrime();
 877             BigInteger[] result = f1.subtract(ONE).divideAndRemainder(SIX);
 878             if (result[1].equals(ZERO)) {
 879                 k = result[0];
 880                 f2 = k.multiply(TWELVE).add(ONE);
 881                 if (f2.isProbablePrime(100)) {
 882                     f3 = k.multiply(EIGHTEEN).add(ONE);
 883                     if (f3.isProbablePrime(100)) {
 884                         c1 = f1.multiply(f2).multiply(f3);
 885                         if (c1.isProbablePrime(100)) {
 886                             System.err.println("Computed Carmichael "
 887                                                +c1.toString(16));
 888                             failCount++;
 889                         }
 890                         found++;
 891                     }
 892                 }
 893             }
 894             f1 = f1.add(TWO);
 895         }
 896 
 897         // Test some composites that are products of 2 primes
 898         for (int i=0; i<50; i++) {
 899             p1 = BigInteger.probablePrime(100, rndSeed.getRandom());
 900             p2 = BigInteger.probablePrime(100, rndSeed.getRandom());
 901             c1 = p1.multiply(p2);
 902             if (c1.isProbablePrime(100)) {
 903                 System.err.println("Composite failed "+c1.toString(16));
 904                 failCount++;
 905             }
 906         }
 907 
 908         for (int i=0; i<4; i++) {
 909             p1 = BigInteger.probablePrime(600, rndSeed.getRandom());
 910             p2 = BigInteger.probablePrime(600, rndSeed.getRandom());
 911             c1 = p1.multiply(p2);
 912             if (c1.isProbablePrime(100)) {
 913                 System.err.println("Composite failed "+c1.toString(16));
 914                 failCount++;
 915             }
 916         }
 917 
 918         report("Prime", failCount);
 919     }
 920 
 921     private static final long[] primesTo100 = {
 922         2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
 923     };
 924 
 925     private static final long[] aPrimeSequence = {
 926         1999999003L, 1999999013L, 1999999049L, 1999999061L, 1999999081L,
 927         1999999087L, 1999999093L, 1999999097L, 1999999117L, 1999999121L,
 928         1999999151L, 1999999171L, 1999999207L, 1999999219L, 1999999271L,
 929         1999999321L, 1999999373L, 1999999423L, 1999999439L, 1999999499L,
 930         1999999553L, 1999999559L, 1999999571L, 1999999609L, 1999999613L,
 931         1999999621L, 1999999643L, 1999999649L, 1999999657L, 1999999747L,
 932         1999999763L, 1999999777L, 1999999811L, 1999999817L, 1999999829L,
 933         1999999853L, 1999999861L, 1999999871L, 1999999873
 934     };
 935 
 936     public static void nextProbablePrime() throws Exception {
 937         int failCount = 0;
 938         BigInteger p1, p2, p3;
 939         p1 = p2 = p3 = ZERO;
 940 
 941         // First test nextProbablePrime on the low range starting at zero
 942         for (int i=0; i<primesTo100.length; i++) {
 943             p1 = p1.nextProbablePrime();
 944             if (p1.longValue() != primesTo100[i]) {
 945                 System.err.println("low range primes failed");
 946                 System.err.println("p1 is "+p1);
 947                 System.err.println("expected "+primesTo100[i]);
 948                 failCount++;
 949             }
 950         }
 951 
 952         // Test nextProbablePrime on a relatively small, known prime sequence
 953         p1 = BigInteger.valueOf(aPrimeSequence[0]);
 954         for (int i=1; i<aPrimeSequence.length; i++) {
 955             p1 = p1.nextProbablePrime();
 956             if (p1.longValue() != aPrimeSequence[i]) {
 957                 System.err.println("prime sequence failed");
 958                 failCount++;
 959             }
 960         }
 961 
 962         // Next, pick some large primes, use nextProbablePrime to find the
 963         // next one, and make sure there are no primes in between
 964         for (int i=0; i<100; i+=10) {
 965             p1 = BigInteger.probablePrime(50 + i, rndSeed.getRandom());
 966             p2 = p1.add(ONE);
 967             p3 = p1.nextProbablePrime();
 968             while(p2.compareTo(p3) < 0) {
 969                 if (p2.isProbablePrime(100)){
 970                     System.err.println("nextProbablePrime failed");
 971                     System.err.println("along range "+p1.toString(16));
 972                     System.err.println("to "+p3.toString(16));
 973                     failCount++;
 974                     break;
 975                 }
 976                 p2 = p2.add(ONE);
 977             }
 978         }
 979 
 980         report("nextProbablePrime", failCount);
 981     }
 982 
 983     public static void serialize() throws Exception {
 984         int failCount = 0;
 985 
 986         String bitPatterns[] = {
 987              "ffffffff00000000ffffffff00000000ffffffff00000000",
 988              "ffffffffffffffffffffffff000000000000000000000000",
 989              "ffffffff0000000000000000000000000000000000000000",
 990              "10000000ffffffffffffffffffffffffffffffffffffffff",
 991              "100000000000000000000000000000000000000000000000",
 992              "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
 993             "-ffffffff00000000ffffffff00000000ffffffff00000000",
 994             "-ffffffffffffffffffffffff000000000000000000000000",
 995             "-ffffffff0000000000000000000000000000000000000000",
 996             "-10000000ffffffffffffffffffffffffffffffffffffffff",
 997             "-100000000000000000000000000000000000000000000000",
 998             "-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
 999         };
1000 
1001         for(int i = 0; i < bitPatterns.length; i++) {
1002             BigInteger b1 = new BigInteger(bitPatterns[i], 16);
1003             BigInteger b2 = null;
1004 
1005             File f = new File("serialtest");
1006 
1007             try (FileOutputStream fos = new FileOutputStream(f)) {
1008                 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
1009                     oos.writeObject(b1);
1010                     oos.flush();
1011                 }
1012 
1013                 try (FileInputStream fis = new FileInputStream(f);
1014                      ObjectInputStream ois = new ObjectInputStream(fis))
1015                 {
1016                     b2 = (BigInteger)ois.readObject();
1017                 }
1018 
1019                 if (!b1.equals(b2) ||
1020                     !b1.equals(b1.or(b2))) {
1021                     failCount++;
1022                     System.err.println("Serialized failed for hex " +
1023                                        b1.toString(16));
1024                 }
1025             }
1026             f.delete();
1027         }
1028 
1029         for(int i=0; i<10; i++) {
1030             BigInteger b1 = fetchNumber(rndSeed.getRandom().nextInt(100));
1031             BigInteger b2 = null;
1032             File f = new File("serialtest");
1033             try (FileOutputStream fos = new FileOutputStream(f)) {
1034                 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
1035                     oos.writeObject(b1);
1036                     oos.flush();
1037                 }
1038 
1039                 try (FileInputStream fis = new FileInputStream(f);
1040                      ObjectInputStream ois = new ObjectInputStream(fis))
1041                 {
1042                     b2 = (BigInteger)ois.readObject();
1043                 }
1044             }
1045 
1046             if (!b1.equals(b2) ||
1047                 !b1.equals(b1.or(b2)))
1048                 failCount++;
1049             f.delete();
1050         }
1051 
1052         report("Serialize", failCount);
1053     }
1054 
1055     /**
1056      * Main to interpret arguments and run several tests.
1057      *
1058      * Up to three arguments may be given to specify the SIZE of BigIntegers
1059      * used for call parameters 1, 2, and 3. The SIZE is interpreted as
1060      * the maximum number of decimal digits that the parameters will have.
1061      *
1062      */
1063     public static void main(String[] args) throws Exception {
1064         System.out.println("Random number generator seed = " + rndSeed.getSeed());
1065 
1066         // Some variables for sizing test numbers in bits
1067         int order1 = ORDER_MEDIUM;
1068         int order2 = ORDER_SMALL;
1069         int order3 = ORDER_KARATSUBA;
1070         int order4 = ORDER_TOOM_COOK;
1071 
1072         if (args.length >0)
1073             order1 = (int)((Integer.parseInt(args[0]))* 3.333);
1074         if (args.length >1)
1075             order2 = (int)((Integer.parseInt(args[1]))* 3.333);
1076         if (args.length >2)
1077             order3 = (int)((Integer.parseInt(args[2]))* 3.333);
1078         if (args.length >3)
1079             order4 = (int)((Integer.parseInt(args[3]))* 3.333);
1080 
1081         constructor();
1082 
1083         prime();
1084         nextProbablePrime();
1085 
1086         arithmetic(order1);   // small numbers
1087         arithmetic(order3);   // Karatsuba range
1088         arithmetic(order4);   // Toom-Cook / Burnikel-Ziegler range
1089 
1090         divideAndRemainder(order1);   // small numbers
1091         divideAndRemainder(order3);   // Karatsuba range
1092         divideAndRemainder(order4);   // Toom-Cook / Burnikel-Ziegler range
1093 
1094         pow(order1);
1095         pow(order3);
1096         pow(order4);
1097 
1098         square(ORDER_MEDIUM);
1099         square(ORDER_KARATSUBA_SQUARE);
1100         square(ORDER_TOOM_COOK_SQUARE);
1101 
1102         bitCount();
1103         bitLength();
1104         bitOps(order1);
1105         bitwise(order1);
1106 
1107         shift(order1);
1108 
1109         byteArrayConv(order1);
1110 
1111         modInv(order1);   // small numbers
1112         modInv(order3);   // Karatsuba range
1113         modInv(order4);   // Toom-Cook / Burnikel-Ziegler range
1114 
1115         modExp(order1, order2);
1116         modExp2(order1);
1117 
1118         stringConv();
1119         serialize();
1120 
1121         multiplyLarge();
1122         squareLarge();
1123         divideLarge();
1124 
1125         if (failure)
1126             throw new RuntimeException("Failure in BigIntegerTest.");
1127     }
1128 
1129     /*
1130      * Get a random or boundary-case number. This is designed to provide
1131      * a lot of numbers that will find failure points, such as max sized
1132      * numbers, empty BigIntegers, etc.
1133      *
1134      * If order is less than 2, order is changed to 2.
1135      */
1136     private static BigInteger fetchNumber(int order) {
1137         boolean negative = rndSeed.getRandom().nextBoolean();
1138         int numType = rndSeed.getRandom().nextInt(7);
1139         BigInteger result = null;
1140         if (order < 2) order = 2;
1141 
1142         switch (numType) {
1143             case 0: // Empty
1144                 result = BigInteger.ZERO;
1145                 break;
1146 
1147             case 1: // One
1148                 result = BigInteger.ONE;
1149                 break;
1150 
1151             case 2: // All bits set in number
1152                 int numBytes = (order+7)/8;
1153                 byte[] fullBits = new byte[numBytes];
1154                 for(int i=0; i<numBytes; i++)
1155                     fullBits[i] = (byte)0xff;
1156                 int excessBits = 8*numBytes - order;
1157                 fullBits[0] &= (1 << (8-excessBits)) - 1;
1158                 result = new BigInteger(1, fullBits);
1159                 break;
1160 
1161             case 3: // One bit in number
1162                 result = BigInteger.ONE.shiftLeft(rndSeed.getRandom().nextInt(order));
1163                 break;
1164 
1165             case 4: // Random bit density
1166                 byte[] val = new byte[(order+7)/8];
1167                 int iterations = rndSeed.getRandom().nextInt(order);
1168                 for (int i=0; i<iterations; i++) {
1169                     int bitIdx = rndSeed.getRandom().nextInt(order);
1170                     val[bitIdx/8] |= 1 << (bitIdx%8);
1171                 }
1172                 result = new BigInteger(1, val);
1173                 break;
1174             case 5: // Runs of consecutive ones and zeros
1175                 result = ZERO;
1176                 int remaining = order;
1177                 int bit = rndSeed.getRandom().nextInt(2);
1178                 while (remaining > 0) {
1179                     int runLength = Math.min(remaining, rndSeed.getRandom().nextInt(order));
1180                     result = result.shiftLeft(runLength);
1181                     if (bit > 0)
1182                         result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
1183                     remaining -= runLength;
1184                     bit = 1 - bit;
1185                 }
1186                 break;
1187 
1188             default: // random bits
1189                 result = new BigInteger(order, rndSeed.getRandom());
1190         }
1191 
1192         if (negative)
1193             result = result.negate();
1194 
1195         return result;
1196     }
1197 
1198     static void report(String testName, int failCount) {
1199         System.err.println(testName+": " +
1200                            (failCount==0 ? "Passed":"Failed("+failCount+")"));
1201         if (failCount > 0)
1202             failure = true;
1203     }
1204 }