serial:

since: 1.2 -

since: 1.2 -

since: 1.5 -

 public BigInteger(byte[] val) 
{
    //Constructors
        if (val.length == 0)
            throw new NumberFormatException("Zero length BigInteger");
        if (val[0] <  0) {
            mag = makePositive(val);
            signum = -1;
        } else {
            mag = stripLeadingZeroBytes(val);
            signum = (mag.length == 0 ? 0 : 1);
        }
}

Translates a byte array containing the two's-complement binary representation of a BigInteger into a BigInteger. The input array is assumed to be in big-endian byte-order: the most significant byte is in the zeroth element.

Parameters:

val - big-endian two's-complement binary representation of BigInteger.

Throws:

NumberFormatException - {@code val} is zero bytes long.

 BigInteger(char[] val) 
{
        int cursor = 0, numDigits;
        int len = val.length;
        // Check for leading minus sign
        signum = 1;
        if (val[0] == '-") {
            if (len == 1)
                throw new NumberFormatException("Zero length BigInteger");
            signum = -1;
            cursor = 1;
        } else if (val[0] == '+") {
            if (len == 1)
                throw new NumberFormatException("Zero length BigInteger");
            cursor = 1;
        }
        // Skip leading zeros and compute number of digits in magnitude
        while (cursor <  len && Character.digit(val[cursor], 10) == 0)
            cursor++;
        if (cursor == len) {
            signum = 0;
            mag = ZERO.mag;
            return;
        } else {
            numDigits = len - cursor;
        }
        // Pre-allocate array of expected size
        int numWords;
        if (len <  10) {
            numWords = 1;
        } else {
            int numBits = (int)(((numDigits * bitsPerDigit[10])  > > > 10) + 1);
            numWords = (numBits + 31) /32;
        }
        mag = new int[numWords];
        // Process first (potentially short) digit group
        int firstGroupLen = numDigits % digitsPerInt[10];
        if (firstGroupLen == 0)
            firstGroupLen = digitsPerInt[10];
        mag[mag.length-1] = parseInt(val, cursor,  cursor += firstGroupLen);
        // Process remaining digit groups
        while (cursor <  len) {
            int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
            destructiveMulAdd(mag, intRadix[10], groupVal);
        }
        mag = trustedStripLeadingZeroInts(mag);
}

 public BigInteger(String val) 
{
        this(val, 10);
}

Translates the decimal String representation of a BigInteger into a BigInteger. The String representation consists of an optional minus sign followed by a sequence of one or more decimal digits. The character-to-digit mapping is provided by {@code Character.digit}. The String may not contain any extraneous characters (whitespace, for example).

Parameters:

val - decimal String representation of BigInteger.

Throws:

NumberFormatException - {@code val} is not a valid representation of a BigInteger.

Also see:

Character#digit

 public BigInteger(int signum,
    byte[] magnitude) 
{
        this.mag = stripLeadingZeroBytes(magnitude);
        if (signum <  -1 || signum  > 1)
            throw(new NumberFormatException("Invalid signum value"));
        if (this.mag.length==0) {
            this.signum = 0;
        } else {
            if (signum == 0)
                throw(new NumberFormatException("signum-magnitude mismatch"));
            this.signum = signum;
        }
}

Translates the sign-magnitude representation of a BigInteger into a BigInteger. The sign is represented as an integer signum value: -1 for negative, 0 for zero, or 1 for positive. The magnitude is a byte array in big-endian byte-order: the most significant byte is in the zeroth element. A zero-length magnitude array is permissible, and will result in a BigInteger value of 0, whether signum is -1, 0 or 1.

Parameters:

signum - signum of the number (-1 for negative, 0 for zero, 1 for positive).

magnitude - big-endian binary representation of the magnitude of the number.

Throws:

