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