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