NumberFormatException - {@code signum} is not one of the three legal values (-1, 0, and 1), or {@code signum} is 0 and {@code magnitude} contains one or more non-zero bytes.

 public BigInteger(String val,
    int radix) 
{
        int cursor = 0, numDigits;
        int len = val.length();
        if (radix <  Character.MIN_RADIX || radix  > Character.MAX_RADIX)
            throw new NumberFormatException("Radix out of range");
        if (val.length() == 0)
            throw new NumberFormatException("Zero length BigInteger");
        // Check for at most one leading sign
        signum = 1;
        int index1 = val.lastIndexOf('-");
        int index2 = val.lastIndexOf('+");
        if ((index1 + index2) < = -1) {
            // No leading sign character or at most one leading sign character
            if (index1 == 0 || index2 == 0) {
                cursor = 1;
                if (val.length() == 1)
                    throw new NumberFormatException("Zero length BigInteger");
            }
            if (index1 == 0)
                signum = -1;
        } else
            throw new NumberFormatException("Illegal embedded sign character");
        // Skip leading zeros and compute number of digits in magnitude
        while (cursor <  len &&
               Character.digit(val.charAt(cursor), radix) == 0)
            cursor++;
        if (cursor == len) {
            signum = 0;
            mag = ZERO.mag;
            return;
        } else {
            numDigits = len - cursor;
        }
        // Pre-allocate array of expected size. May be too large but can
        // never be too small. Typically exact.
        int numBits = (int)(((numDigits * bitsPerDigit[radix])  > > > 10) + 1);
        int numWords = (numBits + 31) /32;
        mag = new int[numWords];
        // Process first (potentially short) digit group
        int firstGroupLen = numDigits % digitsPerInt[radix];
        if (firstGroupLen == 0)
            firstGroupLen = digitsPerInt[radix];
        String group = val.substring(cursor, cursor += firstGroupLen);
        mag[mag.length - 1] = Integer.parseInt(group, radix);
        if (mag[mag.length - 1] <  0)
            throw new NumberFormatException("Illegal digit");
        // Process remaining digit groups
        int superRadix = intRadix[radix];
        int groupVal = 0;
        while (cursor <  val.length()) {
            group = val.substring(cursor, cursor += digitsPerInt[radix]);
            groupVal = Integer.parseInt(group, radix);
            if (groupVal <  0)
                throw new NumberFormatException("Illegal digit");
            destructiveMulAdd(mag, superRadix, groupVal);
        }
        // Required for cases where the array was overallocated.
        mag = trustedStripLeadingZeroInts(mag);
}

Translates the String representation of a BigInteger in the specified radix into a BigInteger. The String representation consists of an optional minus or plus sign followed by a sequence of one or more digits in the specified radix. The character-to-digit mapping is provided by {@code Character.digit}. The String may not contain any extraneous characters (whitespace, for example).

Parameters:

val - String representation of BigInteger.

radix - radix to be used in interpreting {@code val}.

Throws:

NumberFormatException - {@code val} is not a valid representation of a BigInteger in the specified radix, or {@code radix} is outside the range from Character#MIN_RADIX to Character#MAX_RADIX , inclusive.

Also see:

Character#digit

 public BigInteger(int numBits,
    Random rnd) 
{
        this(1, randomBits(numBits, rnd));
}

Constructs a randomly generated BigInteger, uniformly distributed over the range {@code 0} to (2^{{@code numBits}} - 1), inclusive. The uniformity of the distribution assumes that a fair source of random bits is provided in {@code rnd}. Note that this constructor always constructs a non-negative BigInteger.

Parameters:

numBits - maximum bitLength of the new BigInteger.

rnd - source of randomness to be used in computing the new BigInteger.

Throws:

IllegalArgumentException - {@code numBits} is negative.

Also see:

bitLength()

 BigInteger(MutableBigInteger val,
    int sign) 
{
        if (val.offset  > 0 || val.value.length != val.intLen) {
            mag = new int[val.intLen];
            for(int i=0; i< val.intLen; i++)
                mag[i] = val.value[val.offset+i];
        } else {
            mag = val.value;
        }
        this.signum = (val.intLen == 0) ? 0 : sign;
}

This private constructor is for internal use in converting from a MutableBigInteger object into a BigInteger.

 public BigInteger(int bitLength,
    int certainty,
    Random rnd) 
{
        BigInteger prime;
        if (bitLength <  2)
            throw new ArithmeticException("bitLength <  2");
        // The cutoff of 95 was chosen empirically for best performance
        prime = (bitLength <  95 ? smallPrime(bitLength, certainty, rnd)
                                : largePrime(bitLength, certainty, rnd));
        signum = 1;
        mag = prime.mag;
}

Constructs a randomly generated positive BigInteger that is probably prime, with the specified bitLength.

It is recommended that the probablePrime method be used in preference to this constructor unless there is a compelling need to specify a certainty.

Parameters:

bitLength - bitLength of the returned BigInteger.

certainty - a measure of the uncertainty that the caller is willing to tolerate. The probability that the new BigInteger represents a prime number will exceed (1 - 1/2^{{@code certainty}}). The execution time of this constructor is proportional to the value of this parameter.

rnd - source of random bits used to select candidates to be tested for primality.

Throws:

ArithmeticException - {@code bitLength < 2}.

Also see:

bitLength()

 public BigInteger abs() 
{
        return (signum  >= 0 ? this : this.negate());
}

Returns a BigInteger whose value is the absolute value of this BigInteger.

 public BigInteger add(BigInteger val) 
{
    // Arithmetic Operations
        int[] resultMag;
        if (val.signum == 0)
            return this;
        if (signum == 0)
            return val;
        if (val.signum == signum)
            return new BigInteger(add(mag, val.mag), signum);
        int cmp = intArrayCmp(mag, val.mag);
        if (cmp==0)
            return ZERO;
        resultMag = (cmp >0 ? subtract(mag, val.mag)
                           : subtract(val.mag, mag));
        resultMag = trustedStripLeadingZeroInts(resultMag);
        return new BigInteger(resultMag, cmp*signum);
}

Returns a BigInteger whose value is {@code (this + val)}.

 static int addOne(int[] a,
    int offset,
    int mlen,
    int carry) 
{
        offset = a.length-1-mlen-offset;
        long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
        a[offset] = (int)t;
        if ((t  > > > 32) == 0)
            return 0;
        while (--mlen  >= 0) {
            if (--offset <  0) { // Carry out of number
                return 1;
            } else {
                a[offset]++;
                if (a[offset] != 0)
                    return 0;
            }
        }
        return 1;
}

Add one word to the number a mlen words into a. Return the resulting carry.

 public BigInteger and(BigInteger val) 
{
        int[] result = new int[Math.max(intLength(), val.intLength())];
        for (int i=0; i< result.length; i++)
            result[i] = (getInt(result.length-i-1)
                         & val.getInt(result.length-i-1));
        return valueOf(result);
}

Returns a BigInteger whose value is {@code (this & val)}. (This method returns a negative BigInteger if and only if this and val are both negative.)

 public BigInteger andNot(BigInteger val) 
{
        int[] result = new int[Math.max(intLength(), val.intLength())];
        for (int i=0; i< result.length; i++)
            result[i] = (getInt(result.length-i-1)
                         & ~val.getInt(result.length-i-1));
        return valueOf(result);
}

Returns a BigInteger whose value is {@code (this & ~val)}. This method, which is equivalent to {@code and(val.not())}, is provided as a convenience for masking operations. (This method returns a negative BigInteger if and only if {@code this} is negative and {@code val} is positive.)

 static int bitCnt(int val) 
{
        val -= (0xaaaaaaaa & val)  > > > 1;
        val = (val & 0x33333333) + ((val  > > > 2) & 0x33333333);
        val = val + (val  > > > 4) & 0x0f0f0f0f;
        val += val  > > > 8;
        val += val  > > > 16;
        return val & 0xff;
}

 public int bitCount() 
{
                                                                  
        /*
         * Initialize bitCount field the first time this method is executed.
         * This method depends on the atomicity of int modifies; without
         * this guarantee, it would have to be synchronized.
         */
        if (bitCount == -1) {
            // Count the bits in the magnitude
            int magBitCount = 0;
            for (int i=0; i< mag.length; i++)
                magBitCount += bitCnt(mag[i]);
            if (signum <  0) {
                // Count the trailing zeros in the magnitude
                int magTrailingZeroCount = 0, j;
                for (j=mag.length-1; mag[j]==0; j--)
                    magTrailingZeroCount += 32;
                magTrailingZeroCount +=
                            trailingZeroCnt(mag[j]);
                bitCount = magBitCount + magTrailingZeroCount - 1;
            } else {
                bitCount = magBitCount;
            }
        }
        return bitCount;
}

Returns the number of bits in the two's complement representation of this BigInteger that differ from its sign bit. This method is useful when implementing bit-vector style sets atop BigIntegers.

 static int bitLen(int w) 
{
        // Binary search - decision tree (5 tests, rarely 6)
        return
         (w <  1< < 15 ?
          (w <  1< < 7 ?
           (w <  1< < 3 ?
            (w <  1< < 1 ? (w <  1< < 0 ? (w< 0 ? 32 : 0) : 1) : (w <  1< < 2 ? 2 : 3)) :
            (w <  1< < 5 ? (w <  1< < 4 ? 4 : 5) : (w <  1< < 6 ? 6 : 7))) :
           (w <  1< < 11 ?
            (w <  1< < 9 ? (w <  1< < 8 ? 8 : 9) : (w <  1< < 10 ? 10 : 11)) :
            (w <  1< < 13 ? (w <  1< < 12 ? 12 : 13) : (w <  1< < 14 ? 14 : 15)))) :
          (w <  1< < 23 ?
           (w <  1< < 19 ?
            (w <  1< < 17 ? (w <  1< < 16 ? 16 : 17) : (w <  1< < 18 ? 18 : 19)) :
            (w <  1< < 21 ? (w <  1< < 20 ? 20 : 21) : (w <  1< < 22 ? 22 : 23))) :
           (w <  1< < 27 ?
            (w <  1< < 25 ? (w <  1< < 24 ? 24 : 25) : (w <  1< < 26 ? 26 : 27)) :
            (w <  1< < 29 ? (w <  1< < 28 ? 28 : 29) : (w <  1< < 30 ? 30 : 31)))));
}

bitLen(val) is the number of bits in val.

 public int bitLength() 
{
        /*
         * Initialize bitLength field the first time this method is executed.
         * This method depends on the atomicity of int modifies; without
         * this guarantee, it would have to be synchronized.
         */
        if (bitLength == -1) {
            if (signum == 0) {
                bitLength = 0;
            } else {
                // Calculate the bit length of the magnitude
                int magBitLength = ((mag.length-1) < <  5) + bitLen(mag[0]);
                if (signum <  0) {
                    // Check if magnitude is a power of two
                    boolean pow2 = (bitCnt(mag[0]) == 1);
                    for(int i=1; i< mag.length && pow2; i++)
                        pow2 = (mag[i]==0);
                    bitLength = (pow2 ? magBitLength-1 : magBitLength);
                } else {
                    bitLength = magBitLength;
                }
            }
        }
        return bitLength;
}

Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit. For positive BigIntegers, this is equivalent to the number of bits in the ordinary binary representation. (Computes {@code (ceil(log2(this < 0 ? -this : this+1)))}.)

 public BigInteger clearBit(int n) 
{
        if (n< 0)
            throw new ArithmeticException("Negative bit address");
        int intNum = n/32;
        int[] result = new int[Math.max(intLength(), (n+1)/32+1)];
        for (int i=0; i< result.length; i++)
            result[result.length-i-1] = getInt(i);
        result[result.length-intNum-1] &= ~(1 < <  (n%32));
        return valueOf(result);
}

Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit cleared. (Computes {@code (this & ~(1<

 public int compareTo(BigInteger val) 
{
        return (signum==val.signum
                ? signum*intArrayCmp(mag, val.mag)
                : (signum >val.signum ? 1 : -1));
}

Compares this BigInteger with the specified BigInteger. This method is provided in preference to individual methods for each of the six boolean comparison operators ({@literal <}, ==, {@literal >}, {@literal >=}, !=, {@literal <=}). The suggested idiom for performing these comparisons is: {@code (x.compareTo(y)} <op> {@code 0)}, where <op> is one of the six comparison operators.

 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 a BigInteger whose value is {@code (this / val)}.

 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 an array of two BigIntegers containing {@code (this / val)} followed by {@code (this % val)}.

 public double doubleValue() 
{
        // Somewhat inefficient, but guaranteed to work.
        return Double.parseDouble(this.toString());
}

Converts this BigInteger to a {@code double}. This conversion is similar to the narrowing primitive conversion from {@code double} to {@code float} defined in the Java Language Specification: if this BigInteger has too great a magnitude to represent as a {@code double}, it will be converted to Double#NEGATIVE_INFINITY or Double#POSITIVE_INFINITY as appropriate. Note that even when the return value is finite, this conversion can lose information about the precision of the BigInteger value.

 public boolean equals(Object x) 
{
        // This test is just an optimization, which may or may not help
        if (x == this)
            return true;
        if (!(x instanceof BigInteger))
            return false;
        BigInteger xInt = (BigInteger) x;
        if (xInt.signum != signum || xInt.mag.length != mag.length)
            return false;
        for (int i=0; i< mag.length; i++)
            if (xInt.mag[i] != mag[i])
                return false;
        return true;
}

Compares this BigInteger with the specified Object for equality.

 public BigInteger flipBit(int n) 
{
        if (n< 0)
            throw new ArithmeticException("Negative bit address");
        int intNum = n/32;
        int[] result = new int[Math.max(intLength(), intNum+2)];
        for (int i=0; i< result.length; i++)
            result[result.length-i-1] = getInt(i);
        result[result.length-intNum-1] ^= (1 < <  (n%32));
        return valueOf(result);
}

Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit flipped. (Computes {@code (this ^ (1<

 public float floatValue() 
{
        // Somewhat inefficient, but guaranteed to work.
        return Float.parseFloat(this.toString());
}

Converts this BigInteger to a {@code float}. This conversion is similar to the narrowing primitive conversion from {@code double} to {@code float} defined in the Java Language Specification: if this BigInteger has too great a magnitude to represent as a {@code float}, it will be converted to Float#NEGATIVE_INFINITY or Float#POSITIVE_INFINITY as appropriate. Note that even when the return value is finite, this conversion can lose information about the precision of the BigInteger value.

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

Returns a BigInteger whose value is the greatest common divisor of {@code abs(this)} and {@code abs(val)}. Returns 0 if {@code this==0 && val==0}.

 public int getLowestSetBit() 
{
        /*
         * Initialize lowestSetBit field the first time this method is
         * executed. This method depends on the atomicity of int modifies;
         * without this guarantee, it would have to be synchronized.
         */
        if (lowestSetBit == -2) {
            if (signum == 0) {
                lowestSetBit = -1;
            } else {
                // Search for lowest order nonzero int
                int i,b;
                for (i=0; (b = getInt(i))==0; i++)
                    ;
                lowestSetBit = (i < <  5) + trailingZeroCnt(b);
            }
        }
        return lowestSetBit;
}

Returns the index of the rightmost (lowest-order) one bit in this BigInteger (the number of zero bits to the right of the rightmost one bit). Returns -1 if this BigInteger contains no one bits. (Computes {@code (this==0? -1 : log2(this & -this))}.)

 public int hashCode() 
{
        int hashCode = 0;
        for (int i=0; i< mag.length; i++)
            hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK));
        return hashCode * signum;
}

Returns the hash code for this BigInteger.

 public int intValue() 
{
        int result = 0;
        result = getInt(0);
        return result;
}

Converts this BigInteger to an {@code int}. This conversion is analogous to a narrowing primitive conversion from {@code long} to {@code int} as defined in the Java Language Specification: if this BigInteger is too big to fit in an {@code int}, only the low-order 32 bits are returned. Note that this conversion can lose information about the overall magnitude of the BigInteger value as well as return a result with the opposite sign.

 public boolean isProbablePrime(int certainty) 
{
        if (certainty < = 0)
            return true;
        BigInteger w = this.abs();
        if (w.equals(TWO))
            return true;
        if (!w.testBit(0) || w.equals(ONE))
            return false;
        return w.primeToCertainty(certainty, null);
}

Returns {@code true} if this BigInteger is probably prime, {@code false} if it's definitely composite. If {@code certainty} is {@code <= 0}, {@code true} is returned.

 int[] javaIncrement(int[] val) 
{
        int lastSum = 0;
        for (int i=val.length-1;  i  >= 0 && lastSum == 0; i--)
            lastSum = (val[i] += 1);
        if (lastSum == 0) {
            val = new int[val.length+1];
            val[0] = 1;
        }
        return val;
}

 public long longValue() 
{
        long result = 0;
        for (int i=1; i >=0; i--)
            result = (result < <  32) + (getInt(i) & LONG_MASK);
        return result;
}

Converts this BigInteger to a {@code long}. This conversion is analogous to a narrowing primitive conversion from {@code long} to {@code int} as defined in the Java Language Specification: if this BigInteger is too big to fit in a {@code long}, only the low-order 64 bits are returned. Note that this conversion can lose information about the overall magnitude of the BigInteger value as well as return a result with the opposite sign.

 public BigInteger max(BigInteger val) 
{
        return (compareTo(val) >0 ? this : val);
}

Returns the maximum of this BigInteger and {@code val}.

 public BigInteger min(BigInteger val) 
{
        return (compareTo(val)< 0 ? this : val);
}

Returns the minimum of this BigInteger and {@code val}.

 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 {@code (this mod m}). This method differs from {@code remainder} in that it always returns a non-negative BigInteger.

 public BigInteger modInverse(BigInteger m) 
{
        if (m.signum != 1)
            throw new ArithmeticException("BigInteger: modulus not positive");
        if (m.equals(ONE))
            return ZERO;
        // Calculate (this mod m)
        BigInteger modVal = this;
        if (signum <  0 || (intArrayCmp(mag, m.mag)  >= 0))
            modVal = this.mod(m);
        if (modVal.equals(ONE))
            return ONE;
        MutableBigInteger a = new MutableBigInteger(modVal);
        MutableBigInteger b = new MutableBigInteger(m);
        MutableBigInteger result = a.mutableModInverse(b);
        return new BigInteger(result, 1);
}

Returns a BigInteger whose value is {@code (this}^-1 {@code mod m)}.

 public BigInteger modPow(BigInteger exponent,
    BigInteger m) 
{
        if (m.signum < = 0)
            throw new ArithmeticException("BigInteger: modulus not positive");
        // Trivial cases
        if (exponent.signum == 0)
            return (m.equals(ONE) ? ZERO : ONE);
        if (this.equals(ONE))
            return (m.equals(ONE) ? ZERO : ONE);
        if (this.equals(ZERO) && exponent.signum  >= 0)
            return ZERO;
        if (this.equals(negConst[1]) && (!exponent.testBit(0)))
            return (m.equals(ONE) ? ZERO : ONE);
        boolean invertResult;
        if ((invertResult = (exponent.signum <  0)))
            exponent = exponent.negate();
        BigInteger base = (this.signum <  0 || this.compareTo(m)  >= 0
                           ? this.mod(m) : this);
        BigInteger result;
        if (m.testBit(0)) { // odd modulus
            result = base.oddModPow(exponent, m);
        } else {
            /*
             * Even modulus.  Tear it into an "odd part" (m1) and power of two
             * (m2), exponentiate mod m1, manually exponentiate mod m2, and
             * use Chinese Remainder Theorem to combine results.
             */
            // Tear m apart into odd part (m1) and power of 2 (m2)
            int p = m.getLowestSetBit();   // Max pow of 2 that divides m
            BigInteger m1 = m.shiftRight(p);  // m/2**p
            BigInteger m2 = ONE.shiftLeft(p); // 2**p
            // Calculate new base from m1
            BigInteger base2 = (this.signum <  0 || this.compareTo(m1)  >= 0
                                ? this.mod(m1) : this);
            // Caculate (base ** exponent) mod m1.
            BigInteger a1 = (m1.equals(ONE) ? ZERO :
                             base2.oddModPow(exponent, m1));
            // Calculate (this ** exponent) mod m2
            BigInteger a2 = base.modPow2(exponent, p);
            // Combine results using Chinese Remainder Theorem
            BigInteger y1 = m2.modInverse(m1);
            BigInteger y2 = m1.modInverse(m2);
            result = a1.multiply(m2).multiply(y1).add
                     (a2.multiply(m1).multiply(y2)).mod(m);
        }
        return (invertResult ? result.modInverse(m) : result);
}

Returns a BigInteger whose value is (this^exponent mod m). (Unlike {@code pow}, this method permits negative exponents.)

 static int mulAdd(int[] out,
    int[] in,
    int offset,
    int len,
    int k) 
{
        long kLong = k & LONG_MASK;
        long carry = 0;
        offset = out.length-offset - 1;
        for (int j=len-1; j  >= 0; j--) {
            long product = (in[j] & LONG_MASK) * kLong +
                           (out[offset] & LONG_MASK) + carry;
            out[offset--] = (int)product;
            carry = product  > > > 32;
        }
        return (int)carry;
}

Multiply an array by one word k and add to result, return the carry

 public BigInteger multiply(BigInteger val) 
{
        if (val.signum == 0 || 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);
}

Returns a BigInteger whose value is {@code (this * val)}.

 public BigInteger negate() 
{
        return new BigInteger(this.mag, -this.signum);
}

Returns a BigInteger whose value is {@code (-this)}.

 public BigInteger nextProbablePrime() 
{
        if (this.signum <  0)
            throw new ArithmeticException("start <  0: " + this);
        // Handle trivial cases
        if ((this.signum == 0) || this.equals(ONE))
            return TWO;
        BigInteger result = this.add(ONE);
        // Fastpath for small numbers
        if (result.bitLength() <  SMALL_PRIME_THRESHOLD) {
            // Ensure an odd number
            if (!result.testBit(0))
                result = result.add(ONE);
            while(true) {
                // Do cheap "pre-test" if applicable
                if (result.bitLength()  > 6) {
                    long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
                    if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
                        (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
                        (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                        result = result.add(TWO);
                        continue; // Candidate is composite; try another
                    }
                }
                // All candidates of bitLength 2 and 3 are prime by this point
                if (result.bitLength() <  4)
                    return result;
                // The expensive test
                if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                    return result;
                result = result.add(TWO);
            }
        }
        // Start at previous even number
        if (result.testBit(0))
            result = result.subtract(ONE);
        // Looking for the next large prime
        int searchLen = (result.bitLength() / 20) * 64;
        while(true) {
           BitSieve searchSieve = new BitSieve(result, searchLen);
           BigInteger candidate = searchSieve.retrieve(result,
                                                 DEFAULT_PRIME_CERTAINTY, null);
           if (candidate != null)
               return candidate;
           result = result.add(BigInteger.valueOf(2 * searchLen));
        }
}

Returns the first integer greater than this {@code BigInteger} that is probably prime. The probability that the number returned by this method is composite does not exceed 2^-100. This method will never skip over a prime when searching: if it returns {@code p}, there is no prime {@code q} such that {@code this < q < p}.

 public BigInteger not() 
{
        int[] result = new int[intLength()];
        for (int i=0; i< result.length; i++)
            result[i] = ~getInt(result.length-i-1);
        return valueOf(result);
}

Returns a BigInteger whose value is {@code (~this)}. (This method returns a negative value if and only if this BigInteger is non-negative.)

 public BigInteger or(BigInteger val) 
{
        int[] result = new int[Math.max(intLength(), val.intLength())];
        for (int i=0; i< result.length; i++)
            result[i] = (getInt(result.length-i-1)
                         | val.getInt(result.length-i-1));
        return valueOf(result);
}

Returns a BigInteger whose value is {@code (this | val)}. (This method returns a negative BigInteger if and only if either this or val is negative.)

 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 (this^exponent). Note that {@code exponent} is an integer rather than a BigInteger.

 boolean primeToCertainty(int certainty,
    Random random) 
{
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;
        // The relationship between the certainty and the number of rounds
        // we perform is given in the draft standard ANSI X9.80, "PRIME
        // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
        int sizeInBits = this.bitLength();
        if (sizeInBits <  100) {
            rounds = 50;
            rounds = n <  rounds ? n : rounds;
            return passesMillerRabin(rounds, random);
        }
        if (sizeInBits <  256) {
            rounds = 27;
        } else if (sizeInBits <  512) {
            rounds = 15;
        } else if (sizeInBits <  768) {
            rounds = 8;
        } else if (sizeInBits <  1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }
        rounds = n <  rounds ? n : rounds;
        return passesMillerRabin(rounds, random) && passesLucasLehmer();
}

Returns {@code true} if this BigInteger is probably prime, {@code false} if it's definitely composite. This method assumes bitLength > 2.

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

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

 public static BigInteger probablePrime(int bitLength,
    Random rnd) 
{
                                                                                            
        if (bitLength <  2)
            throw new ArithmeticException("bitLength <  2");
        // The cutoff of 95 was chosen empirically for best performance
        return (bitLength <  SMALL_PRIME_THRESHOLD ?
                smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
                largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
}

Returns a positive BigInteger that is probably prime, with the specified bitLength. The probability that a BigInteger returned by this method is composite does not exceed 2^-100.

 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 {@code (this % val)}.

 public BigInteger setBit(int n) 
{
        if (n< 0)
            throw new ArithmeticException("Negative bit address");
        int intNum = n/32;
        int[] result = new int[Math.max(intLength(), intNum+2)];
        for (int i=0; i< result.length; i++)
            result[result.length-i-1] = getInt(i);
        result[result.length-intNum-1] |= (1 < <  (n%32));
        return valueOf(result);
}

Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit set. (Computes {@code (this | (1<

 public BigInteger shiftLeft(int n) 
{
        if (signum == 0)
            return ZERO;
        if (n==0)
            return this;
        if (n< 0)
            return shiftRight(-n);
        int nInts = n  > > > 5;
        int nBits = n & 0x1f;
        int magLen = mag.length;
        int newMag[] = null;
        if (nBits == 0) {
            newMag = new int[magLen + nInts];
            for (int i=0; i< magLen; i++)
                newMag[i] = mag[i];
        } else {
            int i = 0;
            int nBits2 = 32 - nBits;
            int highBits = mag[0]  > > > nBits2;
            if (highBits != 0) {
                newMag = new int[magLen + nInts + 1];
                newMag[i++] = highBits;
            } else {
                newMag = new int[magLen + nInts];
            }
            int j=0;
            while (j <  magLen-1)
                newMag[i++] = mag[j++] < <  nBits | mag[j]  > > > nBits2;
            newMag[i] = mag[j] < <  nBits;
        }
        return new BigInteger(newMag, signum);
}

Returns a BigInteger whose value is {@code (this << n)}. The shift distance, {@code n}, may be negative, in which case this method performs a right shift. (Computes floor(this * 2ⁿ).)

 public BigInteger shiftRight(int n) 
{
        if (n==0)
            return this;
        if (n< 0)
            return shiftLeft(-n);
        int nInts = n  > > > 5;
        int nBits = n & 0x1f;
        int magLen = mag.length;
        int newMag[] = null;
        // Special case: entire contents shifted off the end
        if (nInts  >= magLen)
            return (signum  >= 0 ? ZERO : negConst[1]);
        if (nBits == 0) {
            int newMagLen = magLen - nInts;
            newMag = new int[newMagLen];
            for (int i=0; i< newMagLen; i++)
                newMag[i] = mag[i];
        } else {
            int i = 0;
            int highBits = mag[0]  > > > nBits;
            if (highBits != 0) {
                newMag = new int[magLen - nInts];
                newMag[i++] = highBits;
            } else {
                newMag = new int[magLen - nInts -1];
            }
            int nBits2 = 32 - nBits;
            int j=0;
            while (j <  magLen - nInts - 1)
                newMag[i++] = (mag[j++] < <  nBits2) | (mag[j]  > > > nBits);
        }
        if (signum <  0) {
            // Find out whether any one-bits were shifted off the end.
            boolean onesLost = false;
            for (int i=magLen-1, j=magLen-nInts; i >=j && !onesLost; i--)
                onesLost = (mag[i] != 0);
            if (!onesLost && nBits != 0)
                onesLost = (mag[magLen - nInts - 1] < <  (32 - nBits) != 0);
            if (onesLost)
                newMag = javaIncrement(newMag);
        }
        return new BigInteger(newMag, signum);
}

Returns a BigInteger whose value is {@code (this >> n)}. Sign extension is performed. The shift distance, {@code n}, may be negative, in which case this method performs a left shift. (Computes floor(this / 2ⁿ).)

 public int signum() 
{
        return this.signum;
}

Returns the signum function of this BigInteger.

 public BigInteger subtract(BigInteger val) 
{
        int[] resultMag;
        if (val.signum == 0)
            return this;
        if (signum == 0)
            return val.negate();
        if (val.signum != signum)
            return new BigInteger(add(mag, val.mag), signum);
        int cmp = intArrayCmp(mag, val.mag);
        if (cmp==0)
            return ZERO;
        resultMag = (cmp >0 ? subtract(mag, val.mag)
                           : subtract(val.mag, mag));
        resultMag = trustedStripLeadingZeroInts(resultMag);
        return new BigInteger(resultMag, cmp*signum);
}

Returns a BigInteger whose value is {@code (this - val)}.

 public boolean testBit(int n) 
{
        if (n< 0)
            throw new ArithmeticException("Negative bit address");
        return (getInt(n/32) & (1 < <  (n%32))) != 0;
}

Returns {@code true} if and only if the designated bit is set. (Computes {@code ((this & (1<

 public byte[] toByteArray() 
{
        int byteLen = bitLength()/8 + 1;
        byte[] byteArray = new byte[byteLen];
        for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i >=0; i--) {
            if (bytesCopied == 4) {
                nextInt = getInt(intIndex++);
                bytesCopied = 1;
            } else {
                nextInt  > > >= 8;
                bytesCopied++;
            }
            byteArray[i] = (byte)nextInt;
        }
        return byteArray;
}

Returns a byte array containing the two's-complement representation of this BigInteger. The byte array will be in big-endian byte-order: the most significant byte is in the zeroth element. The array will contain the minimum number of bytes required to represent this BigInteger, including at least one sign bit, which is {@code (ceil((this.bitLength() + 1)/8))}. (This representation is compatible with the (byte[]) constructor.)

 public String toString() 
{
     
        zeros[63] =
            "000000000000000000000000000000000000000000000000000000000000000";
        for (int i=0; i< 63; i++)
            zeros[i] = zeros[63].substring(0, i);
        return toString(10);
}

Returns the decimal String representation of this BigInteger. The digit-to-character mapping provided by {@code Character.forDigit} is used, and a minus sign is prepended if appropriate. (This representation is compatible with the (String) constructor, and allows for String concatenation with Java's + operator.)

 public String toString(int radix) 
{
        if (signum == 0)
            return "0";
        if (radix <  Character.MIN_RADIX || radix  > Character.MAX_RADIX)
            radix = 10;
        // Compute upper bound on number of digit groups and allocate space
        int maxNumDigitGroups = (4*mag.length + 6)/7;
        String digitGroup[] = new String[maxNumDigitGroups];
        // Translate number to string, a digit group at a time
        BigInteger tmp = this.abs();
        int numGroups = 0;
        while (tmp.signum != 0) {
            BigInteger d = longRadix[radix];
            MutableBigInteger q = new MutableBigInteger(),
                              r = new MutableBigInteger(),
                              a = new MutableBigInteger(tmp.mag),
                              b = new MutableBigInteger(d.mag);
            a.divide(b, q, r);
            BigInteger q2 = new BigInteger(q, tmp.signum * d.signum);
            BigInteger r2 = new BigInteger(r, tmp.signum * d.signum);
            digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
            tmp = q2;
        }
        // Put sign (if any) and first digit group into result buffer
        StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
        if (signum< 0)
            buf.append('-");
        buf.append(digitGroup[numGroups-1]);
        // Append remaining digit groups padded with leading zeros
        for (int i=numGroups-2; i >=0; i--) {
            // Prepend (any) leading zeros for this digit group
            int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
            if (numLeadingZeros != 0)
                buf.append(zeros[numLeadingZeros]);
            buf.append(digitGroup[i]);
        }
        return buf.toString();
}

Returns the String representation of this BigInteger in the given radix. If the radix is outside the range from Character#MIN_RADIX to Character#MAX_RADIX inclusive, it will default to 10 (as is the case for {@code Integer.toString}). The digit-to-character mapping provided by {@code Character.forDigit} is used, and a minus sign is prepended if appropriate. (This representation is compatible with the int) (String, int) constructor.)

 static int trailingZeroCnt(int val) 
{
        // Loop unrolled for performance
        int byteVal = val & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal];
        byteVal = (val  > > > 8) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 8;
        byteVal = (val  > > > 16) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 16;
        byteVal = (val  > > > 24) & 0xff;
        return trailingZeroTable[byteVal] + 24;
}

 public static BigInteger valueOf(long val) 
{
        // If -MAX_CONSTANT <  val <  MAX_CONSTANT, return stashed constant
        if (val == 0)
            return ZERO;
        if (val  > 0 && val < = MAX_CONSTANT)
            return posConst[(int) val];
        else if (val <  0 && val  >= -MAX_CONSTANT)
            return negConst[(int) -val];
        return new BigInteger(val);
}

Returns a BigInteger whose value is equal to that of the specified {@code long}. This "static factory method" is provided in preference to a ({@code long}) constructor because it allows for reuse of frequently used BigIntegers.

 public BigInteger xor(BigInteger val) 
{
        int[] result = new int[Math.max(intLength(), val.intLength())];
        for (int i=0; i< result.length; i++)
            result[i] = (getInt(result.length-i-1)
                         ^ val.getInt(result.length-i-1));
        return valueOf(result);
}

Returns a BigInteger whose value is {@code (this ^ val)}. (This method returns a negative BigInteger if and only if exactly one of this and val are negative.)