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 = 50 ints = 1600 bits 60 // TOOM_COOK_THRESHOLD = 75 ints = 2400 bits 61 // KARATSUBA_SQUARE_THRESHOLD = 90 ints = 2880 bits 62 // TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits 63 // 64 // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits 65 // 66 // BURNIKEL_ZIEGLER_THRESHOLD = 50 ints = 1600 bits 67 // 68 static final int BITS_KARATSUBA = 1600; 69 static final int BITS_TOOM_COOK = 2400; 70 static final int BITS_KARATSUBA_SQUARE = 2880; 71 static final int BITS_TOOM_COOK_SQUARE = 4480; 72 static final int BITS_SCHOENHAGE_BASE = 256; 73 static final int BITS_BURNIKEL_ZIEGLER = 1600; 74 75 static final int ORDER_SMALL = 60; 76 static final int ORDER_MEDIUM = 100; 77 // #bits for testing Karatsuba and Burnikel-Ziegler 78 static final int ORDER_KARATSUBA = 1800; 79 // #bits for testing Toom-Cook 80 static final int ORDER_TOOM_COOK = 3000; 81 // #bits for testing Karatsuba squaring 82 static final int ORDER_KARATSUBA_SQUARE = 3200; 83 // #bits for testing Toom-Cook squaring 84 static final int ORDER_TOOM_COOK_SQUARE = 4600; 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 / Burnikel-Ziegler range 968 arithmetic(order4); // Toom-Cook range 969 970 divideAndRemainder(order1); // small numbers 971 divideAndRemainder(order3); // Karatsuba / Burnikel-Ziegler range 972 divideAndRemainder(order4); // Toom-Cook 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 / Burnikel-Ziegler range 993 modInv(order4); // Toom-Cook 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 }