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