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