// Copy remainder of longer number        while (bigIndex > 0)            result[--bigIndex] = big[bigIndex];        return result;    }    /**     * Returns a BigInteger whose value is <tt>(this * val)</tt>.     *     * @param  val value to be multiplied by this BigInteger.     * @return <tt>this * val</tt>     */    public BigInteger multiply(BigInteger val) {        if (signum == 0 || val.signum==0)	    return ZERO;                int[] result = multiplyToLen(mag, mag.length,                                      val.mag, val.mag.length, null);        result = trustedStripLeadingZeroInts(result);        return new BigInteger(result, signum*val.signum);    }    /**     * Multiplies int arrays x and y to the specified lengths and places     * the result into z.     */    private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {        int xstart = xlen - 1;        int ystart = ylen - 1;        if (z == null || z.length < (xlen+ ylen))            z = new int[xlen+ylen];        long carry = 0;        for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) {            long product = (y[j] & LONG_MASK) *                           (x[xstart] & LONG_MASK) + carry;            z[k] = (int)product;            carry = product >>> 32;        }        z[xstart] = (int)carry;        for (int i = xstart-1; i >= 0; i--) {            carry = 0;            for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {                long product = (y[j] & LONG_MASK) *                                (x[i] & LONG_MASK) +                                (z[k] & LONG_MASK) + carry;                z[k] = (int)product;                carry = product >>> 32;            }            z[i] = (int)carry;        }        return z;    }    /**     * Returns a BigInteger whose value is <tt>(this<sup>2</sup>)</tt>.     *     * @return <tt>this<sup>2</sup></tt>     */    private BigInteger square() {        if (signum == 0)	    return ZERO;        int[] z = squareToLen(mag, mag.length, null);        return new BigInteger(trustedStripLeadingZeroInts(z), 1);    }    /**     * Squares the contents of the int array x. The result is placed into the     * int array z.  The contents of x are not changed.     */    private static final int[] squareToLen(int[] x, int len, int[] z) {        /*         * The algorithm used here is adapted from Colin Plumb's C library.         * Technique: Consider the partial products in the multiplication         * of "abcde" by itself:         *         *               a  b  c  d  e         *            *  a  b  c  d  e         *          ==================         *              ae be ce de ee         *           ad bd cd dd de         *        ac bc cc cd ce         *     ab bb bc bd be         *  aa ab ac ad ae         *         * Note that everything above the main diagonal:         *              ae be ce de = (abcd) * e         *           ad bd cd       = (abc) * d         *        ac bc             = (ab) * c         *     ab                   = (a) * b         *         * is a copy of everything below the main diagonal:         *                       de         *                 cd ce         *           bc bd be         *     ab ac ad ae         *         * Thus, the sum is 2 * (off the diagonal) + diagonal.         *         * This is accumulated beginning with the diagonal (which         * consist of the squares of the digits of the input), which is then         * divided by two, the off-diagonal added, and multiplied by two         * again.  The low bit is simply a copy of the low bit of the         * input, so it doesn't need special care.         */        int zlen = len << 1;        if (z == null || z.length < zlen)            z = new int[zlen];                // Store the squares, right shifted one bit (i.e., divided by 2)        int lastProductLowWord = 0;        for (int j=0, i=0; j<len; j++) {            long piece = (x[j] & LONG_MASK);            long product = piece * piece;            z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33);            z[i++] = (int)(product >>> 1);            lastProductLowWord = (int)product;        }        // Add in off-diagonal sums        for (int i=len, offset=1; i>0; i--, offset+=2) {            int t = x[i-1];            t = mulAdd(z, x, offset, i-1, t);            addOne(z, offset-1, i, t);        }        // Shift back up and set low bit        primitiveLeftShift(z, zlen, 1);        z[zlen-1] |= x[len-1] & 1;        return z;    }    /**     * Returns a BigInteger whose value is <tt>(this / val)</tt>.     *     * @param  val value by which this BigInteger is to be divided.     * @return <tt>this / val</tt>     * @throws ArithmeticException <tt>val==0</tt>     */    public BigInteger divide(BigInteger val) {        MutableBigInteger q = new MutableBigInteger(),                          r = new MutableBigInteger(),                          a = new MutableBigInteger(this.mag),                          b = new MutableBigInteger(val.mag);        a.divide(b, q, r);        return new BigInteger(q, this.signum * val.signum);    }    /**     * Returns an array of two BigIntegers containing <tt>(this / val)</tt>     * followed by <tt>(this % val)</tt>.     *     * @param  val value by which this BigInteger is to be divided, and the     *	       remainder computed.     * @return an array of two BigIntegers: the quotient <tt>(this / val)</tt>     *	       is the initial element, and the remainder <tt>(this % val)</tt>     *	       is the final element.     * @throws ArithmeticException <tt>val==0</tt>     */    public BigInteger[] divideAndRemainder(BigInteger val) {        BigInteger[] result = new BigInteger[2];        MutableBigInteger q = new MutableBigInteger(),                          r = new MutableBigInteger(),                          a = new MutableBigInteger(this.mag),                          b = new MutableBigInteger(val.mag);        a.divide(b, q, r);        result[0] = new BigInteger(q, this.signum * val.signum);        result[1] = new BigInteger(r, this.signum);        return result;    }    /**     * Returns a BigInteger whose value is <tt>(this % val)</tt>.     *     * @param  val value by which this BigInteger is to be divided, and the     *	       remainder computed.     * @return <tt>this % val</tt>     * @throws ArithmeticException <tt>val==0</tt>     */    public BigInteger remainder(BigInteger val) {        MutableBigInteger q = new MutableBigInteger(),                          r = new MutableBigInteger(),                          a = new MutableBigInteger(this.mag),                          b = new MutableBigInteger(val.mag);        a.divide(b, q, r);        return new BigInteger(r, this.signum);    }    /**     * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.     * Note that <tt>exponent</tt> is an integer rather than a BigInteger.     *     * @param  exponent exponent to which this BigInteger is to be raised.     * @return <tt>this<sup>exponent</sup></tt>     * @throws ArithmeticException <tt>exponent</tt> is negative.  (This would     *	       cause the operation to yield a non-integer value.)     */    public BigInteger pow(int exponent) {	if (exponent < 0)	    throw new ArithmeticException("Negative exponent");	if (signum==0)	    return (exponent==0 ? ONE : this);	// Perform exponentiation using repeated squaring trick        int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);	int[] baseToPow2 = this.mag;        int[] result = {1};	while (exponent != 0) {	    if ((exponent & 1)==1) {		result = multiplyToLen(result, result.length,                                        baseToPow2, baseToPow2.length, null);		result = trustedStripLeadingZeroInts(result);	    }	    if ((exponent >>>= 1) != 0) {                baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);		baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);	    }	}	return new BigInteger(result, newSign);    }    /**     * Returns a BigInteger whose value is the greatest common divisor of     * <tt>abs(this)</tt> and <tt>abs(val)</tt>.  Returns 0 if     * <tt>this==0 &amp;&amp; val==0</tt>.     *     * @param  val value with which the GCD is to be computed.     * @return <tt>GCD(abs(this), abs(val))</tt>     */    public BigInteger gcd(BigInteger val) {        if (val.signum == 0)	    return this.abs();	else if (this.signum == 0)	    return val.abs();        MutableBigInteger a = new MutableBigInteger(this);        MutableBigInteger b = new MutableBigInteger(val);        MutableBigInteger result = a.hybridGCD(b);        return new BigInteger(result, 1);    }    /**     * Left shift int array a up to len by n bits. Returns the array that     * results from the shift since space may have to be reallocated.     */    private static int[] leftShift(int[] a, int len, int n) {        int nInts = n >>> 5;        int nBits = n&0x1F;        int bitsInHighWord = bitLen(a[0]);                // If shift can be done without recopy, do so        if (n <= (32-bitsInHighWord)) {            primitiveLeftShift(a, len, nBits);            return a;        } else { // Array must be resized            if (nBits <= (32-bitsInHighWord)) {                int result[] = new int[nInts+len];                for (int i=0; i<len; i++)                    result[i] = a[i];                primitiveLeftShift(result, result.length, nBits);                return result;            } else {                int result[] = new int[nInts+len+1];                for (int i=0; i<len; i++)                    result[i] = a[i];                primitiveRightShift(result, result.length, 32 - nBits);                return result;            }        }    }    // shifts a up to len right n bits assumes no leading zeros, 0<n<32    static void primitiveRightShift(int[] a, int len, int n) {        int n2 = 32 - n;        for (int i=len-1, c=a[i]; i>0; i--) {            int b = c;            c = a[i-1];            a[i] = (c << n2) | (b >>> n);        }        a[0] >>>= n;    }    // shifts a up to len left n bits assumes no leading zeros, 0<=n<32    static void primitiveLeftShift(int[] a, int len, int n) {        if (len == 0 || n == 0)            return;        int n2 = 32 - n;        for (int i=0, c=a[i], m=i+len-1; i<m; i++) {            int b = c;            c = a[i+1];            a[i] = (b << n) | (c >>> n2);        }        a[len-1] <<= n;    }    /**     * Calculate bitlength of contents of the first len elements an int array,     * assuming there are no leading zero ints.     */    private static int bitLength(int[] val, int len) {        if (len==0)            return 0;        return ((len-1)<<5) + bitLen(val[0]);    }    /**     * Returns a BigInteger whose value is the absolute value of this     * BigInteger.      *     * @return <tt>abs(this)</tt>     */    public BigInteger abs() {	return (signum >= 0 ? this : this.negate());    }    /**     * Returns a BigInteger whose value is <tt>(-this)</tt>.     *     * @return <tt>-this</tt>     */    public BigInteger negate() {	return new BigInteger(this.mag, -this.signum);    }    /**     * Returns the signum function of this BigInteger.     *     * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or     *	       positive.     */    public int signum() {	return this.signum;    }    // Modular Arithmetic Operations    /**     * Returns a BigInteger whose value is <tt>(this mod m</tt>).  This method     * differs from <tt>remainder</tt> in that it always returns a     * <i>non-negative</i> BigInteger.     *     * @param  m the modulus.     * @return <tt>this mod m</tt>     * @throws ArithmeticException <tt>m &lt;= 0</tt>     * @see    #remainder     */    public BigInteger mod(BigInteger m) {	if (m.signum <= 0)	    throw new ArithmeticException("BigInteger: modulus not positive");	BigInteger result = this.remainder(m);	return (result.signum >= 0 ? result : result.add(m));    }    /**     * Returns a BigInteger whose value is     * <tt>(this<sup>exponent</sup> mod m)</tt>.  (Unlike <tt>pow</tt>, this     * method permits negative exponents.)     *     * @param  exponent the exponent.     * @param  m the modulus.     * @return <tt>this<sup>exponent</sup> mod m</tt>     * @throws ArithmeticException <tt>m &lt;= 0</tt>     * @see    #modInverse     */    public BigInteger modPow(BigInteger exponent, BigInteger m) {	if (m.signum <= 0)