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