| /* |
| * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| /* |
| * @test |
| * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 |
| * @summary tests methods in BigInteger |
| * @run main/timeout=400 BigIntegerTest |
| * @author madbot |
| */ |
| |
| import java.io.File; |
| import java.io.FileInputStream; |
| import java.io.FileOutputStream; |
| import java.io.ObjectInputStream; |
| import java.io.ObjectOutputStream; |
| import java.math.BigInteger; |
| import java.util.Random; |
| |
| /** |
| * This is a simple test class created to ensure that the results |
| * generated by BigInteger adhere to certain identities. Passing |
| * this test is a strong assurance that the BigInteger operations |
| * are working correctly. |
| * |
| * Four arguments may be specified which give the number of |
| * decimal digits you desire in the four batches of test numbers. |
| * |
| * The tests are performed on arrays of random numbers which are |
| * generated by a Random class as well as special cases which |
| * throw in boundary numbers such as 0, 1, maximum sized, etc. |
| * |
| */ |
| public class BigIntegerTest { |
| // |
| // Bit large number thresholds based on the int thresholds |
| // defined in BigInteger itself: |
| // |
| // KARATSUBA_THRESHOLD = 80 ints = 2560 bits |
| // TOOM_COOK_THRESHOLD = 240 ints = 7680 bits |
| // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits |
| // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits |
| // |
| // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits |
| // |
| // BURNIKEL_ZIEGLER_THRESHOLD = 80 ints = 2560 bits |
| // |
| static final int BITS_KARATSUBA = 2560; |
| static final int BITS_TOOM_COOK = 7680; |
| static final int BITS_KARATSUBA_SQUARE = 4096; |
| static final int BITS_TOOM_COOK_SQUARE = 6912; |
| static final int BITS_SCHOENHAGE_BASE = 640; |
| static final int BITS_BURNIKEL_ZIEGLER = 2560; |
| static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280; |
| |
| static final int ORDER_SMALL = 60; |
| static final int ORDER_MEDIUM = 100; |
| // #bits for testing Karatsuba |
| static final int ORDER_KARATSUBA = 2760; |
| // #bits for testing Toom-Cook and Burnikel-Ziegler |
| static final int ORDER_TOOM_COOK = 8000; |
| // #bits for testing Karatsuba squaring |
| static final int ORDER_KARATSUBA_SQUARE = 4200; |
| // #bits for testing Toom-Cook squaring |
| static final int ORDER_TOOM_COOK_SQUARE = 7000; |
| |
| static final int SIZE = 1000; // numbers per batch |
| |
| static Random rnd = new Random(); |
| static boolean failure = false; |
| |
| public static void pow(int order) { |
| int failCount1 = 0; |
| |
| for (int i=0; i<SIZE; i++) { |
| // Test identity x^power == x*x*x ... *x |
| int power = rnd.nextInt(6) + 2; |
| BigInteger x = fetchNumber(order); |
| BigInteger y = x.pow(power); |
| BigInteger z = x; |
| |
| for (int j=1; j<power; j++) |
| z = z.multiply(x); |
| |
| if (!y.equals(z)) |
| failCount1++; |
| } |
| report("pow for " + order + " bits", failCount1); |
| } |
| |
| public static void square(int order) { |
| int failCount1 = 0; |
| |
| for (int i=0; i<SIZE; i++) { |
| // Test identity x^2 == x*x |
| BigInteger x = fetchNumber(order); |
| BigInteger xx = x.multiply(x); |
| BigInteger x2 = x.pow(2); |
| |
| if (!x2.equals(xx)) |
| failCount1++; |
| } |
| report("square for " + order + " bits", failCount1); |
| } |
| |
| public static void arithmetic(int order) { |
| int failCount = 0; |
| |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(order); |
| while(x.compareTo(BigInteger.ZERO) != 1) |
| x = fetchNumber(order); |
| BigInteger y = fetchNumber(order/2); |
| while(x.compareTo(y) == -1) |
| y = fetchNumber(order/2); |
| if (y.equals(BigInteger.ZERO)) |
| y = y.add(BigInteger.ONE); |
| |
| // Test identity ((x/y))*y + x%y - x == 0 |
| // using separate divide() and remainder() |
| BigInteger baz = x.divide(y); |
| baz = baz.multiply(y); |
| baz = baz.add(x.remainder(y)); |
| baz = baz.subtract(x); |
| if (!baz.equals(BigInteger.ZERO)) |
| failCount++; |
| } |
| report("Arithmetic I for " + order + " bits", failCount); |
| |
| failCount = 0; |
| for (int i=0; i<100; i++) { |
| BigInteger x = fetchNumber(order); |
| while(x.compareTo(BigInteger.ZERO) != 1) |
| x = fetchNumber(order); |
| BigInteger y = fetchNumber(order/2); |
| while(x.compareTo(y) == -1) |
| y = fetchNumber(order/2); |
| if (y.equals(BigInteger.ZERO)) |
| y = y.add(BigInteger.ONE); |
| |
| // Test identity ((x/y))*y + x%y - x == 0 |
| // using divideAndRemainder() |
| BigInteger baz[] = x.divideAndRemainder(y); |
| baz[0] = baz[0].multiply(y); |
| baz[0] = baz[0].add(baz[1]); |
| baz[0] = baz[0].subtract(x); |
| if (!baz[0].equals(BigInteger.ZERO)) |
| failCount++; |
| } |
| report("Arithmetic II for " + order + " bits", failCount); |
| } |
| |
| /** |
| * Sanity test for Karatsuba and 3-way Toom-Cook multiplication. |
| * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds, |
| * construct two factors each with a mag array one element shorter than the |
| * threshold, and with the most significant bit set and the rest of the bits |
| * random. Each of these numbers will therefore be below the threshold but |
| * if shifted left be above the threshold. Call the numbers 'u' and 'v' and |
| * define random shifts 'a' and 'b' in the range [1,32]. Then we have the |
| * identity |
| * <pre> |
| * (u << a)*(v << b) = (u*v) << (a + b) |
| * </pre> |
| * For Karatsuba multiplication, the right hand expression will be evaluated |
| * using the standard naive algorithm, and the left hand expression using |
| * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right |
| * hand expression will be evaluated using Karatsuba multiplication, and the |
| * left hand expression using 3-way Toom-Cook multiplication. |
| */ |
| public static void multiplyLarge() { |
| int failCount = 0; |
| |
| BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1); |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1); |
| BigInteger u = base.add(x); |
| int a = 1 + rnd.nextInt(31); |
| BigInteger w = u.shiftLeft(a); |
| |
| BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1); |
| BigInteger v = base.add(y); |
| int b = 1 + rnd.nextInt(32); |
| BigInteger z = v.shiftLeft(b); |
| |
| BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b); |
| BigInteger karatsubaMultiplyResult = w.multiply(z); |
| |
| if (!multiplyResult.equals(karatsubaMultiplyResult)) { |
| failCount++; |
| } |
| } |
| |
| report("multiplyLarge Karatsuba", failCount); |
| |
| failCount = 0; |
| base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA); |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1); |
| BigInteger u = base.add(x); |
| BigInteger u2 = u.shiftLeft(1); |
| BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1); |
| BigInteger v = base.add(y); |
| BigInteger v2 = v.shiftLeft(1); |
| |
| BigInteger multiplyResult = u.multiply(v).shiftLeft(2); |
| BigInteger toomCookMultiplyResult = u2.multiply(v2); |
| |
| if (!multiplyResult.equals(toomCookMultiplyResult)) { |
| failCount++; |
| } |
| } |
| |
| report("multiplyLarge Toom-Cook", failCount); |
| } |
| |
| /** |
| * Sanity test for Karatsuba and 3-way Toom-Cook squaring. |
| * This test is analogous to {@link AbstractMethodError#multiplyLarge} |
| * with both factors being equal. The squaring methods will not be tested |
| * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether |
| * the parameter is the same instance on which the method is being invoked |
| * and calls <code>square()</code> accordingly. |
| */ |
| public static void squareLarge() { |
| int failCount = 0; |
| |
| BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1); |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1); |
| BigInteger u = base.add(x); |
| int a = 1 + rnd.nextInt(31); |
| BigInteger w = u.shiftLeft(a); |
| |
| BigInteger squareResult = u.multiply(u).shiftLeft(2*a); |
| BigInteger karatsubaSquareResult = w.multiply(w); |
| |
| if (!squareResult.equals(karatsubaSquareResult)) { |
| failCount++; |
| } |
| } |
| |
| report("squareLarge Karatsuba", failCount); |
| |
| failCount = 0; |
| base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE); |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1); |
| BigInteger u = base.add(x); |
| int a = 1 + rnd.nextInt(31); |
| BigInteger w = u.shiftLeft(a); |
| |
| BigInteger squareResult = u.multiply(u).shiftLeft(2*a); |
| BigInteger toomCookSquareResult = w.multiply(w); |
| |
| if (!squareResult.equals(toomCookSquareResult)) { |
| failCount++; |
| } |
| } |
| |
| report("squareLarge Toom-Cook", failCount); |
| } |
| |
| /** |
| * Sanity test for Burnikel-Ziegler division. The Burnikel-Ziegler division |
| * algorithm is used when each of the dividend and the divisor has at least |
| * a specified number of ints in its representation. This test is based on |
| * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)} |
| * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if |
| * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then |
| * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test |
| * ensures that {@code v} is just under the B-Z threshold, that {@code z} is |
| * over the threshold and {@code w} is much larger than {@code z}. This |
| * implies that {@code u/v} uses the standard division algorithm and |
| * {@code w/z} uses the B-Z algorithm. The results of the two algorithms |
| * are then compared using the observation described in the foregoing and |
| * if they are not equal a failure is logged. |
| */ |
| public static void divideLarge() { |
| int failCount = 0; |
| |
| BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33); |
| for (int i=0; i<SIZE; i++) { |
| BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, rnd); |
| BigInteger v = base.add(addend); |
| |
| BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1))); |
| |
| if(rnd.nextBoolean()) { |
| u = u.negate(); |
| } |
| if(rnd.nextBoolean()) { |
| v = v.negate(); |
| } |
| |
| int a = BITS_BURNIKEL_ZIEGLER_OFFSET + rnd.nextInt(16); |
| int b = 1 + rnd.nextInt(16); |
| BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a)); |
| BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b)); |
| |
| BigInteger[] divideResult = u.divideAndRemainder(v); |
| divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b)); |
| divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b)); |
| BigInteger[] bzResult = w.divideAndRemainder(z); |
| |
| if (divideResult[0].compareTo(bzResult[0]) != 0 || |
| divideResult[1].compareTo(bzResult[1]) != 0) { |
| failCount++; |
| } |
| } |
| |
| report("divideLarge", failCount); |
| } |
| |
| public static void bitCount() { |
| int failCount = 0; |
| |
| for (int i=0; i<SIZE*10; i++) { |
| int x = rnd.nextInt(); |
| BigInteger bigX = BigInteger.valueOf((long)x); |
| int bit = (x < 0 ? 0 : 1); |
| int tmp = x, bitCount = 0; |
| for (int j=0; j<32; j++) { |
| bitCount += ((tmp & 1) == bit ? 1 : 0); |
| tmp >>= 1; |
| } |
| |
| if (bigX.bitCount() != bitCount) { |
| //System.err.println(x+": "+bitCount+", "+bigX.bitCount()); |
| failCount++; |
| } |
| } |
| report("Bit Count", failCount); |
| } |
| |
| public static void bitLength() { |
| int failCount = 0; |
| |
| for (int i=0; i<SIZE*10; i++) { |
| int x = rnd.nextInt(); |
| BigInteger bigX = BigInteger.valueOf((long)x); |
| int signBit = (x < 0 ? 0x80000000 : 0); |
| int tmp = x, bitLength, j; |
| for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++) |
| tmp <<= 1; |
| bitLength = 32 - j; |
| |
| if (bigX.bitLength() != bitLength) { |
| //System.err.println(x+": "+bitLength+", "+bigX.bitLength()); |
| failCount++; |
| } |
| } |
| |
| report("BitLength", failCount); |
| } |
| |
| public static void bitOps(int order) { |
| int failCount1 = 0, failCount2 = 0, failCount3 = 0; |
| |
| for (int i=0; i<SIZE*5; i++) { |
| BigInteger x = fetchNumber(order); |
| BigInteger y; |
| |
| // Test setBit and clearBit (and testBit) |
| if (x.signum() < 0) { |
| y = BigInteger.valueOf(-1); |
| for (int j=0; j<x.bitLength(); j++) |
| if (!x.testBit(j)) |
| y = y.clearBit(j); |
| } else { |
| y = BigInteger.ZERO; |
| for (int j=0; j<x.bitLength(); j++) |
| if (x.testBit(j)) |
| y = y.setBit(j); |
| } |
| if (!x.equals(y)) |
| failCount1++; |
| |
| // Test flipBit (and testBit) |
| y = BigInteger.valueOf(x.signum()<0 ? -1 : 0); |
| for (int j=0; j<x.bitLength(); j++) |
| if (x.signum()<0 ^ x.testBit(j)) |
| y = y.flipBit(j); |
| if (!x.equals(y)) |
| failCount2++; |
| } |
| report("clearBit/testBit for " + order + " bits", failCount1); |
| report("flipBit/testBit for " + order + " bits", failCount2); |
| |
| for (int i=0; i<SIZE*5; i++) { |
| BigInteger x = fetchNumber(order); |
| |
| // Test getLowestSetBit() |
| int k = x.getLowestSetBit(); |
| if (x.signum() == 0) { |
| if (k != -1) |
| failCount3++; |
| } else { |
| BigInteger z = x.and(x.negate()); |
| int j; |
| for (j=0; j<z.bitLength() && !z.testBit(j); j++) |
| ; |
| if (k != j) |
| failCount3++; |
| } |
| } |
| report("getLowestSetBit for " + order + " bits", failCount3); |
| } |
| |
| public static void bitwise(int order) { |
| |
| // Test identity x^y == x|y &~ x&y |
| int failCount = 0; |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(order); |
| BigInteger y = fetchNumber(order); |
| BigInteger z = x.xor(y); |
| BigInteger w = x.or(y).andNot(x.and(y)); |
| if (!z.equals(w)) |
| failCount++; |
| } |
| report("Logic (^ | & ~) for " + order + " bits", failCount); |
| |
| // Test identity x &~ y == ~(~x | y) |
| failCount = 0; |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(order); |
| BigInteger y = fetchNumber(order); |
| BigInteger z = x.andNot(y); |
| BigInteger w = x.not().or(y).not(); |
| if (!z.equals(w)) |
| failCount++; |
| } |
| report("Logic (&~ | ~) for " + order + " bits", failCount); |
| } |
| |
| public static void shift(int order) { |
| int failCount1 = 0; |
| int failCount2 = 0; |
| int failCount3 = 0; |
| |
| for (int i=0; i<100; i++) { |
| BigInteger x = fetchNumber(order); |
| int n = Math.abs(rnd.nextInt()%200); |
| |
| if (!x.shiftLeft(n).equals |
| (x.multiply(BigInteger.valueOf(2L).pow(n)))) |
| failCount1++; |
| |
| BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n)); |
| BigInteger z = (x.signum()<0 && y[1].signum()!=0 |
| ? y[0].subtract(BigInteger.ONE) |
| : y[0]); |
| |
| BigInteger b = x.shiftRight(n); |
| |
| if (!b.equals(z)) { |
| System.err.println("Input is "+x.toString(2)); |
| System.err.println("shift is "+n); |
| |
| System.err.println("Divided "+z.toString(2)); |
| System.err.println("Shifted is "+b.toString(2)); |
| if (b.toString().equals(z.toString())) |
| System.err.println("Houston, we have a problem."); |
| failCount2++; |
| } |
| |
| if (!x.shiftLeft(n).shiftRight(n).equals(x)) |
| failCount3++; |
| } |
| report("baz shiftLeft for " + order + " bits", failCount1); |
| report("baz shiftRight for " + order + " bits", failCount2); |
| report("baz shiftLeft/Right for " + order + " bits", failCount3); |
| } |
| |
| public static void divideAndRemainder(int order) { |
| int failCount1 = 0; |
| |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(order).abs(); |
| while(x.compareTo(BigInteger.valueOf(3L)) != 1) |
| x = fetchNumber(order).abs(); |
| BigInteger z = x.divide(BigInteger.valueOf(2L)); |
| BigInteger y[] = x.divideAndRemainder(x); |
| if (!y[0].equals(BigInteger.ONE)) { |
| failCount1++; |
| System.err.println("fail1 x :"+x); |
| System.err.println(" y :"+y); |
| } |
| else if (!y[1].equals(BigInteger.ZERO)) { |
| failCount1++; |
| System.err.println("fail2 x :"+x); |
| System.err.println(" y :"+y); |
| } |
| |
| y = x.divideAndRemainder(z); |
| if (!y[0].equals(BigInteger.valueOf(2))) { |
| failCount1++; |
| System.err.println("fail3 x :"+x); |
| System.err.println(" y :"+y); |
| } |
| } |
| report("divideAndRemainder for " + order + " bits", failCount1); |
| } |
| |
| public static void stringConv() { |
| int failCount = 0; |
| |
| // Generic string conversion. |
| for (int i=0; i<100; i++) { |
| byte xBytes[] = new byte[Math.abs(rnd.nextInt())%100+1]; |
| rnd.nextBytes(xBytes); |
| BigInteger x = new BigInteger(xBytes); |
| |
| for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) { |
| String result = x.toString(radix); |
| BigInteger test = new BigInteger(result, radix); |
| if (!test.equals(x)) { |
| failCount++; |
| System.err.println("BigInteger toString: "+x); |
| System.err.println("Test: "+test); |
| System.err.println(radix); |
| } |
| } |
| } |
| |
| // String conversion straddling the Schoenhage algorithm crossover |
| // threshold, and at twice and four times the threshold. |
| for (int k = 0; k <= 2; k++) { |
| int factor = 1 << k; |
| int upper = factor * BITS_SCHOENHAGE_BASE + 33; |
| int lower = upper - 35; |
| |
| for (int bits = upper; bits >= lower; bits--) { |
| for (int i = 0; i < 50; i++) { |
| BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, rnd)); |
| |
| for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) { |
| String result = x.toString(radix); |
| BigInteger test = new BigInteger(result, radix); |
| if (!test.equals(x)) { |
| failCount++; |
| System.err.println("BigInteger toString: " + x); |
| System.err.println("Test: " + test); |
| System.err.println(radix); |
| } |
| } |
| } |
| } |
| } |
| |
| report("String Conversion", failCount); |
| } |
| |
| public static void byteArrayConv(int order) { |
| int failCount = 0; |
| |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(order); |
| while (x.equals(BigInteger.ZERO)) |
| x = fetchNumber(order); |
| BigInteger y = new BigInteger(x.toByteArray()); |
| if (!x.equals(y)) { |
| failCount++; |
| System.err.println("orig is "+x); |
| System.err.println("new is "+y); |
| } |
| } |
| report("Array Conversion for " + order + " bits", failCount); |
| } |
| |
| public static void modInv(int order) { |
| int failCount = 0, successCount = 0, nonInvCount = 0; |
| |
| for (int i=0; i<SIZE; i++) { |
| BigInteger x = fetchNumber(order); |
| while(x.equals(BigInteger.ZERO)) |
| x = fetchNumber(order); |
| BigInteger m = fetchNumber(order).abs(); |
| while(m.compareTo(BigInteger.ONE) != 1) |
| m = fetchNumber(order).abs(); |
| |
| try { |
| BigInteger inv = x.modInverse(m); |
| BigInteger prod = inv.multiply(x).remainder(m); |
| |
| if (prod.signum() == -1) |
| prod = prod.add(m); |
| |
| if (prod.equals(BigInteger.ONE)) |
| successCount++; |
| else |
| failCount++; |
| } catch(ArithmeticException e) { |
| nonInvCount++; |
| } |
| } |
| report("Modular Inverse for " + order + " bits", failCount); |
| } |
| |
| public static void modExp(int order1, int order2) { |
| int failCount = 0; |
| |
| for (int i=0; i<SIZE/10; i++) { |
| BigInteger m = fetchNumber(order1).abs(); |
| while(m.compareTo(BigInteger.ONE) != 1) |
| m = fetchNumber(order1).abs(); |
| BigInteger base = fetchNumber(order2); |
| BigInteger exp = fetchNumber(8).abs(); |
| |
| BigInteger z = base.modPow(exp, m); |
| BigInteger w = base.pow(exp.intValue()).mod(m); |
| if (!z.equals(w)) { |
| System.err.println("z is "+z); |
| System.err.println("w is "+w); |
| System.err.println("mod is "+m); |
| System.err.println("base is "+base); |
| System.err.println("exp is "+exp); |
| failCount++; |
| } |
| } |
| report("Exponentiation I for " + order1 + " and " + |
| order2 + " bits", failCount); |
| } |
| |
| // This test is based on Fermat's theorem |
| // which is not ideal because base must not be multiple of modulus |
| // and modulus must be a prime or pseudoprime (Carmichael number) |
| public static void modExp2(int order) { |
| int failCount = 0; |
| |
| for (int i=0; i<10; i++) { |
| BigInteger m = new BigInteger(100, 5, rnd); |
| while(m.compareTo(BigInteger.ONE) != 1) |
| m = new BigInteger(100, 5, rnd); |
| BigInteger exp = m.subtract(BigInteger.ONE); |
| BigInteger base = fetchNumber(order).abs(); |
| while(base.compareTo(m) != -1) |
| base = fetchNumber(order).abs(); |
| while(base.equals(BigInteger.ZERO)) |
| base = fetchNumber(order).abs(); |
| |
| BigInteger one = base.modPow(exp, m); |
| if (!one.equals(BigInteger.ONE)) { |
| System.err.println("m is "+m); |
| System.err.println("base is "+base); |
| System.err.println("exp is "+exp); |
| failCount++; |
| } |
| } |
| report("Exponentiation II for " + order + " bits", failCount); |
| } |
| |
| private static final int[] mersenne_powers = { |
| 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, |
| 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, |
| 1257787, 1398269, 2976221, 3021377, 6972593, 13466917 }; |
| |
| private static final long[] carmichaels = { |
| 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633, |
| 62745,63973,75361,101101,115921,126217,162401,172081,188461,252601, |
| 278545,294409,314821,334153,340561,399001,410041,449065,488881,512461, |
| 225593397919L }; |
| |
| // Note: testing the larger ones takes too long. |
| private static final int NUM_MERSENNES_TO_TEST = 7; |
| // Note: this constant used for computed Carmichaels, not the array above |
| private static final int NUM_CARMICHAELS_TO_TEST = 5; |
| |
| private static final String[] customer_primes = { |
| "120000000000000000000000000000000019", |
| "633825300114114700748351603131", |
| "1461501637330902918203684832716283019651637554291", |
| "779626057591079617852292862756047675913380626199", |
| "857591696176672809403750477631580323575362410491", |
| "910409242326391377348778281801166102059139832131", |
| "929857869954035706722619989283358182285540127919", |
| "961301750640481375785983980066592002055764391999", |
| "1267617700951005189537696547196156120148404630231", |
| "1326015641149969955786344600146607663033642528339" }; |
| |
| private static final BigInteger ZERO = BigInteger.ZERO; |
| private static final BigInteger ONE = BigInteger.ONE; |
| private static final BigInteger TWO = new BigInteger("2"); |
| private static final BigInteger SIX = new BigInteger("6"); |
| private static final BigInteger TWELVE = new BigInteger("12"); |
| private static final BigInteger EIGHTEEN = new BigInteger("18"); |
| |
| public static void prime() { |
| BigInteger p1, p2, c1; |
| int failCount = 0; |
| |
| // Test consistency |
| for(int i=0; i<10; i++) { |
| p1 = BigInteger.probablePrime(100, rnd); |
| if (!p1.isProbablePrime(100)) { |
| System.err.println("Consistency "+p1.toString(16)); |
| failCount++; |
| } |
| } |
| |
| // Test some known Mersenne primes (2^n)-1 |
| // The array holds the exponents, not the numbers being tested |
| for (int i=0; i<NUM_MERSENNES_TO_TEST; i++) { |
| p1 = new BigInteger("2"); |
| p1 = p1.pow(mersenne_powers[i]); |
| p1 = p1.subtract(BigInteger.ONE); |
| if (!p1.isProbablePrime(100)) { |
| System.err.println("Mersenne prime "+i+ " failed."); |
| failCount++; |
| } |
| } |
| |
| // Test some primes reported by customers as failing in the past |
| for (int i=0; i<customer_primes.length; i++) { |
| p1 = new BigInteger(customer_primes[i]); |
| if (!p1.isProbablePrime(100)) { |
| System.err.println("Customer prime "+i+ " failed."); |
| failCount++; |
| } |
| } |
| |
| // Test some known Carmichael numbers. |
| for (int i=0; i<carmichaels.length; i++) { |
| c1 = BigInteger.valueOf(carmichaels[i]); |
| if(c1.isProbablePrime(100)) { |
| System.err.println("Carmichael "+i+ " reported as prime."); |
| failCount++; |
| } |
| } |
| |
| // Test some computed Carmichael numbers. |
| // Numbers of the form (6k+1)(12k+1)(18k+1) are Carmichael numbers if |
| // each of the factors is prime |
| int found = 0; |
| BigInteger f1 = new BigInteger(40, 100, rnd); |
| while (found < NUM_CARMICHAELS_TO_TEST) { |
| BigInteger k = null; |
| BigInteger f2, f3; |
| f1 = f1.nextProbablePrime(); |
| BigInteger[] result = f1.subtract(ONE).divideAndRemainder(SIX); |
| if (result[1].equals(ZERO)) { |
| k = result[0]; |
| f2 = k.multiply(TWELVE).add(ONE); |
| if (f2.isProbablePrime(100)) { |
| f3 = k.multiply(EIGHTEEN).add(ONE); |
| if (f3.isProbablePrime(100)) { |
| c1 = f1.multiply(f2).multiply(f3); |
| if (c1.isProbablePrime(100)) { |
| System.err.println("Computed Carmichael " |
| +c1.toString(16)); |
| failCount++; |
| } |
| found++; |
| } |
| } |
| } |
| f1 = f1.add(TWO); |
| } |
| |
| // Test some composites that are products of 2 primes |
| for (int i=0; i<50; i++) { |
| p1 = BigInteger.probablePrime(100, rnd); |
| p2 = BigInteger.probablePrime(100, rnd); |
| c1 = p1.multiply(p2); |
| if (c1.isProbablePrime(100)) { |
| System.err.println("Composite failed "+c1.toString(16)); |
| failCount++; |
| } |
| } |
| |
| for (int i=0; i<4; i++) { |
| p1 = BigInteger.probablePrime(600, rnd); |
| p2 = BigInteger.probablePrime(600, rnd); |
| c1 = p1.multiply(p2); |
| if (c1.isProbablePrime(100)) { |
| System.err.println("Composite failed "+c1.toString(16)); |
| failCount++; |
| } |
| } |
| |
| report("Prime", failCount); |
| } |
| |
| private static final long[] primesTo100 = { |
| 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 |
| }; |
| |
| private static final long[] aPrimeSequence = { |
| 1999999003L, 1999999013L, 1999999049L, 1999999061L, 1999999081L, |
| 1999999087L, 1999999093L, 1999999097L, 1999999117L, 1999999121L, |
| 1999999151L, 1999999171L, 1999999207L, 1999999219L, 1999999271L, |
| 1999999321L, 1999999373L, 1999999423L, 1999999439L, 1999999499L, |
| 1999999553L, 1999999559L, 1999999571L, 1999999609L, 1999999613L, |
| 1999999621L, 1999999643L, 1999999649L, 1999999657L, 1999999747L, |
| 1999999763L, 1999999777L, 1999999811L, 1999999817L, 1999999829L, |
| 1999999853L, 1999999861L, 1999999871L, 1999999873 |
| }; |
| |
| public static void nextProbablePrime() throws Exception { |
| int failCount = 0; |
| BigInteger p1, p2, p3; |
| p1 = p2 = p3 = ZERO; |
| |
| // First test nextProbablePrime on the low range starting at zero |
| for (int i=0; i<primesTo100.length; i++) { |
| p1 = p1.nextProbablePrime(); |
| if (p1.longValue() != primesTo100[i]) { |
| System.err.println("low range primes failed"); |
| System.err.println("p1 is "+p1); |
| System.err.println("expected "+primesTo100[i]); |
| failCount++; |
| } |
| } |
| |
| // Test nextProbablePrime on a relatively small, known prime sequence |
| p1 = BigInteger.valueOf(aPrimeSequence[0]); |
| for (int i=1; i<aPrimeSequence.length; i++) { |
| p1 = p1.nextProbablePrime(); |
| if (p1.longValue() != aPrimeSequence[i]) { |
| System.err.println("prime sequence failed"); |
| failCount++; |
| } |
| } |
| |
| // Next, pick some large primes, use nextProbablePrime to find the |
| // next one, and make sure there are no primes in between |
| for (int i=0; i<100; i+=10) { |
| p1 = BigInteger.probablePrime(50 + i, rnd); |
| p2 = p1.add(ONE); |
| p3 = p1.nextProbablePrime(); |
| while(p2.compareTo(p3) < 0) { |
| if (p2.isProbablePrime(100)){ |
| System.err.println("nextProbablePrime failed"); |
| System.err.println("along range "+p1.toString(16)); |
| System.err.println("to "+p3.toString(16)); |
| failCount++; |
| break; |
| } |
| p2 = p2.add(ONE); |
| } |
| } |
| |
| report("nextProbablePrime", failCount); |
| } |
| |
| public static void serialize() throws Exception { |
| int failCount = 0; |
| |
| String bitPatterns[] = { |
| "ffffffff00000000ffffffff00000000ffffffff00000000", |
| "ffffffffffffffffffffffff000000000000000000000000", |
| "ffffffff0000000000000000000000000000000000000000", |
| "10000000ffffffffffffffffffffffffffffffffffffffff", |
| "100000000000000000000000000000000000000000000000", |
| "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", |
| "-ffffffff00000000ffffffff00000000ffffffff00000000", |
| "-ffffffffffffffffffffffff000000000000000000000000", |
| "-ffffffff0000000000000000000000000000000000000000", |
| "-10000000ffffffffffffffffffffffffffffffffffffffff", |
| "-100000000000000000000000000000000000000000000000", |
| "-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |
| }; |
| |
| for(int i = 0; i < bitPatterns.length; i++) { |
| BigInteger b1 = new BigInteger(bitPatterns[i], 16); |
| BigInteger b2 = null; |
| |
| File f = new File("serialtest"); |
| |
| try (FileOutputStream fos = new FileOutputStream(f)) { |
| try (ObjectOutputStream oos = new ObjectOutputStream(fos)) { |
| oos.writeObject(b1); |
| oos.flush(); |
| } |
| |
| try (FileInputStream fis = new FileInputStream(f); |
| ObjectInputStream ois = new ObjectInputStream(fis)) |
| { |
| b2 = (BigInteger)ois.readObject(); |
| } |
| |
| if (!b1.equals(b2) || |
| !b1.equals(b1.or(b2))) { |
| failCount++; |
| System.err.println("Serialized failed for hex " + |
| b1.toString(16)); |
| } |
| } |
| f.delete(); |
| } |
| |
| for(int i=0; i<10; i++) { |
| BigInteger b1 = fetchNumber(rnd.nextInt(100)); |
| BigInteger b2 = null; |
| File f = new File("serialtest"); |
| try (FileOutputStream fos = new FileOutputStream(f)) { |
| try (ObjectOutputStream oos = new ObjectOutputStream(fos)) { |
| oos.writeObject(b1); |
| oos.flush(); |
| } |
| |
| try (FileInputStream fis = new FileInputStream(f); |
| ObjectInputStream ois = new ObjectInputStream(fis)) |
| { |
| b2 = (BigInteger)ois.readObject(); |
| } |
| } |
| |
| if (!b1.equals(b2) || |
| !b1.equals(b1.or(b2))) |
| failCount++; |
| f.delete(); |
| } |
| |
| report("Serialize", failCount); |
| } |
| |
| /** |
| * Main to interpret arguments and run several tests. |
| * |
| * Up to three arguments may be given to specify the SIZE of BigIntegers |
| * used for call parameters 1, 2, and 3. The SIZE is interpreted as |
| * the maximum number of decimal digits that the parameters will have. |
| * |
| */ |
| public static void main(String[] args) throws Exception { |
| |
| // Some variables for sizing test numbers in bits |
| int order1 = ORDER_MEDIUM; |
| int order2 = ORDER_SMALL; |
| int order3 = ORDER_KARATSUBA; |
| int order4 = ORDER_TOOM_COOK; |
| |
| if (args.length >0) |
| order1 = (int)((Integer.parseInt(args[0]))* 3.333); |
| if (args.length >1) |
| order2 = (int)((Integer.parseInt(args[1]))* 3.333); |
| if (args.length >2) |
| order3 = (int)((Integer.parseInt(args[2]))* 3.333); |
| if (args.length >3) |
| order4 = (int)((Integer.parseInt(args[3]))* 3.333); |
| |
| prime(); |
| nextProbablePrime(); |
| |
| arithmetic(order1); // small numbers |
| arithmetic(order3); // Karatsuba range |
| arithmetic(order4); // Toom-Cook / Burnikel-Ziegler range |
| |
| divideAndRemainder(order1); // small numbers |
| divideAndRemainder(order3); // Karatsuba range |
| divideAndRemainder(order4); // Toom-Cook / Burnikel-Ziegler range |
| |
| pow(order1); |
| pow(order3); |
| pow(order4); |
| |
| square(ORDER_MEDIUM); |
| square(ORDER_KARATSUBA_SQUARE); |
| square(ORDER_TOOM_COOK_SQUARE); |
| |
| bitCount(); |
| bitLength(); |
| bitOps(order1); |
| bitwise(order1); |
| |
| shift(order1); |
| |
| byteArrayConv(order1); |
| |
| modInv(order1); // small numbers |
| modInv(order3); // Karatsuba range |
| modInv(order4); // Toom-Cook / Burnikel-Ziegler range |
| |
| modExp(order1, order2); |
| modExp2(order1); |
| |
| stringConv(); |
| serialize(); |
| |
| multiplyLarge(); |
| squareLarge(); |
| divideLarge(); |
| |
| if (failure) |
| throw new RuntimeException("Failure in BigIntegerTest."); |
| } |
| |
| /* |
| * Get a random or boundary-case number. This is designed to provide |
| * a lot of numbers that will find failure points, such as max sized |
| * numbers, empty BigIntegers, etc. |
| * |
| * If order is less than 2, order is changed to 2. |
| */ |
| private static BigInteger fetchNumber(int order) { |
| boolean negative = rnd.nextBoolean(); |
| int numType = rnd.nextInt(7); |
| BigInteger result = null; |
| if (order < 2) order = 2; |
| |
| switch (numType) { |
| case 0: // Empty |
| result = BigInteger.ZERO; |
| break; |
| |
| case 1: // One |
| result = BigInteger.ONE; |
| break; |
| |
| case 2: // All bits set in number |
| int numBytes = (order+7)/8; |
| byte[] fullBits = new byte[numBytes]; |
| for(int i=0; i<numBytes; i++) |
| fullBits[i] = (byte)0xff; |
| int excessBits = 8*numBytes - order; |
| fullBits[0] &= (1 << (8-excessBits)) - 1; |
| result = new BigInteger(1, fullBits); |
| break; |
| |
| case 3: // One bit in number |
| result = BigInteger.ONE.shiftLeft(rnd.nextInt(order)); |
| break; |
| |
| case 4: // Random bit density |
| byte[] val = new byte[(order+7)/8]; |
| int iterations = rnd.nextInt(order); |
| for (int i=0; i<iterations; i++) { |
| int bitIdx = rnd.nextInt(order); |
| val[bitIdx/8] |= 1 << (bitIdx%8); |
| } |
| result = new BigInteger(1, val); |
| break; |
| case 5: // Runs of consecutive ones and zeros |
| result = ZERO; |
| int remaining = order; |
| int bit = rnd.nextInt(2); |
| while (remaining > 0) { |
| int runLength = Math.min(remaining, rnd.nextInt(order)); |
| result = result.shiftLeft(runLength); |
| if (bit > 0) |
| result = result.add(ONE.shiftLeft(runLength).subtract(ONE)); |
| remaining -= runLength; |
| bit = 1 - bit; |
| } |
| break; |
| |
| default: // random bits |
| result = new BigInteger(order, rnd); |
| } |
| |
| if (negative) |
| result = result.negate(); |
| |
| return result; |
| } |
| |
| static void report(String testName, int failCount) { |
| System.err.println(testName+": " + |
| (failCount==0 ? "Passed":"Failed("+failCount+")")); |
| if (failCount > 0) |
| failure = true; |
| } |
| } |
