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 }