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