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