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