/*
 * 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;
import java.lang.reflect.Array;
import java.lang.reflect.Constructor;
import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 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.
 *
 * Five arguments may be specified which give the number of
 * decimal digits you desire in the five 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        = 50  ints = 1600 bits
    // TOOM_COOK_THRESHOLD        = 75  ints = 2400 bits
    // KARATSUBA_SQUARE_THRESHOLD = 90  ints = 2880 bits
    // TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits
    //
    // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits
    //
    // BURNIKEL_ZIEGLER_THRESHOLD = 50  ints = 1600 bits
    //
    static final int BITS_KARATSUBA = 1600;
    static final int BITS_TOOM_COOK = 2400;
    static final int BITS_KARATSUBA_SQUARE = 2880;
    static final int BITS_TOOM_COOK_SQUARE = 4480;
    static final int BITS_SCHOENHAGE_BASE = 256;
    static final int BITS_BURNIKEL_ZIEGLER = 1600;

    static final int ORDER_SMALL = 60;
    static final int ORDER_MEDIUM = 100;
    // #bits for testing Karatsuba and Burnikel-Ziegler
    static final int ORDER_KARATSUBA = 1800;
    // #bits for testing Toom-Cook
    static final int ORDER_TOOM_COOK = 3000;
    // #bits for testing Schoenhage-Strassen and Barrett
    static final int ORDER_SS_BARRETT = 4000000;
    // #bits for testing Karatsuba squaring
    static final int ORDER_KARATSUBA_SQUARE = 3200;
    // #bits for testing Toom-Cook squaring
    static final int ORDER_TOOM_COOK_SQUARE = 4600;

    static final int SIZE = 1000; // numbers per batch
    static final int REDUCED_SIZE = 10;   // numbers per batch in the Schoenhage-Strassen/Barrett range

    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;

        int iterations = order<ORDER_SS_BARRETT ? SIZE : REDUCED_SIZE;
        for (int i=0; i<iterations; 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;

        int iterations = order<ORDER_SS_BARRETT ? SIZE : REDUCED_SIZE;
        for (int i=0; i<iterations; 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 and that {@code w}
     * and {@code z} are both over the threshold.  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 - 33);
        for (int i=0; i<SIZE; i++) {
            BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER - 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 = 17 + rnd.nextInt(16);
            int b = 1 + rnd.nextInt(16);
            BigInteger w = u.multiply(BigInteger.valueOf(1L << a));
            BigInteger z = v.multiply(BigInteger.valueOf(1L << b));

            BigInteger[] divideResult = u.divideAndRemainder(v);
            divideResult[0] = divideResult[0].multiply(BigInteger.valueOf(1L << (a - b)));
            divideResult[1] = divideResult[1].multiply(BigInteger.valueOf(1L << 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 schoenhageStrassen(int order) throws Exception {
        int failCount = 0;

        // test edge cases by multiplying numbers of the form 2^n + {-1,0,1}
        for (int i=0; i<10; i++) {
            int m = 1 << (23+rnd.nextInt(3));
            BigInteger x = ONE.shiftLeft(m);
            BigInteger xd = BigInteger.valueOf(rnd.nextInt(3) - 1);

            int n = 1 << (23+rnd.nextInt(3));
            BigInteger y = ONE.shiftLeft(n);
            BigInteger yd = BigInteger.valueOf(rnd.nextInt(3) - 1);

            BigInteger product = x.add(xd).multiply(y.add(yd));
            BigInteger expected = ONE.shiftLeft(m + n);
            expected = expected.add(yd.shiftLeft(m));   // add x.multiply(yd)
            expected = expected.add(xd.shiftLeft(n));   // add y.multiply(xd)
            expected = expected.add(xd.multiply(yd));

            if (!product.equals(expected)) {
                failCount++;
            }
        }

        // test edge cases by squaring numbers of the form 2^n + {-1,0,1}
        Method squareMethod = BigInteger.class.getDeclaredMethod("square");
        squareMethod.setAccessible(true);
        for (int i=0; i<10; i++) {
            int m = 1 << (23+rnd.nextInt(3));
            BigInteger x = ONE.shiftLeft(m);
            BigInteger xd = BigInteger.valueOf(rnd.nextInt(3) - 1);

            BigInteger square = (BigInteger)squareMethod.invoke(x.add(xd));
            BigInteger expected = ONE.shiftLeft(2 * m);
            expected = expected.add(xd.shiftLeft(m+1));   // add 2*x.multiply(xd)
            expected = expected.add(xd.multiply(xd));

            if (!square.equals(expected)) {
                failCount++;
            }
        }

        // test multithreaded multiplySchoenhageStrassen()
        Method multiplySchoenhageStrassenMethod = BigInteger.class.getDeclaredMethod("multiplySchoenhageStrassen", BigInteger.class, BigInteger.class, int.class);
        multiplySchoenhageStrassenMethod.setAccessible(true);
        for (int i=0; i<10; i++) {
            BigInteger a = new BigInteger(ORDER_SS_BARRETT, rnd);
            BigInteger b = new BigInteger(ORDER_SS_BARRETT, rnd);
            BigInteger c1 = a.multiply(b, 2+rnd.nextInt(10));
            BigInteger c2 = a.multiply(b);
            if (!c1.equals(c2))
                failCount++;
        }

        // verify that idft(dft(a)) = a
        Class<?> mutableModFnClass = Class.forName("java.math.MutableModFn");
        Constructor<?> mutableModFnCtor = mutableModFnClass.getDeclaredConstructor(long[].class);
        mutableModFnCtor.setAccessible(true);
        Field digitsField = mutableModFnClass.getDeclaredField("digits");
        digitsField.setAccessible(true);
        Method dftMethod = BigInteger.class.getDeclaredMethod("dft", Array.newInstance(mutableModFnClass, 0).getClass(), int.class, int.class);
        dftMethod.setAccessible(true);
        Method idftMethod = BigInteger.class.getDeclaredMethod("idft", Array.newInstance(mutableModFnClass, 0).getClass(), int.class, int.class);
        idftMethod.setAccessible(true);
        for (int k=0; k<100; k++) {
            int m = 10 + rnd.nextInt(8);
            int n = m/2 + 1;
            long[][] a = createRandomDftArray(m, n);
            long[][] aOrig = new long[a.length][];
            for (int i=0; i<a.length; i++)
                aOrig[i] = a[i].clone();
            int omega = m%2==0 ? 4 : 2;
            Object vector = Array.newInstance(mutableModFnClass, a.length);
            for (int i=0; i<a.length; i++)
                Array.set(vector, i, mutableModFnCtor.newInstance(a[i]));
            dftMethod.invoke(null, vector, omega, 1);
            idftMethod.invoke(null, vector, omega, 1);
            for (int i=0; i<aOrig.length; i++) {
                long[] origDigits = (long[])digitsField.get(Array.get(vector, i));
                if (!Arrays.equals(origDigits, aOrig[i]))
                    failCount++;
            }
        }

        // test MutableModFn.multiply()
        Method multiplyMethod = mutableModFnClass.getDeclaredMethod("multiply", mutableModFnClass);
        multiplyMethod.setAccessible(true);
        Method reduceMethod = mutableModFnClass.getDeclaredMethod("reduce");
        reduceMethod.setAccessible(true);
        Constructor<BigInteger> bigintCtor = BigInteger.class.getDeclaredConstructor(int.class, int[].class);
        bigintCtor.setAccessible(true);
        for (int i=0; i<100; i++) {
            int n = 6 + rnd.nextInt(10);
            long[] a = createRandomModFn(n);
            long[] b = createRandomModFn(n);

            int[] aInt = toIntArray(a);
            BigInteger aBigInt = bigintCtor.newInstance(1, aInt);
            int[] bInt = toIntArray(b);
            BigInteger bBigInt = bigintCtor.newInstance(1, bInt);
            BigInteger expected = aBigInt.multiply(bBigInt).mod(fermat(n));

            Object aMutable = mutableModFnCtor.newInstance(a);
            Object bMutable = mutableModFnCtor.newInstance(b);
            multiplyMethod.invoke(aMutable, bMutable);
            long[] c = (long[])digitsField.get(aMutable);
            int[] cInt = toIntArray(c);
            BigInteger actual = bigintCtor.newInstance(1, cInt);

            if (!actual.equals(expected))
                failCount++;
        }

        // test MutableModFn.square()
        Method squareModFnMethod = mutableModFnClass.getDeclaredMethod("square");
        squareModFnMethod.setAccessible(true);
        for (int i=0; i<100; i++) {
            int n = 6 + rnd.nextInt(10);
            long[] a = createRandomModFn(n);

            int[] aInt = toIntArray(a);
            BigInteger aBigInt = bigintCtor.newInstance(1, aInt);
            BigInteger expected = aBigInt.multiply(aBigInt).mod(fermat(n));

            Object aMutable = mutableModFnCtor.newInstance(a);
            squareModFnMethod.invoke(aMutable);
            long[] c = (long[])digitsField.get(aMutable);
            int[] cInt = toIntArray(c);
            BigInteger actual = bigintCtor.newInstance(1, cInt);

            if (!actual.equals(expected))
                failCount++;
        }

        // test MutableModFn.add()
        Method addMethod = mutableModFnClass.getDeclaredMethod("add", mutableModFnClass);
        addMethod.setAccessible(true);
        Method toIntArrayOddMethod = mutableModFnClass.getDeclaredMethod("toIntArrayOdd", long[].class);
        toIntArrayOddMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(10);
            long[] aArr = createRandomModFn(n);
            long[] bArr = createRandomModFn(n);

            int[] aArrInt = toIntArray(aArr);
            BigInteger a = bigintCtor.newInstance(1, aArrInt);
            int[] bArrInt = toIntArray(bArr);
            BigInteger b = bigintCtor.newInstance(1, bArrInt);
            BigInteger expected = a.add(b).mod(fermat(n));

            Object aMutable = mutableModFnCtor.newInstance(aArr);
            Object bMutable = mutableModFnCtor.newInstance(bArr);
            addMethod.invoke(aMutable, bMutable);
            aArr = (long[])digitsField.get(aMutable);
            aArrInt = toIntArray(aArr);
            BigInteger actual = bigintCtor.newInstance(1, aArrInt);

            if (!actual.equals(expected))
                failCount++;
        }

        // test MutableModFn.subtract()
        Method subtractMethod = mutableModFnClass.getDeclaredMethod("subtract", mutableModFnClass);
        subtractMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(10);
            long[] aArr = createRandomModFn(n);
            long[] bArr = createRandomModFn(n);

            int[] aArrInt = toIntArray(aArr);
            BigInteger a = bigintCtor.newInstance(1, aArrInt);
            int[] bArrInt = toIntArray(bArr);
            BigInteger b = bigintCtor.newInstance(1, bArrInt);
            BigInteger expected = a.subtract(b).mod(fermat(n));

            Object aMutable = mutableModFnCtor.newInstance(aArr);
            Object bMutable = mutableModFnCtor.newInstance(bArr);
            subtractMethod.invoke(aMutable, bMutable);
            aArr = (long[])digitsField.get(aMutable);
            aArrInt = toIntArray(aArr);
            BigInteger actual = bigintCtor.newInstance(1, aArrInt);

            if (!actual.equals(expected))
                failCount++;
        }

        // test MutableModFn.shiftLeft() against BigInteger.shiftLeft().mod(Fn)
        Method shiftLeftMethod = mutableModFnClass.getDeclaredMethod("shiftLeft", int.class, mutableModFnClass);
        shiftLeftMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(10);
            long[] aArr = createRandomModFn(n);
            long[] bArr = new long[aArr.length];
            int shiftDistance = rnd.nextInt(1 << (n+1));

            int[] aArrInt = toIntArray(aArr);
            BigInteger a = bigintCtor.newInstance(1, aArrInt);
            BigInteger expected = a.shiftLeft(shiftDistance).mod(fermat(n));

            Object aMutable = mutableModFnCtor.newInstance(aArr);
            Object bMutable = mutableModFnCtor.newInstance(bArr);
            shiftLeftMethod.invoke(aMutable, shiftDistance, bMutable);
            bArr = (long[])digitsField.get(bMutable);
            int[] bArrInt = toIntArray(bArr);
            BigInteger actual = bigintCtor.newInstance(1, bArrInt);

            if (!actual.equals(expected))
                failCount++;
        }

        // test MutableModFn.shiftRight() against BigInteger.multiply(2^(-shiftDistance)).mod(Fn)
        Method shiftRightMethod = mutableModFnClass.getDeclaredMethod("shiftRight", int.class, mutableModFnClass);
        shiftRightMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(10);
            long[] aArr = createRandomModFn(n);
            long[] bArr = new long[aArr.length];
            int shiftDistance = rnd.nextInt(1 << (n+1));

            BigInteger Fn = fermat(n);
            BigInteger inv2 = Fn.add(ONE).divide(TWO);   // 2^(-1) mod Fn
            BigInteger inv = inv2.modPow(BigInteger.valueOf(shiftDistance), Fn);   // 2^(-shiftDistance) mod Fn
            int[] aArrInt = toIntArray(aArr);
            BigInteger a = bigintCtor.newInstance(1, aArrInt);
            BigInteger expected = a.multiply(inv).mod(Fn);

            Object aMutable = mutableModFnCtor.newInstance(aArr);
            Object bMutable = mutableModFnCtor.newInstance(bArr);
            shiftRightMethod.invoke(aMutable, shiftDistance, bMutable);
            bArr = (long[])digitsField.get(bMutable);
            int[] bArrInt = toIntArray(bArr);
            BigInteger actual = bigintCtor.newInstance(1, bArrInt);

            if (!actual.equals(expected))
                failCount++;
        }

        // test MutableModFn.shiftLeft() and MutableModFn.shiftRight() by doing multiple shifts which should cancel each other out
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(10);
            int bitLen = (1<<n) + 1;
            // pick random shift amounts whose sum is zero
            List<Integer> amounts = new ArrayList<Integer>();
            int count = 1 + rnd.nextInt(20);
            int total = 0;
            for (int i = 0; i < count; i++) {
                int amount = rnd.nextInt(bitLen);
                amounts.add(amount);
                total += amount;
            }
            while (total > 0) {
                int amount = Math.min(rnd.nextInt(bitLen), total);
                amounts.add(-amount);
                total -= amount;
            }
            Collections.shuffle(amounts);

            long[] a = createRandomModFn(n);
            long[] aOrig = a.clone();
            Object aMutable = mutableModFnCtor.newInstance(a);
            for (int amount: amounts) {
                Object bMutable = mutableModFnCtor.newInstance(new long[a.length]);
                if (amount > 0)
                    shiftLeftMethod.invoke(aMutable, amount, bMutable);
                else
                    shiftRightMethod.invoke(aMutable, -amount, bMutable);
                aMutable = bMutable;
            }
            reduceMethod.invoke(aMutable);
            a = (long[])digitsField.get(aMutable);

            if (!Arrays.equals(a, aOrig))
                failCount++;
        }

        // test MutableModFn.reduce()
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(15);
            long[] a = createRandomModFn(n);
            a[0] = rnd.nextLong();   // test all long values, not just 0 and 1
            long[] aOrig = a.clone();
            BigInteger Fn = fermat(n);

            int[] aOrigInt = toIntArray(aOrig);
            BigInteger expected = bigintCtor.newInstance(1, aOrigInt).mod(Fn);

            Object aMutable = mutableModFnCtor.newInstance(a);
            reduceMethod.invoke(aMutable);
            a = (long[])digitsField.get(aMutable);
            int[] aInt = toIntArray(a);
            BigInteger actual = bigintCtor.newInstance(1, aInt);

            if (!actual.equals(expected))
                failCount++;
            if (actual.compareTo(Fn) >= 0)
                failCount++;
        }

        // test MutableModFn.reduceWide()
        Method reduceWideMethod = mutableModFnClass.getDeclaredMethod("reduceWide", long[].class);
        reduceWideMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(15);
            int len = 1 << (n + 1 - 6);
            long[] a = createRandomArrayLong(len);
            long[] aOrig = a.clone();
            BigInteger Fn = fermat(n);

            int[] aOrigInt = toIntArray(aOrig);
            BigInteger expected = bigintCtor.newInstance(1, aOrigInt).mod(Fn);

            reduceWideMethod.invoke(null, a);
            int[] aInt = (int[])toIntArrayOddMethod.invoke(null, a);
            BigInteger actual = bigintCtor.newInstance(1, aInt);

            if (!actual.equals(expected))
                failCount++;
            if (actual.compareTo(Fn) >= 0)
                failCount++;
        }

        // test MutableModFn.toIntArray() and MutableModFn.toLongArray()
        Method toLongArrayEvenMethod = mutableModFnClass.getDeclaredMethod("toLongArrayEven", int[].class);
        toLongArrayEvenMethod.setAccessible(true);
        for (int i=0; i<1000; i++) {
            int n = 2 + rnd.nextInt(1000);
            int[] a = createRandomArray(n);
            long[] b = n%2==0 ? (long[])toLongArrayEvenMethod.invoke(null, a) : toLongArrayOdd(a);
            int[] c = n%2==0 ? toIntArray(b) : (int[])toIntArrayOddMethod.invoke(null, b);
            if (!Arrays.equals(a, c))
                failCount++;
        }

        // test addModPow2
        Method addModPow2Method = BigInteger.class.getDeclaredMethod("addModPow2", int[].class, int[].class, int.class);
        addModPow2Method.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(15);
            int len = 1 << (n + 1 - 5);
            int[] aArr = createRandomArray(len);
            aArr[0] &= 0x7FFFFFFF; // make sure the most significant int doesn't overflow
            BigInteger a = bigintCtor.newInstance(1, aArr);
            int[] bArr = createRandomArray(len);
            bArr[0] &= 0x7FFFFFFF; // make sure the most significant int doesn't overflow
            BigInteger b = bigintCtor.newInstance(1, bArr);
            int numBits = rnd.nextInt(n);
            BigInteger pow2 = BigInteger.valueOf(1<<numBits);
            BigInteger expected = a.add(b).mod(pow2);
            addModPow2Method.invoke(null, aArr, bArr, numBits);
            BigInteger actual = bigintCtor.newInstance(1, aArr);
            if (!actual.equals(expected))
                failCount++;
        }

        // test subModPow2
        Method subModPow2Method = BigInteger.class.getDeclaredMethod("subModPow2", int[].class, int[].class, int.class);
        subModPow2Method.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 6 + rnd.nextInt(15);
            int len = 1 << (n + 1 - 5);
            int[] aArr = createRandomArray(len);
            aArr[0] &= 0x7FFFFFFF; // make sure the most significant int doesn't overflow
            BigInteger a = bigintCtor.newInstance(1, aArr);
            int[] bArr = createRandomArray(len);
            bArr[0] &= 0x7FFFFFFF; // make sure the most significant int doesn't overflow
            BigInteger b = bigintCtor.newInstance(1, bArr);
            int numBits = rnd.nextInt(n);
            BigInteger pow2 = BigInteger.valueOf(1<<numBits);
            BigInteger expected = a.subtract(b).mod(pow2);
            subModPow2Method.invoke(null, aArr, bArr, numBits);
            BigInteger actual = bigintCtor.newInstance(1, aArr);
            if (!actual.equals(expected))
                failCount++;
        }

        // test splitBits
        Method splitBitsMethod = BigInteger.class.getDeclaredMethod("splitBits", int[].class, int.class);
        splitBitsMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int n = 1 + rnd.nextInt(1000);
            int[] aArr = createRandomArray(n);
            BigInteger actual = bigintCtor.newInstance(1, aArr);
            int pieceSize = 1 + smallRandom(n-1, rnd);
            int[][] pieces = (int[][])splitBitsMethod.invoke(null, aArr, pieceSize);
            BigInteger expected = ZERO;
            for (int i=pieces.length-1; i>=0; i--) {
                int[] piece = pieces[i];
                BigInteger pieceBigInt = bigintCtor.newInstance(1, piece);
                expected = expected.shiftLeft(pieceSize).add(pieceBigInt);
            }
            if (!actual.equals(expected))
                failCount++;
        }

        // test addShifted
        Method addShiftedMethod = BigInteger.class.getDeclaredMethod("addShifted", int[].class, int[].class, int.class);
        addShiftedMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int[] aArr = createRandomArray(1 + rnd.nextInt(1000));
            BigInteger a = bigintCtor.newInstance(1, aArr);
            int offset = rnd.nextInt(aArr.length);
            int[] bArr = createRandomArray(1 + rnd.nextInt(1000));
            BigInteger b = bigintCtor.newInstance(1, bArr);
            addShiftedMethod.invoke(null, aArr, bArr, offset);
            BigInteger actual = bigintCtor.newInstance(1, aArr);
            BigInteger mask = ONE.shiftLeft(aArr.length*32).subtract(ONE);
            BigInteger expected = a.add(b.shiftLeft(offset*32)).and(mask);
            if (!actual.equals(expected))
                failCount++;
        }

        // test appendBits
        Method appendBitsMethod = BigInteger.class.getDeclaredMethod("appendBits", int[].class, int.class, int[].class, int.class, int.class);
        appendBitsMethod.setAccessible(true);
        for (int k = 0; k<100; k++) {
            int[] src = createRandomArray(1 + rnd.nextInt(1000));
            BigInteger srcBigInt = bigintCtor.newInstance(1, src);
            int[] dest = new int[src.length];
            int valBits = 1 + smallRandom(src.length*32-1, rnd);
            int padBits = 1 + smallRandom(src.length*32-1, rnd);
            BigInteger mask = ONE.shiftLeft(valBits).subtract(ONE);
            int srcIndex = 0;
            int destBits = 0;
            BigInteger expected = ZERO;
            while (srcIndex+(valBits+31)/32<src.length && destBits+valBits+padBits<dest.length*32) {
                expected = expected.add(srcBigInt.shiftRight(srcIndex*32).and(mask).shiftLeft(destBits));
                appendBitsMethod.invoke(null, dest, destBits, src, srcIndex, valBits);
                srcIndex += (valBits+31) / 32;
                destBits += valBits + padBits;
            }
            if (destBits > 0)
                dest = Arrays.copyOfRange(dest, dest.length-(destBits+31)/32, dest.length);
            BigInteger actual = bigintCtor.newInstance(1, dest);
            if (!actual.equals(expected))
                failCount++;
        }

        report("Schoenhage-Strassen", failCount);
    }

    // like Random.nextInt(int) but favors small numbers
    private static int smallRandom(int n, Random rnd) {
        return (int)(n * Math.pow(rnd.nextDouble(), 5));
    }

    private static int[] createRandomArray(int length) {
        int[] a = new int[length];
        for (int i=0; i<a.length; i++)
            a[i] = rnd.nextInt();
        return a;
    }

    private static long[] createRandomArrayLong(int length) {
        long[] a = new long[length];
        for (int i=0; i<a.length; i++)
            a[i] = rnd.nextLong();
        return a;
    }

    /**
     * Returns a random number modulo 2^2^n+1. The results are biased
     * towards the special case 2^2^n.
     * @param n must be 6 or greater
     * @return an array of length ceil((2^n+1) / 64.0)
     */
    private static long[] createRandomModFn(int n) {
        int length = (1<<(n-6)) + 1;
        long[] a = new long[length];
        if (rnd.nextInt(5) == 0)
            a[0] = 1;   // return 2^2^n
        else
            // leave a[0] zero, make everything else random
            for (int i=1; i<a.length; i++)
                a[i] = rnd.nextLong();
        return a;
    }

    private static long[][] createRandomDftArray(int m, int n) {
        int numElements = m%2==0 ? 1<<n : 1<<(n+1);
        numElements /= 2;
        long[][] a = new long[numElements][];
        for (int i=0; i<a.length; i++)
            a[i] = createRandomModFn(n);
        return a;
    }

    private static int[] toIntArray(long[] digits) {
        int[] intDigits = new int[digits.length*2];
        for (int i=0; i<digits.length; i++) {
            intDigits[2*i] = (int)(digits[i] >>> 32);
            intDigits[2*i+1] = (int)(digits[i] & -1);
        }
        return intDigits;
    }

    /** digits.length must be an odd number */
    public static long[] toLongArrayOdd(int[] digits) {
        long[] longDigits = new long[digits.length/2+1];
        longDigits[0] = digits[0];
        for (int i=1; i<longDigits.length; i++)
            longDigits[i] = (((long)digits[2*i-1])<<32) | (digits[2*i]&0xFFFFFFFFL);
        return longDigits;
    }

    /** Returns the n-th Fermat number */
    private static BigInteger fermat(int n) throws Exception {
        Constructor<BigInteger> bigintCtor = BigInteger.class.getDeclaredConstructor(int.class, int[].class);
        bigintCtor.setAccessible(true);
        int length = (1<<(n-5)) + 1;
        int[] FnArr = new int[length];
        FnArr[0] = 1;
        FnArr[FnArr.length-1] = 1;
        return bigintCtor.newInstance(1, FnArr);
    }

    private static void inverse() throws Exception {
        int failCount = 0;

        Method inverseMethod = BigInteger.class.getDeclaredMethod("inverse", int.class, int.class);
        inverseMethod.setAccessible(true);
        for (int i=0; i<REDUCED_SIZE; i++) {
            BigInteger a;
            do {
                a = fetchNumber(ORDER_SS_BARRETT);
            } while (a.compareTo(ZERO) <= 0);
            int n = rnd.nextInt(a.bitLength());
            BigInteger expected = BigInteger.ONE.shiftLeft(a.bitLength()+n).divide(a);
            BigInteger actual = (BigInteger)inverseMethod.invoke(a, n, 1+rnd.nextInt(4));
            if (actual.subtract(expected).abs().compareTo(ONE) > 1)
                failCount++;
        }
        report("Inverse", 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;

        int iterations = order<ORDER_SS_BARRETT ? SIZE : REDUCED_SIZE;
        for (int i=0; i<iterations; 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;

        int iterations = order<ORDER_SS_BARRETT ? SIZE : REDUCED_SIZE;
        for (int i=0; i<iterations; 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;
        int order5 = ORDER_SS_BARRETT;

        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);
        if (args.length >4)
            order5 = (int)((Integer.parseInt(args[4]))* 3.333);

        prime();
        nextProbablePrime();

        schoenhageStrassen(order5);

        inverse();

        arithmetic(order1);   // small numbers
        arithmetic(order3);   // Karatsuba range
        arithmetic(order4);   // Toom-Cook / Burnikel-Ziegler range
        arithmetic(order5);   // SS/Barrett range

        divideAndRemainder(order1);   // small numbers
        divideAndRemainder(order3);   // Karatsuba range
        divideAndRemainder(order4);   // Toom-Cook / Burnikel-Ziegler range
        divideAndRemainder(order5);   // SS/Barrett range

        pow(order1);
        pow(order3);
        pow(order4);

        square(ORDER_MEDIUM);
        square(ORDER_KARATSUBA_SQUARE);
        square(ORDER_TOOM_COOK_SQUARE);
        square(order5);   // SS/Barrett range

        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;
    }
}