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