0001: /*
0002: * @(#)BigInteger.java 1.47 06/10/23
0003: *
0004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License version
0009: * 2 only, as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful, but
0012: * WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: * General Public License version 2 for more details (a copy is
0015: * included at /legal/license.txt).
0016: *
0017: * You should have received a copy of the GNU General Public License
0018: * version 2 along with this work; if not, write to the Free Software
0019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
0020: * 02110-1301 USA
0021: *
0022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
0023: * Clara, CA 95054 or visit www.sun.com if you need additional
0024: * information or have any questions.
0025: *
0026: */
0027:
0028: package java.math;
0029:
0030: import java.util.Random;
0031: import java.io.*;
0032:
0033: /**
0034: * Immutable arbitrary-precision integers. All operations behave as if
0035: * BigIntegers were represented in two's-complement notation (like Java's
0036: * primitive integer types). BigInteger provides analogues to all of Java's
0037: * primitive integer operators, and all relevant methods from java.lang.Math.
0038: * Additionally, BigInteger provides operations for modular arithmetic, GCD
0039: * calculation, primality testing, prime generation, bit manipulation,
0040: * and a few other miscellaneous operations.
0041: * <p>
0042: * Semantics of arithmetic operations exactly mimic those of Java's integer
0043: * arithmetic operators, as defined in <i>The Java Language Specification</i>.
0044: * For example, division by zero throws an <tt>ArithmeticException</tt>, and
0045: * division of a negative by a positive yields a negative (or zero) remainder.
0046: * All of the details in the Spec concerning overflow are ignored, as
0047: * BigIntegers are made as large as necessary to accommodate the results of an
0048: * operation.
0049: * <p>
0050: * Semantics of shift operations extend those of Java's shift operators
0051: * to allow for negative shift distances. A right-shift with a negative
0052: * shift distance results in a left shift, and vice-versa. The unsigned
0053: * right shift operator (>>>) is omitted, as this operation makes
0054: * little sense in combination with the "infinite word size" abstraction
0055: * provided by this class.
0056: * <p>
0057: * Semantics of bitwise logical operations exactly mimic those of Java's
0058: * bitwise integer operators. The binary operators (<tt>and</tt>,
0059: * <tt>or</tt>, <tt>xor</tt>) implicitly perform sign extension on the shorter
0060: * of the two operands prior to performing the operation.
0061: * <p>
0062: * Comparison operations perform signed integer comparisons, analogous to
0063: * those performed by Java's relational and equality operators.
0064: * <p>
0065: * Modular arithmetic operations are provided to compute residues, perform
0066: * exponentiation, and compute multiplicative inverses. These methods always
0067: * return a non-negative result, between <tt>0</tt> and <tt>(modulus - 1)</tt>,
0068: * inclusive.
0069: * <p>
0070: * Bit operations operate on a single bit of the two's-complement
0071: * representation of their operand. If necessary, the operand is sign-
0072: * extended so that it contains the designated bit. None of the single-bit
0073: * operations can produce a BigInteger with a different sign from the
0074: * BigInteger being operated on, as they affect only a single bit, and the
0075: * "infinite word size" abstraction provided by this class ensures that there
0076: * are infinitely many "virtual sign bits" preceding each BigInteger.
0077: * <p>
0078: * For the sake of brevity and clarity, pseudo-code is used throughout the
0079: * descriptions of BigInteger methods. The pseudo-code expression
0080: * <tt>(i + j)</tt> is shorthand for "a BigInteger whose value is
0081: * that of the BigInteger <tt>i</tt> plus that of the BigInteger <tt>j</tt>."
0082: * The pseudo-code expression <tt>(i == j)</tt> is shorthand for
0083: * "<tt>true</tt> if and only if the BigInteger <tt>i</tt> represents the same
0084: * value as the the BigInteger <tt>j</tt>." Other pseudo-code expressions are
0085: * interpreted similarly.
0086: * <p>
0087: * All methods and constructors in this class throw
0088: * <CODE>NullPointerException</CODE> when passed
0089: * a null object reference for any input parameter.
0090: *
0091: * @see BigDecimal
0092: * @version 1.36, 04/21/00
0093: * @author Josh Bloch
0094: * @author Michael McCloskey
0095: * @since JDK1.1
0096: */
0097:
0098: public class BigInteger extends Number implements Comparable {
0099: /**
0100: * The signum of this BigInteger: -1 for negative, 0 for zero, or
0101: * 1 for positive. Note that the BigInteger zero <i>must</i> have
0102: * a signum of 0. This is necessary to ensures that there is exactly one
0103: * representation for each BigInteger value.
0104: *
0105: * @serial
0106: */
0107: int signum;
0108:
0109: /**
0110: * The magnitude of this BigInteger, in <i>big-endian</i> order: the
0111: * zeroth element of this array is the most-significant int of the
0112: * magnitude. The magnitude must be "minimal" in that the most-significant
0113: * int (<tt>mag[0]</tt>) must be non-zero. This is necessary to
0114: * ensure that there is exactly one representation for each BigInteger
0115: * value. Note that this implies that the BigInteger zero has a
0116: * zero-length mag array.
0117: */
0118: transient int[] mag;
0119:
0120: /**
0121: * This field is required for historical reasons. The magnitude of a
0122: * BigInteger used to be in a byte representation, and is still serialized
0123: * that way. The mag field is used in all real computations but the
0124: * magnitude field is required for storage.
0125: *
0126: * @serial
0127: */
0128: private byte[] magnitude;
0129:
0130: // These "redundant fields" are initialized with recognizable nonsense
0131: // values, and cached the first time they are needed (or never, if they
0132: // aren't needed).
0133:
0134: /**
0135: * The bitCount of this BigInteger, as returned by bitCount(), or -1
0136: * (either value is acceptable).
0137: *
0138: * @serial
0139: * @see #bitCount
0140: */
0141: private int bitCount = -1;
0142:
0143: /**
0144: * The bitLength of this BigInteger, as returned by bitLength(), or -1
0145: * (either value is acceptable).
0146: *
0147: * @serial
0148: * @see #bitLength
0149: */
0150: private int bitLength = -1;
0151:
0152: /**
0153: * The lowest set bit of this BigInteger, as returned by getLowestSetBit(),
0154: * or -2 (either value is acceptable).
0155: *
0156: * @serial
0157: * @see #getLowestSetBit
0158: */
0159: private int lowestSetBit = -2;
0160:
0161: /**
0162: * The index of the lowest-order byte in the magnitude of this BigInteger
0163: * that contains a nonzero byte, or -2 (either value is acceptable). The
0164: * least significant byte has int-number 0, the next byte in order of
0165: * increasing significance has byte-number 1, and so forth.
0166: *
0167: * @serial
0168: */
0169: private int firstNonzeroByteNum = -2;
0170:
0171: /**
0172: * The index of the lowest-order int in the magnitude of this BigInteger
0173: * that contains a nonzero int, or -2 (either value is acceptable). The
0174: * least significant int has int-number 0, the next int in order of
0175: * increasing significance has int-number 1, and so forth.
0176: */
0177: private transient int firstNonzeroIntNum = -2;
0178:
0179: /**
0180: * This mask is used to obtain the value of an int as if it were unsigned.
0181: */
0182: private final static long LONG_MASK = 0xffffffffL;
0183:
0184: //Constructors
0185:
0186: /**
0187: * Translates a byte array containing the two's-complement binary
0188: * representation of a BigInteger into a BigInteger. The input array is
0189: * assumed to be in <i>big-endian</i> byte-order: the most significant
0190: * byte is in the zeroth element.
0191: *
0192: * @param val big-endian two's-complement binary representation of
0193: * BigInteger.
0194: * @throws NumberFormatException <tt>val</tt> is zero bytes long.
0195: */
0196: public BigInteger(byte[] val) {
0197: if (val.length == 0)
0198: throw new NumberFormatException("Zero length BigInteger");
0199:
0200: if (val[0] < 0) {
0201: mag = makePositive(val);
0202: signum = -1;
0203: } else {
0204: mag = stripLeadingZeroBytes(val);
0205: signum = (mag.length == 0 ? 0 : 1);
0206: }
0207: }
0208:
0209: /**
0210: * This private constructor translates an int array containing the
0211: * two's-complement binary representation of a BigInteger into a
0212: * BigInteger. The input array is assumed to be in <i>big-endian</i>
0213: * int-order: the most significant int is in the zeroth element.
0214: */
0215: private BigInteger(int[] val) {
0216: if (val.length == 0)
0217: throw new NumberFormatException("Zero length BigInteger");
0218:
0219: if (val[0] < 0) {
0220: mag = makePositive(val);
0221: signum = -1;
0222: } else {
0223: mag = trustedStripLeadingZeroInts(val);
0224: signum = (mag.length == 0 ? 0 : 1);
0225: }
0226: }
0227:
0228: /**
0229: * Translates the sign-magnitude representation of a BigInteger into a
0230: * BigInteger. The sign is represented as an integer signum value: -1 for
0231: * negative, 0 for zero, or 1 for positive. The magnitude is a byte array
0232: * in <i>big-endian</i> byte-order: the most significant byte is in the
0233: * zeroth element. A zero-length magnitude array is permissible, and will
0234: * result in in a BigInteger value of 0, whether signum is -1, 0 or 1.
0235: *
0236: * @param signum signum of the number (-1 for negative, 0 for zero, 1
0237: * for positive).
0238: * @param magnitude big-endian binary representation of the magnitude of
0239: * the number.
0240: * @throws NumberFormatException <tt>signum</tt> is not one of the three
0241: * legal values (-1, 0, and 1), or <tt>signum</tt> is 0 and
0242: * <tt>magnitude</tt> contains one or more non-zero bytes.
0243: */
0244: public BigInteger(int signum, byte[] magnitude) {
0245: this .mag = stripLeadingZeroBytes(magnitude);
0246:
0247: if (signum < -1 || signum > 1)
0248: throw (new NumberFormatException("Invalid signum value"));
0249:
0250: if (this .mag.length == 0) {
0251: this .signum = 0;
0252: } else {
0253: if (signum == 0)
0254: throw (new NumberFormatException(
0255: "signum-magnitude mismatch"));
0256: this .signum = signum;
0257: }
0258: }
0259:
0260: /**
0261: * A constructor for internal use that translates the sign-magnitude
0262: * representation of a BigInteger into a BigInteger. It checks the
0263: * arguments and copies the magnitude so this constructor would be
0264: * safe for external use.
0265: */
0266: private BigInteger(int signum, int[] magnitude) {
0267: this .mag = stripLeadingZeroInts(magnitude);
0268:
0269: if (signum < -1 || signum > 1)
0270: throw (new NumberFormatException("Invalid signum value"));
0271:
0272: if (this .mag.length == 0) {
0273: this .signum = 0;
0274: } else {
0275: if (signum == 0)
0276: throw (new NumberFormatException(
0277: "signum-magnitude mismatch"));
0278: this .signum = signum;
0279: }
0280: }
0281:
0282: /**
0283: * Translates the String representation of a BigInteger in the specified
0284: * radix into a BigInteger. The String representation consists of an
0285: * optional minus sign followed by a sequence of one or more digits in the
0286: * specified radix. The character-to-digit mapping is provided by
0287: * <tt>Character.digit</tt>. The String may not contain any extraneous
0288: * characters (whitespace, for example).
0289: *
0290: * @param val String representation of BigInteger.
0291: * @param radix radix to be used in interpreting <tt>val</tt>.
0292: * @throws NumberFormatException <tt>val</tt> is not a valid representation
0293: * of a BigInteger in the specified radix, or <tt>radix</tt> is
0294: * outside the range from {@link Character#MIN_RADIX} to
0295: * {@link Character#MAX_RADIX}, inclusive.
0296: * @see Character#digit
0297: */
0298: public BigInteger(String val, int radix) {
0299: int cursor = 0, numDigits;
0300: int len = val.length();
0301:
0302: if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
0303: throw new NumberFormatException("Radix out of range");
0304: if (val.length() == 0)
0305: throw new NumberFormatException("Zero length BigInteger");
0306:
0307: // Check for minus sign
0308: signum = 1;
0309: int index = val.indexOf('-');
0310: if (index != -1) {
0311: if (index == 0) {
0312: if (val.length() == 1)
0313: throw new NumberFormatException(
0314: "Zero length BigInteger");
0315: signum = -1;
0316: cursor = 1;
0317: } else {
0318: throw new NumberFormatException(
0319: "Illegal embedded minus sign");
0320: }
0321: }
0322:
0323: // Skip leading zeros and compute number of digits in magnitude
0324: while (cursor < len
0325: && Character.digit(val.charAt(cursor), radix) == 0)
0326: cursor++;
0327: if (cursor == len) {
0328: signum = 0;
0329: mag = ZERO.mag;
0330: return;
0331: } else {
0332: numDigits = len - cursor;
0333: }
0334:
0335: // Pre-allocate array of expected size. May be too large but can
0336: // never be too small. Typically exact.
0337: int numBits = (int) (((numDigits * bitsPerDigit[radix]) >>> 10) + 1);
0338: int numWords = (numBits + 31) / 32;
0339: mag = new int[numWords];
0340:
0341: // Process first (potentially short) digit group
0342: int firstGroupLen = numDigits % digitsPerInt[radix];
0343: if (firstGroupLen == 0)
0344: firstGroupLen = digitsPerInt[radix];
0345: String group = val.substring(cursor, cursor += firstGroupLen);
0346: mag[mag.length - 1] = Integer.parseInt(group, radix);
0347: if (mag[mag.length - 1] < 0)
0348: throw new NumberFormatException("Illegal digit");
0349:
0350: // Process remaining digit groups
0351: int super Radix = intRadix[radix];
0352: int groupVal = 0;
0353: while (cursor < val.length()) {
0354: group = val
0355: .substring(cursor, cursor += digitsPerInt[radix]);
0356: groupVal = Integer.parseInt(group, radix);
0357: if (groupVal < 0)
0358: throw new NumberFormatException("Illegal digit");
0359: destructiveMulAdd(mag, super Radix, groupVal);
0360: }
0361: // Required for cases where the array was overallocated.
0362: mag = trustedStripLeadingZeroInts(mag);
0363: }
0364:
0365: // Constructs a new BigInteger using a char array with radix=10
0366: BigInteger(char[] val) {
0367: int cursor = 0, numDigits;
0368: int len = val.length;
0369:
0370: // Check for leading minus sign
0371: signum = 1;
0372: if (val[0] == '-') {
0373: if (len == 1)
0374: throw new NumberFormatException(
0375: "Zero length BigInteger");
0376: signum = -1;
0377: cursor = 1;
0378: }
0379:
0380: // Skip leading zeros and compute number of digits in magnitude
0381: while (cursor < len && Character.digit(val[cursor], 10) == 0)
0382: cursor++;
0383: if (cursor == len) {
0384: signum = 0;
0385: mag = ZERO.mag;
0386: return;
0387: } else {
0388: numDigits = len - cursor;
0389: }
0390:
0391: // Pre-allocate array of expected size
0392: int numWords;
0393: if (len < 10) {
0394: numWords = 1;
0395: } else {
0396: int numBits = (int) (((numDigits * bitsPerDigit[10]) >>> 10) + 1);
0397: numWords = (numBits + 31) / 32;
0398: }
0399: mag = new int[numWords];
0400:
0401: // Process first (potentially short) digit group
0402: int firstGroupLen = numDigits % digitsPerInt[10];
0403: if (firstGroupLen == 0)
0404: firstGroupLen = digitsPerInt[10];
0405: mag[mag.length - 1] = parseInt(val, cursor,
0406: cursor += firstGroupLen);
0407:
0408: // Process remaining digit groups
0409: while (cursor < len) {
0410: int groupVal = parseInt(val, cursor,
0411: cursor += digitsPerInt[10]);
0412: destructiveMulAdd(mag, intRadix[10], groupVal);
0413: }
0414: mag = trustedStripLeadingZeroInts(mag);
0415: }
0416:
0417: // Create an integer with the digits between the two indexes
0418: // Assumes start < end. The result may be negative, but it
0419: // is to be treated as an unsigned value.
0420: private int parseInt(char[] source, int start, int end) {
0421: int result = Character.digit(source[start++], 10);
0422: if (result == -1)
0423: throw new NumberFormatException(new String(source));
0424:
0425: for (int index = start; index < end; index++) {
0426: int nextVal = Character.digit(source[index], 10);
0427: if (nextVal == -1)
0428: throw new NumberFormatException(new String(source));
0429: result = 10 * result + nextVal;
0430: }
0431:
0432: return result;
0433: }
0434:
0435: // bitsPerDigit in the given radix times 1024
0436: // Rounded up to avoid underallocation.
0437: private static long bitsPerDigit[] = { 0, 0, 1024, 1624, 2048,
0438: 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672, 3790, 3899,
0439: 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633, 4696,
0440: 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
0441: 5253, 5295 };
0442:
0443: // Multiply x array times word y in place, and add word z
0444: private static void destructiveMulAdd(int[] x, int y, int z) {
0445: // Perform the multiplication word by word
0446: long ylong = y & LONG_MASK;
0447: long zlong = z & LONG_MASK;
0448: int len = x.length;
0449:
0450: long product = 0;
0451: long carry = 0;
0452: for (int i = len - 1; i >= 0; i--) {
0453: product = ylong * (x[i] & LONG_MASK) + carry;
0454: x[i] = (int) product;
0455: carry = product >>> 32;
0456: }
0457:
0458: // Perform the addition
0459: long sum = (x[len - 1] & LONG_MASK) + zlong;
0460: x[len - 1] = (int) sum;
0461: carry = sum >>> 32;
0462: for (int i = len - 2; i >= 0; i--) {
0463: sum = (x[i] & LONG_MASK) + carry;
0464: x[i] = (int) sum;
0465: carry = sum >>> 32;
0466: }
0467: }
0468:
0469: /**
0470: * Translates the decimal String representation of a BigInteger into a
0471: * BigInteger. The String representation consists of an optional minus
0472: * sign followed by a sequence of one or more decimal digits. The
0473: * character-to-digit mapping is provided by <tt>Character.digit</tt>.
0474: * The String may not contain any extraneous characters (whitespace, for
0475: * example).
0476: *
0477: * @param val decimal String representation of BigInteger.
0478: * @throws NumberFormatException <tt>val</tt> is not a valid representation
0479: * of a BigInteger.
0480: * @see Character#digit
0481: */
0482: public BigInteger(String val) {
0483: this (val, 10);
0484: }
0485:
0486: /**
0487: * Constructs a randomly generated BigInteger, uniformly distributed over
0488: * the range <tt>0</tt> to <tt>(2<sup>numBits</sup> - 1)</tt>, inclusive.
0489: * The uniformity of the distribution assumes that a fair source of random
0490: * bits is provided in <tt>rnd</tt>. Note that this constructor always
0491: * constructs a non-negative BigInteger.
0492: *
0493: * @param numBits maximum bitLength of the new BigInteger.
0494: * @param rnd source of randomness to be used in computing the new
0495: * BigInteger.
0496: * @throws IllegalArgumentException <tt>numBits</tt> is negative.
0497: * @see #bitLength
0498: */
0499: public BigInteger(int numBits, Random rnd) {
0500: this (1, randomBits(numBits, rnd));
0501: }
0502:
0503: private static byte[] randomBits(int numBits, Random rnd) {
0504: if (numBits < 0)
0505: throw new IllegalArgumentException(
0506: "numBits must be non-negative");
0507: int numBytes = (numBits + 7) / 8;
0508: byte[] randomBits = new byte[numBytes];
0509:
0510: // Generate random bytes and mask out any excess bits
0511: if (numBytes > 0) {
0512: rnd.nextBytes(randomBits);
0513: int excessBits = 8 * numBytes - numBits;
0514: randomBits[0] &= (1 << (8 - excessBits)) - 1;
0515: }
0516: return randomBits;
0517: }
0518:
0519: /**
0520: * Constructs a randomly generated positive BigInteger that is probably
0521: * prime, with the specified bitLength.<p>
0522: *
0523: * It is recommended that the {@link #probablePrime probablePrime}
0524: * method be used in preference to this constructor unless there
0525: * is a compelling need to specify a certainty.
0526: *
0527: * @param bitLength bitLength of the returned BigInteger.
0528: * @param certainty a measure of the uncertainty that the caller is
0529: * willing to tolerate. The probability that the new BigInteger
0530: * represents a prime number will exceed
0531: * <tt>(1 - 1/2<sup>certainty</sup></tt>). The execution time of
0532: * this constructor is proportional to the value of this parameter.
0533: * @param rnd source of random bits used to select candidates to be
0534: * tested for primality.
0535: * @throws ArithmeticException <tt>bitLength < 2</tt>.
0536: * @see #bitLength
0537: */
0538: public BigInteger(int bitLength, int certainty, Random rnd) {
0539: BigInteger prime;
0540:
0541: if (bitLength < 2)
0542: throw new ArithmeticException("bitLength < 2");
0543: // The cutoff of 95 was chosen empirically for best performance
0544: prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
0545: : largePrime(bitLength, certainty, rnd));
0546: signum = 1;
0547: mag = prime.mag;
0548: }
0549:
0550: // Minimum size in bits that the requested prime number has
0551: // before we use the large prime number generating algorithms
0552: private static final int SMALL_PRIME_THRESHOLD = 95;
0553:
0554: /**
0555: * Returns a positive BigInteger that is probably prime, with the
0556: * specified bitLength. The probability that a BigInteger returned
0557: * by this method is composite does not exceed 2<sup>-100</sup>.
0558: *
0559: * @param bitLength bitLength of the returned BigInteger.
0560: * @param rnd source of random bits used to select candidates to be
0561: * tested for primality.
0562: * @return a BigInteger of <tt>bitLength</tt> bits that is probably prime
0563: * @throws ArithmeticException <tt>bitLength < 2</tt>.
0564: * @see #bitLength
0565: */
0566: private static BigInteger probablePrime(int bitLength, Random rnd) {
0567: if (bitLength < 2)
0568: throw new ArithmeticException("bitLength < 2");
0569:
0570: // The cutoff of 95 was chosen empirically for best performance
0571: return (bitLength < SMALL_PRIME_THRESHOLD ? smallPrime(
0572: bitLength, 100, rnd) : largePrime(bitLength, 100, rnd));
0573: }
0574:
0575: /**
0576: * Find a random number of the specified bitLength that is probably prime.
0577: * This method is used for smaller primes, its performance degrades on
0578: * larger bitlengths.
0579: *
0580: * This method assumes bitLength > 1.
0581: */
0582: private static BigInteger smallPrime(int bitLength, int certainty,
0583: Random rnd) {
0584: int magLen = (bitLength + 31) >>> 5;
0585: int temp[] = new int[magLen];
0586: int highBit = 1 << ((bitLength + 31) & 0x1f); // High bit of high int
0587: int highMask = (highBit << 1) - 1; // Bits to keep in high int
0588:
0589: while (true) {
0590: // Construct a candidate
0591: for (int i = 0; i < magLen; i++)
0592: temp[i] = rnd.nextInt();
0593: temp[0] = (temp[0] & highMask) | highBit; // Ensure exact length
0594: if (bitLength > 2)
0595: temp[magLen - 1] |= 1; // Make odd if bitlen > 2
0596:
0597: BigInteger p = new BigInteger(temp, 1);
0598:
0599: // Do cheap "pre-test" if applicable
0600: if (bitLength > 6) {
0601: long r = p.remainder(SMALL_PRIME_PRODUCT).longValue();
0602: if ((r % 3 == 0) || (r % 5 == 0) || (r % 7 == 0)
0603: || (r % 11 == 0) || (r % 13 == 0)
0604: || (r % 17 == 0) || (r % 19 == 0)
0605: || (r % 23 == 0) || (r % 29 == 0)
0606: || (r % 31 == 0) || (r % 37 == 0)
0607: || (r % 41 == 0))
0608: continue; // Candidate is composite; try another
0609: }
0610:
0611: // All candidates of bitLength 2 and 3 are prime by this point
0612: if (bitLength < 4)
0613: return p;
0614:
0615: // Do expensive test if we survive pre-test (or it's inapplicable)
0616: if (p.primeToCertainty(certainty))
0617: return p;
0618: }
0619: }
0620:
0621: private static final BigInteger SMALL_PRIME_PRODUCT = valueOf(3L
0622: * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41);
0623:
0624: /**
0625: * Find a random number of the specified bitLength that is probably prime.
0626: * This method is more appropriate for larger bitlengths since it uses
0627: * a sieve to eliminate most composites before using a more expensive
0628: * test.
0629: */
0630: private static BigInteger largePrime(int bitLength, int certainty,
0631: Random rnd) {
0632: BigInteger p;
0633: p = new BigInteger(bitLength, rnd).setBit(bitLength - 1);
0634: p.mag[p.mag.length - 1] &= 0xfffffffe;
0635:
0636: // Use a sieve length likely to contain the next prime number
0637: int searchLen = (bitLength / 20) * 64;
0638: BitSieve searchSieve = new BitSieve(p, searchLen);
0639: BigInteger candidate = searchSieve.retrieve(p, certainty);
0640:
0641: while ((candidate == null)
0642: || (candidate.bitLength() != bitLength)) {
0643: p = p.add(BigInteger.valueOf(2 * searchLen));
0644: if (p.bitLength() != bitLength)
0645: p = new BigInteger(bitLength, rnd)
0646: .setBit(bitLength - 1);
0647: p.mag[p.mag.length - 1] &= 0xfffffffe;
0648: searchSieve = new BitSieve(p, searchLen);
0649: candidate = searchSieve.retrieve(p, certainty);
0650: }
0651: return candidate;
0652: }
0653:
0654: /**
0655: * Returns <tt>true</tt> if this BigInteger is probably prime,
0656: * <tt>false</tt> if it's definitely composite.
0657: *
0658: * This method assumes bitLength > 2.
0659: *
0660: * @param certainty a measure of the uncertainty that the caller is
0661: * willing to tolerate: if the call returns <tt>true</tt>
0662: * the probability that this BigInteger is prime exceeds
0663: * <tt>(1 - 1/2<sup>certainty</sup>)</tt>. The execution time of
0664: * this method is proportional to the value of this parameter.
0665: * @return <tt>true</tt> if this BigInteger is probably prime,
0666: * <tt>false</tt> if it's definitely composite.
0667: */
0668: boolean primeToCertainty(int certainty) {
0669: int rounds = 0;
0670: int n = (Math.min(certainty, Integer.MAX_VALUE - 1) + 1) / 2;
0671:
0672: // The relationship between the certainty and the number of rounds
0673: // we perform is given in the draft standard ANSI X9.80, "PRIME
0674: // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
0675: int sizeInBits = this .bitLength();
0676: if (sizeInBits < 100) {
0677: rounds = 50;
0678: rounds = n < rounds ? n : rounds;
0679: return passesMillerRabin(rounds);
0680: }
0681:
0682: if (sizeInBits < 256) {
0683: rounds = 27;
0684: } else if (sizeInBits < 512) {
0685: rounds = 15;
0686: } else if (sizeInBits < 768) {
0687: rounds = 8;
0688: } else if (sizeInBits < 1024) {
0689: rounds = 4;
0690: } else {
0691: rounds = 2;
0692: }
0693: rounds = n < rounds ? n : rounds;
0694:
0695: return passesMillerRabin(rounds) && passesLucasLehmer();
0696: }
0697:
0698: /**
0699: * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
0700: *
0701: * The following assumptions are made:
0702: * This BigInteger is a positive, odd number.
0703: */
0704: private boolean passesLucasLehmer() {
0705: BigInteger this PlusOne = this .add(ONE);
0706:
0707: // Step 1
0708: int d = 5;
0709: while (jacobiSymbol(d, this ) != -1) {
0710: // 5, -7, 9, -11, ...
0711: d = (d < 0) ? Math.abs(d) + 2 : -(d + 2);
0712: }
0713:
0714: // Step 2
0715: BigInteger u = lucasLehmerSequence(d, this PlusOne, this );
0716:
0717: // Step 3
0718: return u.mod(this ).equals(ZERO);
0719: }
0720:
0721: /**
0722: * Computes Jacobi(p,n).
0723: * Assumes n is positive, odd.
0724: */
0725: int jacobiSymbol(int p, BigInteger n) {
0726: if (p == 0)
0727: return 0;
0728:
0729: // Algorithm and comments adapted from Colin Plumb's C library.
0730: int j = 1;
0731: int u = n.mag[n.mag.length - 1];
0732:
0733: // Make p positive
0734: if (p < 0) {
0735: p = -p;
0736: int n8 = u & 7;
0737: if ((n8 == 3) || (n8 == 7))
0738: j = -j; // 3 (011) or 7 (111) mod 8
0739: }
0740:
0741: // Get rid of factors of 2 in p
0742: while ((p & 3) == 0)
0743: p >>= 2;
0744: if ((p & 1) == 0) {
0745: p >>= 1;
0746: if (((u ^ u >> 1) & 2) != 0)
0747: j = -j; // 3 (011) or 5 (101) mod 8
0748: }
0749: if (p == 1)
0750: return j;
0751: // Then, apply quadratic reciprocity
0752: if ((p & u & 2) != 0) // p = u = 3 (mod 4)?
0753: j = -j;
0754: // And reduce u mod p
0755: u = n.mod(BigInteger.valueOf(p)).intValue();
0756:
0757: // Now compute Jacobi(u,p), u < p
0758: while (u != 0) {
0759: while ((u & 3) == 0)
0760: u >>= 2;
0761: if ((u & 1) == 0) {
0762: u >>= 1;
0763: if (((p ^ p >> 1) & 2) != 0)
0764: j = -j; // 3 (011) or 5 (101) mod 8
0765: }
0766: if (u == 1)
0767: return j;
0768: // Now both u and p are odd, so use quadratic reciprocity
0769: if (u < p) {
0770: int t = u;
0771: u = p;
0772: p = t;
0773: if ((u & p & 2) != 0)// u = p = 3 (mod 4)?
0774: j = -j;
0775: }
0776: // Now u >= p, so it can be reduced
0777: u %= p;
0778: }
0779: return 0;
0780: }
0781:
0782: private static BigInteger lucasLehmerSequence(int z, BigInteger k,
0783: BigInteger n) {
0784: BigInteger d = BigInteger.valueOf(z);
0785: BigInteger u = ONE;
0786: BigInteger u2;
0787: BigInteger v = ONE;
0788: BigInteger v2;
0789:
0790: for (int i = k.bitLength() - 2; i >= 0; i--) {
0791: u2 = u.multiply(v).mod(n);
0792:
0793: v2 = v.square().add(d.multiply(u.square())).mod(n);
0794: if (v2.testBit(0)) {
0795: v2 = n.subtract(v2);
0796: v2.signum = -v2.signum;
0797: }
0798: v2 = v2.shiftRight(1);
0799:
0800: u = u2;
0801: v = v2;
0802: if (k.testBit(i)) {
0803: u2 = u.add(v).mod(n);
0804: if (u2.testBit(0)) {
0805: u2 = n.subtract(u2);
0806: u2.signum = -u2.signum;
0807: }
0808: u2 = u2.shiftRight(1);
0809:
0810: v2 = v.add(d.multiply(u)).mod(n);
0811: if (v2.testBit(0)) {
0812: v2 = n.subtract(v2);
0813: v2.signum = -v2.signum;
0814: }
0815: v2 = v2.shiftRight(1);
0816:
0817: u = u2;
0818: v = v2;
0819: }
0820: }
0821: return u;
0822: }
0823:
0824: /**
0825: * Returns true iff this BigInteger passes the specified number of
0826: * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
0827: * 186-2).
0828: *
0829: * The following assumptions are made:
0830: * This BigInteger is a positive, odd number greater than 2.
0831: * iterations<=50.
0832: */
0833: private boolean passesMillerRabin(int iterations) {
0834: // Find a and m such that m is odd and this == 1 + 2**a * m
0835: BigInteger this MinusOne = this .subtract(ONE);
0836: BigInteger m = this MinusOne;
0837: int a = m.getLowestSetBit();
0838: m = m.shiftRight(a);
0839:
0840: // Do the tests
0841: Random rnd = new Random();
0842: for (int i = 0; i < iterations; i++) {
0843: // Generate a uniform random on (1, this)
0844: BigInteger b;
0845: do {
0846: b = new BigInteger(this .bitLength(), rnd);
0847: } while (b.compareTo(ONE) <= 0 || b.compareTo(this ) >= 0);
0848:
0849: int j = 0;
0850: BigInteger z = b.modPow(m, this );
0851: while (!((j == 0 && z.equals(ONE)) || z
0852: .equals(this MinusOne))) {
0853: if (j > 0 && z.equals(ONE) || ++j == a)
0854: return false;
0855: z = z.modPow(TWO, this );
0856: }
0857: }
0858: return true;
0859: }
0860:
0861: /**
0862: * This private constructor differs from its public cousin
0863: * with the arguments reversed in two ways: it assumes that its
0864: * arguments are correct, and it doesn't copy the magnitude array.
0865: */
0866: private BigInteger(int[] magnitude, int signum) {
0867: this .signum = (magnitude.length == 0 ? 0 : signum);
0868: this .mag = magnitude;
0869: }
0870:
0871: /**
0872: * This private constructor is for internal use and assumes that its
0873: * arguments are correct.
0874: */
0875: private BigInteger(byte[] magnitude, int signum) {
0876: this .signum = (magnitude.length == 0 ? 0 : signum);
0877: this .mag = stripLeadingZeroBytes(magnitude);
0878: }
0879:
0880: /**
0881: * This private constructor is for internal use in converting
0882: * from a MutableBigInteger object into a BigInteger.
0883: */
0884: BigInteger(MutableBigInteger val, int sign) {
0885: if (val.offset > 0 || val.value.length != val.intLen) {
0886: mag = new int[val.intLen];
0887: for (int i = 0; i < val.intLen; i++)
0888: mag[i] = val.value[val.offset + i];
0889: } else {
0890: mag = val.value;
0891: }
0892:
0893: this .signum = (val.intLen == 0) ? 0 : sign;
0894: }
0895:
0896: //Static Factory Methods
0897:
0898: /**
0899: * Returns a BigInteger whose value is equal to that of the
0900: * specified <code>long</code>. This "static factory method" is
0901: * provided in preference to a (<code>long</code>) constructor
0902: * because it allows for reuse of frequently used BigIntegers.
0903: *
0904: * @param val value of the BigInteger to return.
0905: * @return a BigInteger with the specified value.
0906: */
0907: public static BigInteger valueOf(long val) {
0908: // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
0909: if (val == 0)
0910: return ZERO;
0911: if (val > 0 && val <= MAX_CONSTANT)
0912: return posConst[(int) val];
0913: else if (val < 0 && val >= -MAX_CONSTANT)
0914: return negConst[(int) -val];
0915:
0916: return new BigInteger(val);
0917: }
0918:
0919: /**
0920: * Constructs a BigInteger with the specified value, which may not be zero.
0921: */
0922: private BigInteger(long val) {
0923: if (val < 0) {
0924: signum = -1;
0925: val = -val;
0926: } else {
0927: signum = 1;
0928: }
0929:
0930: int highWord = (int) (val >>> 32);
0931: if (highWord == 0) {
0932: mag = new int[1];
0933: mag[0] = (int) val;
0934: } else {
0935: mag = new int[2];
0936: mag[0] = highWord;
0937: mag[1] = (int) val;
0938: }
0939: }
0940:
0941: /**
0942: * Returns a BigInteger with the given two's complement representation.
0943: * Assumes that the input array will not be modified (the returned
0944: * BigInteger will reference the input array if feasible).
0945: */
0946: private static BigInteger valueOf(int val[]) {
0947: return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(
0948: val));
0949: }
0950:
0951: // Constants
0952:
0953: /**
0954: * Initialize static constant array when class is loaded.
0955: */
0956: private final static int MAX_CONSTANT = 16;
0957: private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT + 1];
0958: private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT + 1];
0959: static {
0960: for (int i = 1; i <= MAX_CONSTANT; i++) {
0961: int[] magnitude = new int[1];
0962: magnitude[0] = (int) i;
0963: posConst[i] = new BigInteger(magnitude, 1);
0964: negConst[i] = new BigInteger(magnitude, -1);
0965: }
0966: }
0967:
0968: /**
0969: * The BigInteger constant zero.
0970: *
0971: * @since 1.2
0972: */
0973: public static final BigInteger ZERO = new BigInteger(new int[0], 0);
0974:
0975: /**
0976: * The BigInteger constant one.
0977: *
0978: * @since 1.2
0979: */
0980: public static final BigInteger ONE = valueOf(1);
0981:
0982: /**
0983: * The BigInteger constant two. (Not exported.)
0984: */
0985: private static final BigInteger TWO = valueOf(2);
0986:
0987: // Arithmetic Operations
0988:
0989: /**
0990: * Returns a BigInteger whose value is <tt>(this + val)</tt>.
0991: *
0992: * @param val value to be added to this BigInteger.
0993: * @return <tt>this + val</tt>
0994: */
0995: public BigInteger add(BigInteger val) {
0996: int[] resultMag;
0997: if (val.signum == 0)
0998: return this ;
0999: if (signum == 0)
1000: return val;
1001: if (val.signum == signum)
1002: return new BigInteger(add(mag, val.mag), signum);
1003:
1004: int cmp = intArrayCmp(mag, val.mag);
1005: if (cmp == 0)
1006: return ZERO;
1007: resultMag = (cmp > 0 ? subtract(mag, val.mag) : subtract(
1008: val.mag, mag));
1009: resultMag = trustedStripLeadingZeroInts(resultMag);
1010:
1011: return new BigInteger(resultMag, cmp * signum);
1012: }
1013:
1014: /**
1015: * Adds the contents of the int arrays x and y. This method allocates
1016: * a new int array to hold the answer and returns a reference to that
1017: * array.
1018: */
1019: private static int[] add(int[] x, int[] y) {
1020: // If x is shorter, swap the two arrays
1021: if (x.length < y.length) {
1022: int[] tmp = x;
1023: x = y;
1024: y = tmp;
1025: }
1026:
1027: int xIndex = x.length;
1028: int yIndex = y.length;
1029: int result[] = new int[xIndex];
1030: long sum = 0;
1031:
1032: // Add common parts of both numbers
1033: while (yIndex > 0) {
1034: sum = (x[--xIndex] & LONG_MASK) + (y[--yIndex] & LONG_MASK)
1035: + (sum >>> 32);
1036: result[xIndex] = (int) sum;
1037: }
1038:
1039: // Copy remainder of longer number while carry propagation is required
1040: boolean carry = (sum >>> 32 != 0);
1041: while (xIndex > 0 && carry)
1042: carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1043:
1044: // Copy remainder of longer number
1045: while (xIndex > 0)
1046: result[--xIndex] = x[xIndex];
1047:
1048: // Grow result if necessary
1049: if (carry) {
1050: int newLen = result.length + 1;
1051: int temp[] = new int[newLen];
1052: for (int i = 1; i < newLen; i++)
1053: temp[i] = result[i - 1];
1054: temp[0] = 0x01;
1055: result = temp;
1056: }
1057: return result;
1058: }
1059:
1060: /**
1061: * Returns a BigInteger whose value is <tt>(this - val)</tt>.
1062: *
1063: * @param val value to be subtracted from this BigInteger.
1064: * @return <tt>this - val</tt>
1065: */
1066: public BigInteger subtract(BigInteger val) {
1067: int[] resultMag;
1068: if (val.signum == 0)
1069: return this ;
1070: if (signum == 0)
1071: return val.negate();
1072: if (val.signum != signum)
1073: return new BigInteger(add(mag, val.mag), signum);
1074:
1075: int cmp = intArrayCmp(mag, val.mag);
1076: if (cmp == 0)
1077: return ZERO;
1078: resultMag = (cmp > 0 ? subtract(mag, val.mag) : subtract(
1079: val.mag, mag));
1080: resultMag = trustedStripLeadingZeroInts(resultMag);
1081: return new BigInteger(resultMag, cmp * signum);
1082: }
1083:
1084: /**
1085: * Subtracts the contents of the second int arrays (little) from the
1086: * first (big). The first int array (big) must represent a larger number
1087: * than the second. This method allocates the space necessary to hold the
1088: * answer.
1089: */
1090: private static int[] subtract(int[] big, int[] little) {
1091: int bigIndex = big.length;
1092: int result[] = new int[bigIndex];
1093: int littleIndex = little.length;
1094: long difference = 0;
1095:
1096: // Subtract common parts of both numbers
1097: while (littleIndex > 0) {
1098: difference = (big[--bigIndex] & LONG_MASK)
1099: - (little[--littleIndex] & LONG_MASK)
1100: + (difference >> 32);
1101: result[bigIndex] = (int) difference;
1102: }
1103:
1104: // Subtract remainder of longer number while borrow propagates
1105: boolean borrow = (difference >> 32 != 0);
1106: while (bigIndex > 0 && borrow)
1107: borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1108:
1109: // Copy remainder of longer number
1110: while (bigIndex > 0)
1111: result[--bigIndex] = big[bigIndex];
1112:
1113: return result;
1114: }
1115:
1116: /**
1117: * Returns a BigInteger whose value is <tt>(this * val)</tt>.
1118: *
1119: * @param val value to be multiplied by this BigInteger.
1120: * @return <tt>this * val</tt>
1121: */
1122: public BigInteger multiply(BigInteger val) {
1123: if (signum == 0 || val.signum == 0)
1124: return ZERO;
1125:
1126: int[] result = multiplyToLen(mag, mag.length, val.mag,
1127: val.mag.length, null);
1128: result = trustedStripLeadingZeroInts(result);
1129: return new BigInteger(result, signum * val.signum);
1130: }
1131:
1132: /**
1133: * Multiplies int arrays x and y to the specified lengths and places
1134: * the result into z.
1135: */
1136: private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen,
1137: int[] z) {
1138: int xstart = xlen - 1;
1139: int ystart = ylen - 1;
1140:
1141: if (z == null || z.length < (xlen + ylen))
1142: z = new int[xlen + ylen];
1143:
1144: long carry = 0;
1145: for (int j = ystart, k = ystart + 1 + xstart; j >= 0; j--, k--) {
1146: long product = (y[j] & LONG_MASK) * (x[xstart] & LONG_MASK)
1147: + carry;
1148: z[k] = (int) product;
1149: carry = product >>> 32;
1150: }
1151: z[xstart] = (int) carry;
1152:
1153: for (int i = xstart - 1; i >= 0; i--) {
1154: carry = 0;
1155: for (int j = ystart, k = ystart + 1 + i; j >= 0; j--, k--) {
1156: long product = (y[j] & LONG_MASK) * (x[i] & LONG_MASK)
1157: + (z[k] & LONG_MASK) + carry;
1158: z[k] = (int) product;
1159: carry = product >>> 32;
1160: }
1161: z[i] = (int) carry;
1162: }
1163: return z;
1164: }
1165:
1166: /**
1167: * Returns a BigInteger whose value is <tt>(this<sup>2</sup>)</tt>.
1168: *
1169: * @return <tt>this<sup>2</sup></tt>
1170: */
1171: private BigInteger square() {
1172: if (signum == 0)
1173: return ZERO;
1174: int[] z = squareToLen(mag, mag.length, null);
1175: return new BigInteger(trustedStripLeadingZeroInts(z), 1);
1176: }
1177:
1178: /**
1179: * Squares the contents of the int array x. The result is placed into the
1180: * int array z. The contents of x are not changed.
1181: */
1182: private static final int[] squareToLen(int[] x, int len, int[] z) {
1183: /*
1184: * The algorithm used here is adapted from Colin Plumb's C library.
1185: * Technique: Consider the partial products in the multiplication
1186: * of "abcde" by itself:
1187: *
1188: * a b c d e
1189: * * a b c d e
1190: * ==================
1191: * ae be ce de ee
1192: * ad bd cd dd de
1193: * ac bc cc cd ce
1194: * ab bb bc bd be
1195: * aa ab ac ad ae
1196: *
1197: * Note that everything above the main diagonal:
1198: * ae be ce de = (abcd) * e
1199: * ad bd cd = (abc) * d
1200: * ac bc = (ab) * c
1201: * ab = (a) * b
1202: *
1203: * is a copy of everything below the main diagonal:
1204: * de
1205: * cd ce
1206: * bc bd be
1207: * ab ac ad ae
1208: *
1209: * Thus, the sum is 2 * (off the diagonal) + diagonal.
1210: *
1211: * This is accumulated beginning with the diagonal (which
1212: * consist of the squares of the digits of the input), which is then
1213: * divided by two, the off-diagonal added, and multiplied by two
1214: * again. The low bit is simply a copy of the low bit of the
1215: * input, so it doesn't need special care.
1216: */
1217: int zlen = len << 1;
1218: if (z == null || z.length < zlen)
1219: z = new int[zlen];
1220:
1221: // Store the squares, right shifted one bit (i.e., divided by 2)
1222: int lastProductLowWord = 0;
1223: for (int j = 0, i = 0; j < len; j++) {
1224: long piece = (x[j] & LONG_MASK);
1225: long product = piece * piece;
1226: z[i++] = (lastProductLowWord << 31)
1227: | (int) (product >>> 33);
1228: z[i++] = (int) (product >>> 1);
1229: lastProductLowWord = (int) product;
1230: }
1231:
1232: // Add in off-diagonal sums
1233: for (int i = len, offset = 1; i > 0; i--, offset += 2) {
1234: int t = x[i - 1];
1235: t = mulAdd(z, x, offset, i - 1, t);
1236: addOne(z, offset - 1, i, t);
1237: }
1238:
1239: // Shift back up and set low bit
1240: primitiveLeftShift(z, zlen, 1);
1241: z[zlen - 1] |= x[len - 1] & 1;
1242:
1243: return z;
1244: }
1245:
1246: /**
1247: * Returns a BigInteger whose value is <tt>(this / val)</tt>.
1248: *
1249: * @param val value by which this BigInteger is to be divided.
1250: * @return <tt>this / val</tt>
1251: * @throws ArithmeticException <tt>val==0</tt>
1252: */
1253: public BigInteger divide(BigInteger val) {
1254: MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
1255: this .mag), b = new MutableBigInteger(val.mag);
1256:
1257: a.divide(b, q, r);
1258: return new BigInteger(q, this .signum * val.signum);
1259: }
1260:
1261: /**
1262: * Returns an array of two BigIntegers containing <tt>(this / val)</tt>
1263: * followed by <tt>(this % val)</tt>.
1264: *
1265: * @param val value by which this BigInteger is to be divided, and the
1266: * remainder computed.
1267: * @return an array of two BigIntegers: the quotient <tt>(this / val)</tt>
1268: * is the initial element, and the remainder <tt>(this % val)</tt>
1269: * is the final element.
1270: * @throws ArithmeticException <tt>val==0</tt>
1271: */
1272: public BigInteger[] divideAndRemainder(BigInteger val) {
1273: BigInteger[] result = new BigInteger[2];
1274: MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
1275: this .mag), b = new MutableBigInteger(val.mag);
1276: a.divide(b, q, r);
1277: result[0] = new BigInteger(q, this .signum * val.signum);
1278: result[1] = new BigInteger(r, this .signum);
1279: return result;
1280: }
1281:
1282: /**
1283: * Returns a BigInteger whose value is <tt>(this % val)</tt>.
1284: *
1285: * @param val value by which this BigInteger is to be divided, and the
1286: * remainder computed.
1287: * @return <tt>this % val</tt>
1288: * @throws ArithmeticException <tt>val==0</tt>
1289: */
1290: public BigInteger remainder(BigInteger val) {
1291: MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
1292: this .mag), b = new MutableBigInteger(val.mag);
1293:
1294: a.divide(b, q, r);
1295: return new BigInteger(r, this .signum);
1296: }
1297:
1298: /**
1299: * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
1300: * Note that <tt>exponent</tt> is an integer rather than a BigInteger.
1301: *
1302: * @param exponent exponent to which this BigInteger is to be raised.
1303: * @return <tt>this<sup>exponent</sup></tt>
1304: * @throws ArithmeticException <tt>exponent</tt> is negative. (This would
1305: * cause the operation to yield a non-integer value.)
1306: */
1307: public BigInteger pow(int exponent) {
1308: if (exponent < 0)
1309: throw new ArithmeticException("Negative exponent");
1310: if (signum == 0)
1311: return (exponent == 0 ? ONE : this );
1312:
1313: // Perform exponentiation using repeated squaring method
1314: int newSign = (signum < 0 && (exponent & 1) == 1 ? -1 : 1);
1315: int[] baseToPow2 = this .mag;
1316: int[] result = { 1 };
1317:
1318: while (exponent != 0) {
1319: if ((exponent & 1) == 1) {
1320: result = multiplyToLen(result, result.length,
1321: baseToPow2, baseToPow2.length, null);
1322: result = trustedStripLeadingZeroInts(result);
1323: }
1324: if ((exponent >>>= 1) != 0) {
1325: baseToPow2 = squareToLen(baseToPow2, baseToPow2.length,
1326: null);
1327: baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
1328: }
1329: }
1330: return new BigInteger(result, newSign);
1331: }
1332:
1333: /**
1334: * Returns a BigInteger whose value is the greatest common divisor of
1335: * <tt>abs(this)</tt> and <tt>abs(val)</tt>. Returns 0 if
1336: * <tt>this==0 && val==0</tt>.
1337: *
1338: * @param val value with with the GCD is to be computed.
1339: * @return <tt>GCD(abs(this), abs(val))</tt>
1340: */
1341: public BigInteger gcd(BigInteger val) {
1342: if (val.signum == 0)
1343: return this .abs();
1344: else if (this .signum == 0)
1345: return val.abs();
1346:
1347: MutableBigInteger a = new MutableBigInteger(this );
1348: MutableBigInteger b = new MutableBigInteger(val);
1349:
1350: MutableBigInteger result = a.hybridGCD(b);
1351:
1352: return new BigInteger(result, 1);
1353: }
1354:
1355: /**
1356: * Left shift int array a up to len by n bits. Returns the array that
1357: * results from the shift since space may have to be reallocated.
1358: */
1359: private static int[] leftShift(int[] a, int len, int n) {
1360: int nInts = n >>> 5;
1361: int nBits = n & 0x1F;
1362: int bitsInHighWord = bitLen(a[0]);
1363:
1364: // If shift can be done without recopy, do so
1365: if (n <= (32 - bitsInHighWord)) {
1366: primitiveLeftShift(a, len, nBits);
1367: return a;
1368: } else { // Array must be resized
1369: if (nBits <= (32 - bitsInHighWord)) {
1370: int result[] = new int[nInts + len];
1371: for (int i = 0; i < len; i++)
1372: result[i] = a[i];
1373: primitiveLeftShift(result, result.length, nBits);
1374: return result;
1375: } else {
1376: int result[] = new int[nInts + len + 1];
1377: for (int i = 0; i < len; i++)
1378: result[i] = a[i];
1379: primitiveRightShift(result, result.length, 32 - nBits);
1380: return result;
1381: }
1382: }
1383: }
1384:
1385: // shifts a up to len right n bits assumes no leading zeros, 0<n<32
1386: static void primitiveRightShift(int[] a, int len, int n) {
1387: int n2 = 32 - n;
1388: for (int i = len - 1, c = a[i]; i > 0; i--) {
1389: int b = c;
1390: c = a[i - 1];
1391: a[i] = (c << n2) | (b >>> n);
1392: }
1393: a[0] >>>= n;
1394: }
1395:
1396: // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
1397: static void primitiveLeftShift(int[] a, int len, int n) {
1398: if (len == 0 || n == 0)
1399: return;
1400:
1401: int n2 = 32 - n;
1402: for (int i = 0, c = a[i], m = i + len - 1; i < m; i++) {
1403: int b = c;
1404: c = a[i + 1];
1405: a[i] = (b << n) | (c >>> n2);
1406: }
1407: a[len - 1] <<= n;
1408: }
1409:
1410: /**
1411: * Calculate bitlength of contents of the first len elements an int array,
1412: * assuming there are no leading zero ints.
1413: */
1414: private static int bitLength(int[] val, int len) {
1415: if (len == 0)
1416: return 0;
1417: return ((len - 1) << 5) + bitLen(val[0]);
1418: }
1419:
1420: /**
1421: * Returns a BigInteger whose value is the absolute value of this
1422: * BigInteger.
1423: *
1424: * @return <tt>abs(this)</tt>
1425: */
1426: public BigInteger abs() {
1427: return (signum >= 0 ? this : this .negate());
1428: }
1429:
1430: /**
1431: * Returns a BigInteger whose value is <tt>(-this)</tt>.
1432: *
1433: * @return <tt>-this</tt>
1434: */
1435: public BigInteger negate() {
1436: return new BigInteger(this .mag, -this .signum);
1437: }
1438:
1439: /**
1440: * Returns the signum function of this BigInteger.
1441: *
1442: * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
1443: * positive.
1444: */
1445: public int signum() {
1446: return this .signum;
1447: }
1448:
1449: // Modular Arithmetic Operations
1450:
1451: /**
1452: * Returns a BigInteger whose value is <tt>(this mod m</tt>). This method
1453: * differs from <tt>remainder</tt> in that it always returns a
1454: * <i>non-negative</i> BigInteger.
1455: *
1456: * @param m the modulus.
1457: * @return <tt>this mod m</tt>
1458: * @throws ArithmeticException <tt>m <= 0</tt>
1459: * @see #remainder
1460: */
1461: public BigInteger mod(BigInteger m) {
1462: if (m.signum <= 0)
1463: throw new ArithmeticException(
1464: "BigInteger: modulus not positive");
1465:
1466: BigInteger result = this .remainder(m);
1467: return (result.signum >= 0 ? result : result.add(m));
1468: }
1469:
1470: /**
1471: * Returns a BigInteger whose value is
1472: * <tt>(this<sup>exponent</sup> mod m)</tt>. (Unlike <tt>pow</tt>, this
1473: * method permits negative exponents.)
1474: *
1475: * @param exponent the exponent.
1476: * @param m the modulus.
1477: * @return <tt>this<sup>exponent</sup> mod m</tt>
1478: * @throws ArithmeticException <tt>m <= 0</tt>
1479: * @see #modInverse
1480: */
1481: public BigInteger modPow(BigInteger exponent, BigInteger m) {
1482: if (m.signum <= 0)
1483: throw new ArithmeticException(
1484: "BigInteger: modulus not positive");
1485:
1486: // Trivial cases
1487: if (exponent.signum == 0)
1488: return (m.equals(ONE) ? ZERO : ONE);
1489:
1490: if (this .equals(ONE))
1491: return (m.equals(ONE) ? ZERO : ONE);
1492:
1493: if (this .equals(ZERO) && exponent.signum >= 0)
1494: return ZERO;
1495:
1496: if (this .equals(negConst[1]) && (!exponent.testBit(0)))
1497: return (m.equals(ONE) ? ZERO : ONE);
1498:
1499: boolean invertResult;
1500: if ((invertResult = (exponent.signum < 0)))
1501: exponent = exponent.negate();
1502:
1503: BigInteger base = (this .signum < 0 || this .compareTo(m) >= 0 ? this
1504: .mod(m)
1505: : this );
1506: BigInteger result;
1507: if (m.testBit(0)) { // odd modulus
1508: result = base.oddModPow(exponent, m);
1509: } else {
1510: /*
1511: * Even modulus. Tear it into an "odd part" (m1) and power of two
1512: * (m2), exponentiate mod m1, manually exponentiate mod m2, and
1513: * use Chinese Remainder Theorem to combine results.
1514: */
1515:
1516: // Tear m apart into odd part (m1) and power of 2 (m2)
1517: int p = m.getLowestSetBit(); // Max pow of 2 that divides m
1518:
1519: BigInteger m1 = m.shiftRight(p); // m/2**p
1520: BigInteger m2 = ONE.shiftLeft(p); // 2**p
1521:
1522: // Calculate new base from m1
1523: BigInteger base2 = (this .signum < 0
1524: || this .compareTo(m1) >= 0 ? this .mod(m1) : this );
1525:
1526: // Caculate (base ** exponent) mod m1.
1527: BigInteger a1 = (m1.equals(ONE) ? ZERO : base2.oddModPow(
1528: exponent, m1));
1529:
1530: // Calculate (this ** exponent) mod m2
1531: BigInteger a2 = base.modPow2(exponent, p);
1532:
1533: // Combine results using Chinese Remainder Theorem
1534: BigInteger y1 = m2.modInverse(m1);
1535: BigInteger y2 = m1.modInverse(m2);
1536:
1537: result = a1.multiply(m2).multiply(y1).add(
1538: a2.multiply(m1).multiply(y2)).mod(m);
1539: }
1540:
1541: return (invertResult ? result.modInverse(m) : result);
1542: }
1543:
1544: static int[] bnExpModThreshTable = { 7, 25, 81, 241, 673, 1793,
1545: Integer.MAX_VALUE }; // Sentinel
1546:
1547: /**
1548: * Returns a BigInteger whose value is x to the power of y mod z.
1549: * Assumes: z is odd && x < z.
1550: */
1551: private BigInteger oddModPow(BigInteger y, BigInteger z) {
1552: /*
1553: * The algorithm is adapted from Colin Plumb's C library.
1554: *
1555: * The window algorithm:
1556: * The idea is to keep a running product of b1 = n^(high-order bits of exp)
1557: * and then keep appending exponent bits to it. The following patterns
1558: * apply to a 3-bit window (k = 3):
1559: * To append 0: square
1560: * To append 1: square, multiply by n^1
1561: * To append 10: square, multiply by n^1, square
1562: * To append 11: square, square, multiply by n^3
1563: * To append 100: square, multiply by n^1, square, square
1564: * To append 101: square, square, square, multiply by n^5
1565: * To append 110: square, square, multiply by n^3, square
1566: * To append 111: square, square, square, multiply by n^7
1567: *
1568: * Since each pattern involves only one multiply, the longer the pattern
1569: * the better, except that a 0 (no multiplies) can be appended directly.
1570: * We precompute a table of odd powers of n, up to 2^k, and can then
1571: * multiply k bits of exponent at a time. Actually, assuming random
1572: * exponents, there is on average one zero bit between needs to
1573: * multiply (1/2 of the time there's none, 1/4 of the time there's 1,
1574: * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so
1575: * you have to do one multiply per k+1 bits of exponent.
1576: *
1577: * The loop walks down the exponent, squaring the result buffer as
1578: * it goes. There is a wbits+1 bit lookahead buffer, buf, that is
1579: * filled with the upcoming exponent bits. (What is read after the
1580: * end of the exponent is unimportant, but it is filled with zero here.)
1581: * When the most-significant bit of this buffer becomes set, i.e.
1582: * (buf & tblmask) != 0, we have to decide what pattern to multiply
1583: * by, and when to do it. We decide, remember to do it in future
1584: * after a suitable number of squarings have passed (e.g. a pattern
1585: * of "100" in the buffer requires that we multiply by n^1 immediately;
1586: * a pattern of "110" calls for multiplying by n^3 after one more
1587: * squaring), clear the buffer, and continue.
1588: *
1589: * When we start, there is one more optimization: the result buffer
1590: * is implcitly one, so squaring it or multiplying by it can be
1591: * optimized away. Further, if we start with a pattern like "100"
1592: * in the lookahead window, rather than placing n into the buffer
1593: * and then starting to square it, we have already computed n^2
1594: * to compute the odd-powers table, so we can place that into
1595: * the buffer and save a squaring.
1596: *
1597: * This means that if you have a k-bit window, to compute n^z,
1598: * where z is the high k bits of the exponent, 1/2 of the time
1599: * it requires no squarings. 1/4 of the time, it requires 1
1600: * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
1601: * And the remaining 1/2^(k-1) of the time, the top k bits are a
1602: * 1 followed by k-1 0 bits, so it again only requires k-2
1603: * squarings, not k-1. The average of these is 1. Add that
1604: * to the one squaring we have to do to compute the table,
1605: * and you'll see that a k-bit window saves k-2 squarings
1606: * as well as reducing the multiplies. (It actually doesn't
1607: * hurt in the case k = 1, either.)
1608: */
1609: // Special case for exponent of one
1610: if (y.equals(ONE))
1611: return this ;
1612:
1613: // Special case for base of zero
1614: if (signum == 0)
1615: return ZERO;
1616:
1617: int[] base = (int[]) mag.clone();
1618: int[] exp = y.mag;
1619: int[] mod = z.mag;
1620: int modLen = mod.length;
1621:
1622: // Select an appropriate window size
1623: int wbits = 0;
1624: int ebits = bitLength(exp, exp.length);
1625: while (ebits > bnExpModThreshTable[wbits])
1626: wbits++;
1627:
1628: // Calculate appropriate table size
1629: int tblmask = 1 << wbits;
1630:
1631: // Allocate table for precomputed odd powers of base in Montgomery form
1632: int[][] table = new int[tblmask][];
1633: for (int i = 0; i < tblmask; i++)
1634: table[i] = new int[modLen];
1635:
1636: // Compute the modular inverse
1637: int inv = -MutableBigInteger.inverseMod32(mod[modLen - 1]);
1638:
1639: // Convert base to Montgomery form
1640: int[] a = leftShift(base, base.length, modLen << 5);
1641:
1642: MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a2 = new MutableBigInteger(
1643: a), b2 = new MutableBigInteger(mod);
1644:
1645: a2.divide(b2, q, r);
1646: table[0] = r.toIntArray();
1647:
1648: // Pad table[0] with leading zeros so its length is at least modLen
1649: if (table[0].length < modLen) {
1650: int offset = modLen - table[0].length;
1651: int[] t2 = new int[modLen];
1652: for (int i = 0; i < table[0].length; i++)
1653: t2[i + offset] = table[0][i];
1654: table[0] = t2;
1655: }
1656:
1657: // Set b to the square of the base
1658: int[] b = squareToLen(table[0], modLen, null);
1659: b = montReduce(b, mod, modLen, inv);
1660:
1661: // Set t to high half of b
1662: int[] t = new int[modLen];
1663: for (int i = 0; i < modLen; i++)
1664: t[i] = b[i];
1665:
1666: // Fill in the table with odd powers of the base
1667: for (int i = 1; i < tblmask; i++) {
1668: int[] prod = multiplyToLen(t, modLen, table[i - 1], modLen,
1669: null);
1670: table[i] = montReduce(prod, mod, modLen, inv);
1671: }
1672:
1673: // Pre load the window that slides over the exponent
1674: int bitpos = 1 << ((ebits - 1) & (32 - 1));
1675:
1676: int buf = 0;
1677: int elen = exp.length;
1678: int eIndex = 0;
1679: for (int i = 0; i <= wbits; i++) {
1680: buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0) ? 1 : 0);
1681: bitpos >>>= 1;
1682: if (bitpos == 0) {
1683: eIndex++;
1684: bitpos = 1 << (32 - 1);
1685: elen--;
1686: }
1687: }
1688:
1689: int multpos = ebits;
1690:
1691: // The first iteration, which is hoisted out of the main loop
1692: ebits--;
1693: boolean isone = true;
1694:
1695: multpos = ebits - wbits;
1696: while ((buf & 1) == 0) {
1697: buf >>>= 1;
1698: multpos++;
1699: }
1700:
1701: int[] mult = table[buf >>> 1];
1702:
1703: buf = 0;
1704: if (multpos == ebits)
1705: isone = false;
1706:
1707: // The main loop
1708: while (true) {
1709: ebits--;
1710: // Advance the window
1711: buf <<= 1;
1712:
1713: if (elen != 0) {
1714: buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0;
1715: bitpos >>>= 1;
1716: if (bitpos == 0) {
1717: eIndex++;
1718: bitpos = 1 << (32 - 1);
1719: elen--;
1720: }
1721: }
1722:
1723: // Examine the window for pending multiplies
1724: if ((buf & tblmask) != 0) {
1725: multpos = ebits - wbits;
1726: while ((buf & 1) == 0) {
1727: buf >>>= 1;
1728: multpos++;
1729: }
1730: mult = table[buf >>> 1];
1731: buf = 0;
1732: }
1733:
1734: // Perform multiply
1735: if (ebits == multpos) {
1736: if (isone) {
1737: b = (int[]) mult.clone();
1738: isone = false;
1739: } else {
1740: t = b;
1741: a = multiplyToLen(t, modLen, mult, modLen, a);
1742: a = montReduce(a, mod, modLen, inv);
1743: t = a;
1744: a = b;
1745: b = t;
1746: }
1747: }
1748:
1749: // Check if done
1750: if (ebits == 0)
1751: break;
1752:
1753: // Square the input
1754: if (!isone) {
1755: t = b;
1756: a = squareToLen(t, modLen, a);
1757: a = montReduce(a, mod, modLen, inv);
1758: t = a;
1759: a = b;
1760: b = t;
1761: }
1762: }
1763:
1764: // Convert result out of Montgomery form and return
1765: int[] t2 = new int[2 * modLen];
1766: for (int i = 0; i < modLen; i++)
1767: t2[i + modLen] = b[i];
1768:
1769: b = montReduce(t2, mod, modLen, inv);
1770:
1771: t2 = new int[modLen];
1772: for (int i = 0; i < modLen; i++)
1773: t2[i] = b[i];
1774:
1775: return new BigInteger(1, t2);
1776: }
1777:
1778: /**
1779: * Montgomery reduce n, modulo mod. This reduces modulo mod and divides
1780: * by 2^(32*mlen). Adapted from Colin Plumb's C library.
1781: */
1782: private static int[] montReduce(int[] n, int[] mod, int mlen,
1783: int inv) {
1784: int c = 0;
1785: int len = mlen;
1786: int offset = 0;
1787:
1788: do {
1789: int nEnd = n[n.length - 1 - offset];
1790: int carry = mulAdd(n, mod, offset, mlen, inv * nEnd);
1791: c += addOne(n, offset, mlen, carry);
1792: offset++;
1793: } while (--len > 0);
1794:
1795: while (c > 0)
1796: c += subN(n, mod, mlen);
1797:
1798: while (intArrayCmpToLen(n, mod, mlen) >= 0)
1799: subN(n, mod, mlen);
1800:
1801: return n;
1802: }
1803:
1804: /*
1805: * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than,
1806: * equal to, or greater than arg2 up to length len.
1807: */
1808: private static int intArrayCmpToLen(int[] arg1, int[] arg2, int len) {
1809: for (int i = 0; i < len; i++) {
1810: long b1 = arg1[i] & LONG_MASK;
1811: long b2 = arg2[i] & LONG_MASK;
1812: if (b1 < b2)
1813: return -1;
1814: if (b1 > b2)
1815: return 1;
1816: }
1817: return 0;
1818: }
1819:
1820: /**
1821: * Subtracts two numbers of same length, returning borrow.
1822: */
1823: private static int subN(int[] a, int[] b, int len) {
1824: long sum = 0;
1825:
1826: while (--len >= 0) {
1827: sum = (a[len] & LONG_MASK) - (b[len] & LONG_MASK)
1828: + (sum >> 32);
1829: a[len] = (int) sum;
1830: }
1831:
1832: return (int) (sum >> 32);
1833: }
1834:
1835: /**
1836: * Multiply an array by one word k and add to result, return the carry
1837: */
1838: static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
1839: long kLong = k & LONG_MASK;
1840: long carry = 0;
1841:
1842: offset = out.length - offset - 1;
1843: for (int j = len - 1; j >= 0; j--) {
1844: long product = (in[j] & LONG_MASK) * kLong
1845: + (out[offset] & LONG_MASK) + carry;
1846: out[offset--] = (int) product;
1847: carry = product >>> 32;
1848: }
1849: return (int) carry;
1850: }
1851:
1852: /**
1853: * Add one word to the number a mlen words into a. Return the resulting
1854: * carry.
1855: */
1856: static int addOne(int[] a, int offset, int mlen, int carry) {
1857: offset = a.length - 1 - mlen - offset;
1858: long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
1859:
1860: a[offset] = (int) t;
1861: if ((t >>> 32) == 0)
1862: return 0;
1863: while (--mlen >= 0) {
1864: if (--offset < 0) { // Carry out of number
1865: return 1;
1866: } else {
1867: a[offset]++;
1868: if (a[offset] != 0)
1869: return 0;
1870: }
1871: }
1872: return 1;
1873: }
1874:
1875: /**
1876: * Returns a BigInteger whose value is (this ** exponent) mod (2**p)
1877: */
1878: private BigInteger modPow2(BigInteger exponent, int p) {
1879: /*
1880: * Perform exponentiation using repeated squaring method, chopping off
1881: * high order bits as indicated by modulus.
1882: */
1883: BigInteger result = valueOf(1);
1884: BigInteger baseToPow2 = this .mod2(p);
1885: int expOffset = 0;
1886:
1887: int limit = exponent.bitLength();
1888:
1889: if (this .testBit(0))
1890: limit = (p - 1) < limit ? (p - 1) : limit;
1891:
1892: while (expOffset < limit) {
1893: if (exponent.testBit(expOffset))
1894: result = result.multiply(baseToPow2).mod2(p);
1895: expOffset++;
1896: if (expOffset < limit)
1897: baseToPow2 = baseToPow2.square().mod2(p);
1898: }
1899:
1900: return result;
1901: }
1902:
1903: /**
1904: * Returns a BigInteger whose value is this mod(2**p).
1905: * Assumes that this BigInteger >= 0 and p > 0.
1906: */
1907: private BigInteger mod2(int p) {
1908: if (bitLength() <= p)
1909: return this ;
1910:
1911: // Copy remaining ints of mag
1912: int numInts = (p + 31) / 32;
1913: int[] mag = new int[numInts];
1914: for (int i = 0; i < numInts; i++)
1915: mag[i] = this .mag[i + (this .mag.length - numInts)];
1916:
1917: // Mask out any excess bits
1918: int excessBits = (numInts << 5) - p;
1919: mag[0] &= (1L << (32 - excessBits)) - 1;
1920:
1921: return (mag[0] == 0 ? new BigInteger(1, mag) : new BigInteger(
1922: mag, 1));
1923: }
1924:
1925: /**
1926: * Returns a BigInteger whose value is <tt>(this<sup>-1</sup> mod m)</tt>.
1927: *
1928: * @param m the modulus.
1929: * @return <tt>this<sup>-1</sup> mod m</tt>.
1930: * @throws ArithmeticException <tt> m <= 0</tt>, or this BigInteger
1931: * has no multiplicative inverse mod m (that is, this BigInteger
1932: * is not <i>relatively prime</i> to m).
1933: */
1934: public BigInteger modInverse(BigInteger m) {
1935: if (m.signum != 1)
1936: throw new ArithmeticException(
1937: "BigInteger: modulus not positive");
1938:
1939: if (m.equals(ONE))
1940: return ZERO;
1941:
1942: // Calculate (this mod m)
1943: BigInteger modVal = this ;
1944: if (signum < 0 || (intArrayCmp(mag, m.mag) >= 0))
1945: modVal = this .mod(m);
1946:
1947: if (modVal.equals(ONE))
1948: return ONE;
1949:
1950: MutableBigInteger a = new MutableBigInteger(modVal);
1951: MutableBigInteger b = new MutableBigInteger(m);
1952:
1953: MutableBigInteger result = a.mutableModInverse(b);
1954: return new BigInteger(result, 1);
1955: }
1956:
1957: // Shift Operations
1958:
1959: /**
1960: * Returns a BigInteger whose value is <tt>(this << n)</tt>.
1961: * The shift distance, <tt>n</tt>, may be negative, in which case
1962: * this method performs a right shift.
1963: * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
1964: *
1965: * @param n shift distance, in bits.
1966: * @return <tt>this << n</tt>
1967: * @see #shiftRight
1968: */
1969: public BigInteger shiftLeft(int n) {
1970: if (signum == 0)
1971: return ZERO;
1972: if (n == 0)
1973: return this ;
1974: if (n < 0)
1975: return shiftRight(-n);
1976:
1977: int nInts = n >>> 5;
1978: int nBits = n & 0x1f;
1979: int magLen = mag.length;
1980: int newMag[] = null;
1981:
1982: if (nBits == 0) {
1983: newMag = new int[magLen + nInts];
1984: for (int i = 0; i < magLen; i++)
1985: newMag[i] = mag[i];
1986: } else {
1987: int i = 0;
1988: int nBits2 = 32 - nBits;
1989: int highBits = mag[0] >>> nBits2;
1990: if (highBits != 0) {
1991: newMag = new int[magLen + nInts + 1];
1992: newMag[i++] = highBits;
1993: } else {
1994: newMag = new int[magLen + nInts];
1995: }
1996: int j = 0;
1997: while (j < magLen - 1)
1998: newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
1999: newMag[i] = mag[j] << nBits;
2000: }
2001:
2002: return new BigInteger(newMag, signum);
2003: }
2004:
2005: /**
2006: * Returns a BigInteger whose value is <tt>(this >> n)</tt>. Sign
2007: * extension is performed. The shift distance, <tt>n</tt>, may be
2008: * negative, in which case this method performs a left shift.
2009: * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.)
2010: *
2011: * @param n shift distance, in bits.
2012: * @return <tt>this >> n</tt>
2013: * @see #shiftLeft
2014: */
2015: public BigInteger shiftRight(int n) {
2016: if (n == 0)
2017: return this ;
2018: if (n < 0)
2019: return shiftLeft(-n);
2020:
2021: int nInts = n >>> 5;
2022: int nBits = n & 0x1f;
2023: int magLen = mag.length;
2024: int newMag[] = null;
2025:
2026: // Special case: entire contents shifted off the end
2027: if (nInts >= magLen)
2028: return (signum >= 0 ? ZERO : negConst[1]);
2029:
2030: if (nBits == 0) {
2031: int newMagLen = magLen - nInts;
2032: newMag = new int[newMagLen];
2033: for (int i = 0; i < newMagLen; i++)
2034: newMag[i] = mag[i];
2035: } else {
2036: int i = 0;
2037: int highBits = mag[0] >>> nBits;
2038: if (highBits != 0) {
2039: newMag = new int[magLen - nInts];
2040: newMag[i++] = highBits;
2041: } else {
2042: newMag = new int[magLen - nInts - 1];
2043: }
2044:
2045: int nBits2 = 32 - nBits;
2046: int j = 0;
2047: while (j < magLen - nInts - 1)
2048: newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
2049: }
2050:
2051: if (signum < 0) {
2052: // Find out whether any one-bits were shifted off the end.
2053: boolean onesLost = false;
2054: for (int i = magLen - 1, j = magLen - nInts; i >= j
2055: && !onesLost; i--)
2056: onesLost = (mag[i] != 0);
2057: if (!onesLost && nBits != 0)
2058: onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0);
2059:
2060: if (onesLost)
2061: newMag = javaIncrement(newMag);
2062: }
2063:
2064: return new BigInteger(newMag, signum);
2065: }
2066:
2067: int[] javaIncrement(int[] val) {
2068: boolean done = false;
2069: int lastSum = 0;
2070: for (int i = val.length - 1; i >= 0 && lastSum == 0; i--)
2071: lastSum = (val[i] += 1);
2072: if (lastSum == 0) {
2073: val = new int[val.length + 1];
2074: val[0] = 1;
2075: }
2076: return val;
2077: }
2078:
2079: // Bitwise Operations
2080:
2081: /**
2082: * Returns a BigInteger whose value is <tt>(this & val)</tt>. (This
2083: * method returns a negative BigInteger if and only if this and val are
2084: * both negative.)
2085: *
2086: * @param val value to be AND'ed with this BigInteger.
2087: * @return <tt>this & val</tt>
2088: */
2089: public BigInteger and(BigInteger val) {
2090: int[] result = new int[Math.max(intLength(), val.intLength())];
2091: for (int i = 0; i < result.length; i++)
2092: result[i] = (int) (getInt(result.length - i - 1) & val
2093: .getInt(result.length - i - 1));
2094:
2095: return valueOf(result);
2096: }
2097:
2098: /**
2099: * Returns a BigInteger whose value is <tt>(this | val)</tt>. (This method
2100: * returns a negative BigInteger if and only if either this or val is
2101: * negative.)
2102: *
2103: * @param val value to be OR'ed with this BigInteger.
2104: * @return <tt>this | val</tt>
2105: */
2106: public BigInteger or(BigInteger val) {
2107: int[] result = new int[Math.max(intLength(), val.intLength())];
2108: for (int i = 0; i < result.length; i++)
2109: result[i] = (int) (getInt(result.length - i - 1) | val
2110: .getInt(result.length - i - 1));
2111:
2112: return valueOf(result);
2113: }
2114:
2115: /**
2116: * Returns a BigInteger whose value is <tt>(this ^ val)</tt>. (This method
2117: * returns a negative BigInteger if and only if exactly one of this and
2118: * val are negative.)
2119: *
2120: * @param val value to be XOR'ed with this BigInteger.
2121: * @return <tt>this ^ val</tt>
2122: */
2123: public BigInteger xor(BigInteger val) {
2124: int[] result = new int[Math.max(intLength(), val.intLength())];
2125: for (int i = 0; i < result.length; i++)
2126: result[i] = (int) (getInt(result.length - i - 1) ^ val
2127: .getInt(result.length - i - 1));
2128:
2129: return valueOf(result);
2130: }
2131:
2132: /**
2133: * Returns a BigInteger whose value is <tt>(~this)</tt>. (This method
2134: * returns a negative value if and only if this BigInteger is
2135: * non-negative.)
2136: *
2137: * @return <tt>~this</tt>
2138: */
2139: public BigInteger not() {
2140: int[] result = new int[intLength()];
2141: for (int i = 0; i < result.length; i++)
2142: result[i] = (int) ~getInt(result.length - i - 1);
2143:
2144: return valueOf(result);
2145: }
2146:
2147: /**
2148: * Returns a BigInteger whose value is <tt>(this & ~val)</tt>. This
2149: * method, which is equivalent to <tt>and(val.not())</tt>, is provided as
2150: * a convenience for masking operations. (This method returns a negative
2151: * BigInteger if and only if <tt>this</tt> is negative and <tt>val</tt> is
2152: * positive.)
2153: *
2154: * @param val value to be complemented and AND'ed with this BigInteger.
2155: * @return <tt>this & ~val</tt>
2156: */
2157: public BigInteger andNot(BigInteger val) {
2158: int[] result = new int[Math.max(intLength(), val.intLength())];
2159: for (int i = 0; i < result.length; i++)
2160: result[i] = (int) (getInt(result.length - i - 1) & ~val
2161: .getInt(result.length - i - 1));
2162:
2163: return valueOf(result);
2164: }
2165:
2166: // Single Bit Operations
2167:
2168: /**
2169: * Returns <tt>true</tt> if and only if the designated bit is set.
2170: * (Computes <tt>((this & (1<<n)) != 0)</tt>.)
2171: *
2172: * @param n index of bit to test.
2173: * @return <tt>true</tt> if and only if the designated bit is set.
2174: * @throws ArithmeticException <tt>n</tt> is negative.
2175: */
2176: public boolean testBit(int n) {
2177: if (n < 0)
2178: throw new ArithmeticException("Negative bit address");
2179:
2180: return (getInt(n / 32) & (1 << (n % 32))) != 0;
2181: }
2182:
2183: /**
2184: * Returns a BigInteger whose value is equivalent to this BigInteger
2185: * with the designated bit set. (Computes <tt>(this | (1<<n))</tt>.)
2186: *
2187: * @param n index of bit to set.
2188: * @return <tt>this | (1<<n)</tt>
2189: * @throws ArithmeticException <tt>n</tt> is negative.
2190: */
2191: public BigInteger setBit(int n) {
2192: if (n < 0)
2193: throw new ArithmeticException("Negative bit address");
2194:
2195: int intNum = n / 32;
2196: int[] result = new int[Math.max(intLength(), intNum + 2)];
2197:
2198: for (int i = 0; i < result.length; i++)
2199: result[result.length - i - 1] = getInt(i);
2200:
2201: result[result.length - intNum - 1] |= (1 << (n % 32));
2202:
2203: return valueOf(result);
2204: }
2205:
2206: /**
2207: * Returns a BigInteger whose value is equivalent to this BigInteger
2208: * with the designated bit cleared.
2209: * (Computes <tt>(this & ~(1<<n))</tt>.)
2210: *
2211: * @param n index of bit to clear.
2212: * @return <tt>this & ~(1<<n)</tt>
2213: * @throws ArithmeticException <tt>n</tt> is negative.
2214: */
2215: public BigInteger clearBit(int n) {
2216: if (n < 0)
2217: throw new ArithmeticException("Negative bit address");
2218:
2219: int intNum = n / 32;
2220: int[] result = new int[Math.max(intLength(), (n + 1) / 32 + 1)];
2221:
2222: for (int i = 0; i < result.length; i++)
2223: result[result.length - i - 1] = getInt(i);
2224:
2225: result[result.length - intNum - 1] &= ~(1 << (n % 32));
2226:
2227: return valueOf(result);
2228: }
2229:
2230: /**
2231: * Returns a BigInteger whose value is equivalent to this BigInteger
2232: * with the designated bit flipped.
2233: * (Computes <tt>(this ^ (1<<n))</tt>.)
2234: *
2235: * @param n index of bit to flip.
2236: * @return <tt>this ^ (1<<n)</tt>
2237: * @throws ArithmeticException <tt>n</tt> is negative.
2238: */
2239: public BigInteger flipBit(int n) {
2240: if (n < 0)
2241: throw new ArithmeticException("Negative bit address");
2242:
2243: int intNum = n / 32;
2244: int[] result = new int[Math.max(intLength(), intNum + 2)];
2245:
2246: for (int i = 0; i < result.length; i++)
2247: result[result.length - i - 1] = getInt(i);
2248:
2249: result[result.length - intNum - 1] ^= (1 << (n % 32));
2250:
2251: return valueOf(result);
2252: }
2253:
2254: /**
2255: * Returns the index of the rightmost (lowest-order) one bit in this
2256: * BigInteger (the number of zero bits to the right of the rightmost
2257: * one bit). Returns -1 if this BigInteger contains no one bits.
2258: * (Computes <tt>(this==0? -1 : log<sub>2</sub>(this & -this))</tt>.)
2259: *
2260: * @return index of the rightmost one bit in this BigInteger.
2261: */
2262: public int getLowestSetBit() {
2263: /*
2264: * Initialize lowestSetBit field the first time this method is
2265: * executed. This method depends on the atomicity of int modifies;
2266: * without this guarantee, it would have to be synchronized.
2267: */
2268: if (lowestSetBit == -2) {
2269: if (signum == 0) {
2270: lowestSetBit = -1;
2271: } else {
2272: // Search for lowest order nonzero int
2273: int i, b;
2274: for (i = 0; (b = getInt(i)) == 0; i++)
2275: ;
2276: lowestSetBit = (i << 5) + trailingZeroCnt(b);
2277: }
2278: }
2279: return lowestSetBit;
2280: }
2281:
2282: // Miscellaneous Bit Operations
2283:
2284: /**
2285: * Returns the number of bits in the minimal two's-complement
2286: * representation of this BigInteger, <i>excluding</i> a sign bit.
2287: * For positive BigIntegers, this is equivalent to the number of bits in
2288: * the ordinary binary representation. (Computes
2289: * <tt>(ceil(log<sub>2</sub>(this < 0 ? -this : this+1)))</tt>.)
2290: *
2291: * @return number of bits in the minimal two's-complement
2292: * representation of this BigInteger, <i>excluding</i> a sign bit.
2293: */
2294: public int bitLength() {
2295: /*
2296: * Initialize bitLength field the first time this method is executed.
2297: * This method depends on the atomicity of int modifies; without
2298: * this guarantee, it would have to be synchronized.
2299: */
2300: if (bitLength == -1) {
2301: if (signum == 0) {
2302: bitLength = 0;
2303: } else {
2304: // Calculate the bit length of the magnitude
2305: int magBitLength = ((mag.length - 1) << 5)
2306: + bitLen(mag[0]);
2307:
2308: if (signum < 0) {
2309: // Check if magnitude is a power of two
2310: boolean pow2 = (bitCnt(mag[0]) == 1);
2311: for (int i = 1; i < mag.length && pow2; i++)
2312: pow2 = (mag[i] == 0);
2313:
2314: bitLength = (pow2 ? magBitLength - 1 : magBitLength);
2315: } else {
2316: bitLength = magBitLength;
2317: }
2318: }
2319: }
2320: return bitLength;
2321: }
2322:
2323: /**
2324: * bitLen(val) is the number of bits in val.
2325: */
2326: static int bitLen(int w) {
2327: // Binary search - decision tree (5 tests, rarely 6)
2328: return (w < 1 << 15 ? (w < 1 << 7 ? (w < 1 << 3 ? (w < 1 << 1 ? (w < 1 << 0 ? (w < 0 ? 32
2329: : 0)
2330: : 1)
2331: : (w < 1 << 2 ? 2 : 3))
2332: : (w < 1 << 5 ? (w < 1 << 4 ? 4 : 5) : (w < 1 << 6 ? 6
2333: : 7)))
2334: : (w < 1 << 11 ? (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9)
2335: : (w < 1 << 10 ? 10 : 11))
2336: : (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13)
2337: : (w < 1 << 14 ? 14 : 15))))
2338: : (w < 1 << 23 ? (w < 1 << 19 ? (w < 1 << 17 ? (w < 1 << 16 ? 16
2339: : 17)
2340: : (w < 1 << 18 ? 18 : 19))
2341: : (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21)
2342: : (w < 1 << 22 ? 22 : 23)))
2343: : (w < 1 << 27 ? (w < 1 << 25 ? (w < 1 << 24 ? 24
2344: : 25)
2345: : (w < 1 << 26 ? 26 : 27))
2346: : (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29)
2347: : (w < 1 << 30 ? 30 : 31)))));
2348: }
2349:
2350: /*
2351: * trailingZeroTable[i] is the number of trailing zero bits in the binary
2352: * representaion of i.
2353: */
2354: final static byte trailingZeroTable[] = { -25, 0, 1, 0, 2, 0, 1, 0,
2355: 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
2356: 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
2357: 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0,
2358: 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
2359: 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
2360: 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
2361: 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
2362: 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0,
2363: 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
2364: 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
2365: 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0,
2366: 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
2367: 3, 0, 1, 0, 2, 0, 1, 0 };
2368:
2369: /**
2370: * Returns the number of bits in the two's complement representation
2371: * of this BigInteger that differ from its sign bit. This method is
2372: * useful when implementing bit-vector style sets atop BigIntegers.
2373: *
2374: * @return number of bits in the two's complement representation
2375: * of this BigInteger that differ from its sign bit.
2376: */
2377: public int bitCount() {
2378: /*
2379: * Initialize bitCount field the first time this method is executed.
2380: * This method depends on the atomicity of int modifies; without
2381: * this guarantee, it would have to be synchronized.
2382: */
2383: if (bitCount == -1) {
2384: // Count the bits in the magnitude
2385: int magBitCount = 0;
2386: for (int i = 0; i < mag.length; i++)
2387: magBitCount += bitCnt(mag[i]);
2388:
2389: if (signum < 0) {
2390: // Count the trailing zeros in the magnitude
2391: int magTrailingZeroCount = 0, j;
2392: for (j = mag.length - 1; mag[j] == 0; j--)
2393: magTrailingZeroCount += 32;
2394: magTrailingZeroCount += trailingZeroCnt(mag[j]);
2395:
2396: bitCount = magBitCount + magTrailingZeroCount - 1;
2397: } else {
2398: bitCount = magBitCount;
2399: }
2400: }
2401: return bitCount;
2402: }
2403:
2404: static int bitCnt(int val) {
2405: val -= (0xaaaaaaaa & val) >>> 1;
2406: val = (val & 0x33333333) + ((val >>> 2) & 0x33333333);
2407: val = val + (val >>> 4) & 0x0f0f0f0f;
2408: val += val >>> 8;
2409: val += val >>> 16;
2410: return val & 0xff;
2411: }
2412:
2413: static int trailingZeroCnt(int val) {
2414: // Loop unrolled for performance
2415: int byteVal = val & 0xff;
2416: if (byteVal != 0)
2417: return trailingZeroTable[byteVal];
2418:
2419: byteVal = (val >>> 8) & 0xff;
2420: if (byteVal != 0)
2421: return trailingZeroTable[byteVal] + 8;
2422:
2423: byteVal = (val >>> 16) & 0xff;
2424: if (byteVal != 0)
2425: return trailingZeroTable[byteVal] + 16;
2426:
2427: byteVal = (val >>> 24) & 0xff;
2428: return trailingZeroTable[byteVal] + 24;
2429: }
2430:
2431: // Primality Testing
2432:
2433: /**
2434: * Returns <tt>true</tt> if this BigInteger is probably prime,
2435: * <tt>false</tt> if it's definitely composite. If
2436: * <tt>certainty</tt> is <tt> <= 0</tt>, <tt>true</tt> is
2437: * returned.
2438: *
2439: * @param certainty a measure of the uncertainty that the caller is
2440: * willing to tolerate: if the call returns <tt>true</tt>
2441: * the probability that this BigInteger is prime exceeds
2442: * <tt>(1 - 1/2<sup>certainty</sup>)</tt>. The execution time of
2443: * this method is proportional to the value of this parameter.
2444: * @return <tt>true</tt> if this BigInteger is probably prime,
2445: * <tt>false</tt> if it's definitely composite.
2446: */
2447: public boolean isProbablePrime(int certainty) {
2448: if (certainty <= 0)
2449: return true;
2450: BigInteger w = this .abs();
2451: if (w.equals(TWO))
2452: return true;
2453: if (!w.testBit(0) || w.equals(ONE))
2454: return false;
2455:
2456: return w.primeToCertainty(certainty);
2457: }
2458:
2459: // Comparison Operations
2460:
2461: /**
2462: * Compares this BigInteger with the specified BigInteger. This method is
2463: * provided in preference to individual methods for each of the six
2464: * boolean comparison operators (<, ==, >, >=, !=, <=). The
2465: * suggested idiom for performing these comparisons is:
2466: * <tt>(x.compareTo(y)</tt> <<i>op</i>> <tt>0)</tt>,
2467: * where <<i>op</i>> is one of the six comparison operators.
2468: *
2469: * @param val BigInteger to which this BigInteger is to be compared.
2470: * @return -1, 0 or 1 as this BigInteger is numerically less than, equal
2471: * to, or greater than <tt>val</tt>.
2472: */
2473: public int compareTo(BigInteger val) {
2474: return (signum == val.signum ? signum
2475: * intArrayCmp(mag, val.mag) : (signum > val.signum ? 1
2476: : -1));
2477: }
2478:
2479: /**
2480: * Compares this BigInteger with the specified Object. If the Object is a
2481: * BigInteger, this method behaves like <tt>compareTo(BigInteger)</tt>.
2482: * Otherwise, it throws a <tt>ClassCastException</tt> (as BigIntegers are
2483: * comparable only to other BigIntegers).
2484: *
2485: * @param o Object to which this BigInteger is to be compared.
2486: * @return a negative number, zero, or a positive number as this
2487: * BigInteger is numerically less than, equal to, or greater
2488: * than <tt>o</tt>, which must be a BigInteger.
2489: * @throws ClassCastException <tt>o</tt> is not a BigInteger.
2490: * @see #compareTo(java.math.BigInteger)
2491: * @see Comparable
2492: * @since 1.2
2493: */
2494: public int compareTo(Object o) {
2495: return compareTo((BigInteger) o);
2496: }
2497:
2498: /*
2499: * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is
2500: * less than, equal to, or greater than arg2.
2501: */
2502: private static int intArrayCmp(int[] arg1, int[] arg2) {
2503: if (arg1.length < arg2.length)
2504: return -1;
2505: if (arg1.length > arg2.length)
2506: return 1;
2507:
2508: // Argument lengths are equal; compare the values
2509: for (int i = 0; i < arg1.length; i++) {
2510: long b1 = arg1[i] & LONG_MASK;
2511: long b2 = arg2[i] & LONG_MASK;
2512: if (b1 < b2)
2513: return -1;
2514: if (b1 > b2)
2515: return 1;
2516: }
2517: return 0;
2518: }
2519:
2520: /**
2521: * Compares this BigInteger with the specified Object for equality.
2522: *
2523: * @param x Object to which this BigInteger is to be compared.
2524: * @return <tt>true</tt> if and only if the specified Object is a
2525: * BigInteger whose value is numerically equal to this BigInteger.
2526: */
2527: public boolean equals(Object x) {
2528: // This test is just an optimization, which may or may not help
2529: if (x == this )
2530: return true;
2531:
2532: if (!(x instanceof BigInteger))
2533: return false;
2534: BigInteger xInt = (BigInteger) x;
2535:
2536: if (xInt.signum != signum || xInt.mag.length != mag.length)
2537: return false;
2538:
2539: for (int i = 0; i < mag.length; i++)
2540: if (xInt.mag[i] != mag[i])
2541: return false;
2542:
2543: return true;
2544: }
2545:
2546: /**
2547: * Returns the minimum of this BigInteger and <tt>val</tt>.
2548: *
2549: * @param val value with with the minimum is to be computed.
2550: * @return the BigInteger whose value is the lesser of this BigInteger and
2551: * <tt>val</tt>. If they are equal, either may be returned.
2552: */
2553: public BigInteger min(BigInteger val) {
2554: return (compareTo(val) < 0 ? this : val);
2555: }
2556:
2557: /**
2558: * Returns the maximum of this BigInteger and <tt>val</tt>.
2559: *
2560: * @param val value with with the maximum is to be computed.
2561: * @return the BigInteger whose value is the greater of this and
2562: * <tt>val</tt>. If they are equal, either may be returned.
2563: */
2564: public BigInteger max(BigInteger val) {
2565: return (compareTo(val) > 0 ? this : val);
2566: }
2567:
2568: // Hash Function
2569:
2570: /**
2571: * Returns the hash code for this BigInteger.
2572: *
2573: * @return hash code for this BigInteger.
2574: */
2575: public int hashCode() {
2576: int hashCode = 0;
2577:
2578: for (int i = 0; i < mag.length; i++)
2579: hashCode = (int) (31 * hashCode + (mag[i] & LONG_MASK));
2580:
2581: return hashCode * signum;
2582: }
2583:
2584: /**
2585: * Returns the String representation of this BigInteger in the
2586: * given radix. If the radix is outside the range from {@link
2587: * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
2588: * it will default to 10 (as is the case for
2589: * <tt>Integer.toString</tt>). The digit-to-character mapping
2590: * provided by <tt>Character.forDigit</tt> is used, and a minus
2591: * sign is prepended if appropriate. (This representation is
2592: * compatible with the {@link #BigInteger(String, int) (String,
2593: * <code>int</code>)} constructor.)
2594: *
2595: * @param radix radix of the String representation.
2596: * @return String representation of this BigInteger in the given radix.
2597: * @see Integer#toString
2598: * @see Character#forDigit
2599: * @see #BigInteger(java.lang.String, int)
2600: */
2601: public String toString(int radix) {
2602: if (signum == 0)
2603: return "0";
2604: if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
2605: radix = 10;
2606:
2607: // Compute upper bound on number of digit groups and allocate space
2608: int maxNumDigitGroups = (4 * mag.length + 6) / 7;
2609: String digitGroup[] = new String[maxNumDigitGroups];
2610:
2611: // Translate number to string, a digit group at a time
2612: BigInteger tmp = this .abs();
2613: int numGroups = 0;
2614: while (tmp.signum != 0) {
2615: BigInteger d = longRadix[radix];
2616:
2617: MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
2618: tmp.mag), b = new MutableBigInteger(d.mag);
2619: a.divide(b, q, r);
2620: BigInteger q2 = new BigInteger(q, tmp.signum * d.signum);
2621: BigInteger r2 = new BigInteger(r, tmp.signum * d.signum);
2622:
2623: digitGroup[numGroups++] = Long.toString(r2.longValue(),
2624: radix);
2625: tmp = q2;
2626: }
2627:
2628: // Put sign (if any) and first digit group into result buffer
2629: StringBuffer buf = new StringBuffer(numGroups
2630: * digitsPerLong[radix] + 1);
2631: if (signum < 0)
2632: buf.append('-');
2633: buf.append(digitGroup[numGroups - 1]);
2634:
2635: // Append remaining digit groups padded with leading zeros
2636: for (int i = numGroups - 2; i >= 0; i--) {
2637: // Prepend (any) leading zeros for this digit group
2638: int numLeadingZeros = digitsPerLong[radix]
2639: - digitGroup[i].length();
2640: if (numLeadingZeros != 0)
2641: buf.append(zeros[numLeadingZeros]);
2642: buf.append(digitGroup[i]);
2643: }
2644: return buf.toString();
2645: }
2646:
2647: /* zero[i] is a string of i consecutive zeros. */
2648: private static String zeros[] = new String[64];
2649: static {
2650: zeros[63] = "000000000000000000000000000000000000000000000000000000000000000";
2651: for (int i = 0; i < 63; i++)
2652: zeros[i] = zeros[63].substring(0, i);
2653: }
2654:
2655: /**
2656: * Returns the decimal String representation of this BigInteger.
2657: * The digit-to-character mapping provided by
2658: * <tt>Character.forDigit</tt> is used, and a minus sign is
2659: * prepended if appropriate. (This representation is compatible
2660: * with the {@link #BigInteger(String) (String)} constructor, and
2661: * allows for String concatenation with Java's + operator.)
2662: *
2663: * @return decimal String representation of this BigInteger.
2664: * @see Character#forDigit
2665: * @see #BigInteger(java.lang.String)
2666: */
2667: public String toString() {
2668: return toString(10);
2669: }
2670:
2671: /**
2672: * Returns a byte array containing the two's-complement
2673: * representation of this BigInteger. The byte array will be in
2674: * <i>big-endian</i> byte-order: the most significant byte is in
2675: * the zeroth element. The array will contain the minimum number
2676: * of bytes required to represent this BigInteger, including at
2677: * least one sign bit, which is <tt>(ceil((this.bitLength() +
2678: * 1)/8))</tt>. (This representation is compatible with the
2679: * {@link #BigInteger(byte[]) (byte[])} constructor.)
2680: *
2681: * @return a byte array containing the two's-complement representation of
2682: * this BigInteger.
2683: * @see #BigInteger(byte[])
2684: */
2685: public byte[] toByteArray() {
2686: int byteLen = bitLength() / 8 + 1;
2687: byte[] byteArray = new byte[byteLen];
2688:
2689: for (int i = byteLen - 1, bytesCopied = 4, nextInt = 0, intIndex = 0; i >= 0; i--) {
2690: if (bytesCopied == 4) {
2691: nextInt = getInt(intIndex++);
2692: bytesCopied = 1;
2693: } else {
2694: nextInt >>>= 8;
2695: bytesCopied++;
2696: }
2697: byteArray[i] = (byte) nextInt;
2698: }
2699: return byteArray;
2700: }
2701:
2702: /**
2703: * Converts this BigInteger to an <code>int</code>. This
2704: * conversion is analogous to a <a
2705: * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2706: * primitive conversion</i></a> from <code>long</code> to
2707: * <code>int</code> as defined in the <a
2708: * href="http://java.sun.com/docs/books/jls/html/">Java Language
2709: * Specification</a>: if this BigInteger is too big to fit in an
2710: * <code>int</code>, only the low-order 32 bits are returned.
2711: * Note that this conversion can lose information about the
2712: * overall magnitude of the BigInteger value as well as return a
2713: * result with the opposite sign.
2714: *
2715: * @return this BigInteger converted to an <code>int</code>.
2716: */
2717: public int intValue() {
2718: int result = 0;
2719: result = getInt(0);
2720: return result;
2721: }
2722:
2723: /**
2724: * Converts this BigInteger to a <code>long</code>. This
2725: * conversion is analogous to a <a
2726: * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2727: * primitive conversion</i></a> from <code>long</code> to
2728: * <code>int</code> as defined in the <a
2729: * href="http://java.sun.com/docs/books/jls/html/">Java Language
2730: * Specification</a>: if this BigInteger is too big to fit in a
2731: * <code>long</code>, only the low-order 64 bits are returned.
2732: * Note that this conversion can lose information about the
2733: * overall magnitude of the BigInteger value as well as return a
2734: * result with the opposite sign.
2735: *
2736: * @return this BigInteger converted to a <code>long</code>.
2737: */
2738: public long longValue() {
2739: long result = 0;
2740:
2741: for (int i = 1; i >= 0; i--)
2742: result = (result << 32) + (getInt(i) & LONG_MASK);
2743: return result;
2744: }
2745:
2746: /**
2747: * Converts this BigInteger to a <code>float</code>. This
2748: * conversion is similar to the <a
2749: * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2750: * primitive conversion</i></a> from <code>double</code> to
2751: * <code>float</code> defined in the <a
2752: * href="http://java.sun.com/docs/books/jls/html/">Java Language
2753: * Specification</a>: if this BigInteger has too great a magnitude
2754: * to represent as a <code>float</code>, it will be converted to
2755: * {@link Float#NEGATIVE_INFINITY} or {@link
2756: * Float#POSITIVE_INFINITY} as appropriate. Note that even when
2757: * the return value is finite, this conversion can lose
2758: * information about the precision of the BigInteger value.
2759: *
2760: * @return this BigInteger converted to a <code>float</code>.
2761: */
2762: public float floatValue() {
2763: // Somewhat inefficient, but guaranteed to work.
2764: return Float.valueOf(this .toString()).floatValue();
2765: }
2766:
2767: /**
2768: * Converts this BigInteger to a <code>double</code>. This
2769: * conversion is similar to the <a
2770: * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
2771: * primitive conversion</i></a> from <code>double</code> to
2772: * <code>float</code> defined in the <a
2773: * href="http://java.sun.com/docs/books/jls/html/">Java Language
2774: * Specification</a>: if this BigInteger has too great a magnitude
2775: * to represent as a <code>double</code>, it will be converted to
2776: * {@link Double#NEGATIVE_INFINITY} or {@link
2777: * Double#POSITIVE_INFINITY} as appropriate. Note that even when
2778: * the return value is finite, this conversion can lose
2779: * information about the precision of the BigInteger value.
2780: *
2781: * @return this BigInteger converted to a <code>double</code>.
2782: */
2783: public double doubleValue() {
2784: // Somewhat inefficient, but guaranteed to work.
2785: return Double.valueOf(this .toString()).doubleValue();
2786: }
2787:
2788: /**
2789: * Returns a copy of the input array stripped of any leading zero bytes.
2790: */
2791: private static int[] stripLeadingZeroInts(int val[]) {
2792: int byteLength = val.length;
2793: int keep;
2794:
2795: // Find first nonzero byte
2796: for (keep = 0; keep < val.length && val[keep] == 0; keep++)
2797: ;
2798:
2799: int result[] = new int[val.length - keep];
2800: for (int i = 0; i < val.length - keep; i++)
2801: result[i] = val[keep + i];
2802:
2803: return result;
2804: }
2805:
2806: /**
2807: * Returns the input array stripped of any leading zero bytes.
2808: * Since the source is trusted the copying may be skipped.
2809: */
2810: private static int[] trustedStripLeadingZeroInts(int val[]) {
2811: int byteLength = val.length;
2812: int keep;
2813:
2814: // Find first nonzero byte
2815: for (keep = 0; keep < val.length && val[keep] == 0; keep++)
2816: ;
2817:
2818: // Only perform copy if necessary
2819: if (keep > 0) {
2820: int result[] = new int[val.length - keep];
2821: for (int i = 0; i < val.length - keep; i++)
2822: result[i] = val[keep + i];
2823: return result;
2824: }
2825: return val;
2826: }
2827:
2828: /**
2829: * Returns a copy of the input array stripped of any leading zero bytes.
2830: */
2831: private static int[] stripLeadingZeroBytes(byte a[]) {
2832: int byteLength = a.length;
2833: int keep;
2834:
2835: // Find first nonzero byte
2836: for (keep = 0; keep < a.length && a[keep] == 0; keep++)
2837: ;
2838:
2839: // Allocate new array and copy relevant part of input array
2840: int intLength = ((byteLength - keep) + 3) / 4;
2841: int[] result = new int[intLength];
2842: int b = byteLength - 1;
2843: for (int i = intLength - 1; i >= 0; i--) {
2844: result[i] = a[b--] & 0xff;
2845: int bytesRemaining = b - keep + 1;
2846: int bytesToTransfer = Math.min(3, bytesRemaining);
2847: for (int j = 8; j <= 8 * bytesToTransfer; j += 8)
2848: result[i] |= ((a[b--] & 0xff) << j);
2849: }
2850: return result;
2851: }
2852:
2853: /**
2854: * Takes an array a representing a negative 2's-complement number and
2855: * returns the minimal (no leading zero bytes) unsigned whose value is -a.
2856: */
2857: private static int[] makePositive(byte a[]) {
2858: int keep, k;
2859: int byteLength = a.length;
2860:
2861: // Find first non-sign (0xff) byte of input
2862: for (keep = 0; keep < byteLength && a[keep] == -1; keep++)
2863: ;
2864:
2865: /* Allocate output array. If all non-sign bytes are 0x00, we must
2866: * allocate space for one extra output byte. */
2867: for (k = keep; k < byteLength && a[k] == 0; k++)
2868: ;
2869:
2870: int extraByte = (k == byteLength) ? 1 : 0;
2871: int intLength = ((byteLength - keep + extraByte) + 3) / 4;
2872: int result[] = new int[intLength];
2873:
2874: /* Copy one's complement of input into into output, leaving extra
2875: * byte (if it exists) == 0x00 */
2876: int b = byteLength - 1;
2877: for (int i = intLength - 1; i >= 0; i--) {
2878: result[i] = a[b--] & 0xff;
2879: int numBytesToTransfer = Math.min(3, b - keep + 1);
2880: if (numBytesToTransfer < 0)
2881: numBytesToTransfer = 0;
2882: for (int j = 8; j <= 8 * numBytesToTransfer; j += 8)
2883: result[i] |= ((a[b--] & 0xff) << j);
2884:
2885: // Mask indicates which bits must be complemented
2886: int mask = -1 >>> (8 * (3 - numBytesToTransfer));
2887: result[i] = ~result[i] & mask;
2888: }
2889:
2890: // Add one to one's complement to generate two's complement
2891: for (int i = result.length - 1; i >= 0; i--) {
2892: result[i] = (int) ((result[i] & LONG_MASK) + 1);
2893: if (result[i] != 0)
2894: break;
2895: }
2896:
2897: return result;
2898: }
2899:
2900: /**
2901: * Takes an array a representing a negative 2's-complement number and
2902: * returns the minimal (no leading zero ints) unsigned whose value is -a.
2903: */
2904: private static int[] makePositive(int a[]) {
2905: int keep, j;
2906:
2907: // Find first non-sign (0xffffffff) int of input
2908: for (keep = 0; keep < a.length && a[keep] == -1; keep++)
2909: ;
2910:
2911: /* Allocate output array. If all non-sign ints are 0x00, we must
2912: * allocate space for one extra output int. */
2913: for (j = keep; j < a.length && a[j] == 0; j++)
2914: ;
2915: int extraInt = (j == a.length ? 1 : 0);
2916: int result[] = new int[a.length - keep + extraInt];
2917:
2918: /* Copy one's complement of input into into output, leaving extra
2919: * int (if it exists) == 0x00 */
2920: for (int i = keep; i < a.length; i++)
2921: result[i - keep + extraInt] = ~a[i];
2922:
2923: // Add one to one's complement to generate two's complement
2924: for (int i = result.length - 1; ++result[i] == 0; i--)
2925: ;
2926:
2927: return result;
2928: }
2929:
2930: /*
2931: * The following two arrays are used for fast String conversions. Both
2932: * are indexed by radix. The first is the number of digits of the given
2933: * radix that can fit in a Java long without "going negative", i.e., the
2934: * highest integer n such that radix**n < 2**63. The second is the
2935: * "long radix" that tears each number into "long digits", each of which
2936: * consists of the number of digits in the corresponding element in
2937: * digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
2938: * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
2939: * used.
2940: */
2941: private static int digitsPerLong[] = { 0, 0, 62, 39, 31, 27, 24,
2942: 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14, 14, 14,
2943: 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12 };
2944:
2945: private static BigInteger longRadix[] = { null, null,
2946: valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
2947: valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
2948: valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
2949: valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
2950: valueOf(0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
2951: valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
2952: valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
2953: valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
2954: valueOf(0x5da0e1e53c5c8000L), valueOf(0xb16a458ef403f19L),
2955: valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
2956: valueOf(0x5658597bcaa24000L), valueOf(0x6feb266931a75b7L),
2957: valueOf(0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
2958: valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
2959: valueOf(0x5a3c23e39c000000L), valueOf(0x4e900abb53e6b71L),
2960: valueOf(0x7600ec618141000L), valueOf(0xaee5720ee830681L),
2961: valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
2962: valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
2963: valueOf(0x41c21cb8e1000000L) };
2964:
2965: /*
2966: * These two arrays are the integer analogue of above.
2967: */
2968: private static int digitsPerInt[] = { 0, 0, 30, 19, 15, 13, 11, 11,
2969: 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6,
2970: 6, 6, 6, 6, 6, 6, 6, 6, 6, 5 };
2971:
2972: private static int intRadix[] = { 0, 0, 0x40000000, 0x4546b3db,
2973: 0x40000000, 0x48c27395, 0x159fd800, 0x75db9c97, 0x40000000,
2974: 0x17179149, 0x3b9aca00, 0xcc6db61, 0x19a10000, 0x309f1021,
2975: 0x57f6c100, 0xa2f1b6f, 0x10000000, 0x18754571, 0x247dbc80,
2976: 0x3547667b, 0x4c4b4000, 0x6b5a6e1d, 0x6c20a40, 0x8d2d931,
2977: 0xb640000, 0xe8d4a51, 0x1269ae40, 0x17179149, 0x1cb91000,
2978: 0x23744899, 0x2b73a840, 0x34e63b41, 0x40000000, 0x4cfa3cc1,
2979: 0x5c13d840, 0x6d91b519, 0x39aa400 };
2980:
2981: /**
2982: * These routines provide access to the two's complement representation
2983: * of BigIntegers.
2984: */
2985:
2986: /**
2987: * Returns the length of the two's complement representation in ints,
2988: * including space for at least one sign bit.
2989: */
2990: private int intLength() {
2991: return bitLength() / 32 + 1;
2992: }
2993:
2994: /* Returns sign bit */
2995: private int signBit() {
2996: return (signum < 0 ? 1 : 0);
2997: }
2998:
2999: /* Returns an int of sign bits */
3000: private int signInt() {
3001: return (int) (signum < 0 ? -1 : 0);
3002: }
3003:
3004: /**
3005: * Returns the specified int of the little-endian two's complement
3006: * representation (int 0 is the least significant). The int number can
3007: * be arbitrarily high (values are logically preceded by infinitely many
3008: * sign ints).
3009: */
3010: private int getInt(int n) {
3011: if (n < 0)
3012: return 0;
3013: if (n >= mag.length)
3014: return signInt();
3015:
3016: int magInt = mag[mag.length - n - 1];
3017:
3018: return (int) (signum >= 0 ? magInt
3019: : (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
3020: }
3021:
3022: /**
3023: * Returns the index of the int that contains the first nonzero int in the
3024: * little-endian binary representation of the magnitude (int 0 is the
3025: * least significant). If the magnitude is zero, return value is undefined.
3026: */
3027: private int firstNonzeroIntNum() {
3028: /*
3029: * Initialize firstNonzeroIntNum field the first time this method is
3030: * executed. This method depends on the atomicity of int modifies;
3031: * without this guarantee, it would have to be synchronized.
3032: */
3033: if (firstNonzeroIntNum == -2) {
3034: // Search for the first nonzero int
3035: int i;
3036: for (i = mag.length - 1; i >= 0 && mag[i] == 0; i--)
3037: ;
3038: firstNonzeroIntNum = mag.length - i - 1;
3039: }
3040: return firstNonzeroIntNum;
3041: }
3042:
3043: /** use serialVersionUID from JDK 1.1. for interoperability */
3044: private static final long serialVersionUID = -8287574255936472291L;
3045:
3046: /**
3047: * Reconstitute the <tt>BigInteger</tt> instance from a stream (that is,
3048: * deserialize it). The magnitude is read in as an array of bytes
3049: * for historical reasons, but it is converted to an array of ints
3050: * and the byte array is discarded.
3051: */
3052: private void readObject(java.io.ObjectInputStream s)
3053: throws java.io.IOException, ClassNotFoundException {
3054: /*
3055: * In order to maintain compatibility with previous serialized forms,
3056: * the magnitude of a BigInteger is serialized as an array of bytes.
3057: * The magnitude field is used as a temporary store for the byte array
3058: * that is deserialized. The cached computation fields should be
3059: * transient but are serialized for compatibility reasons.
3060: */
3061:
3062: // Read in all fields
3063: s.defaultReadObject();
3064:
3065: // Validate signum
3066: if (signum < -1 || signum > 1)
3067: throw new java.io.StreamCorruptedException(
3068: "BigInteger: Invalid signum value");
3069: if ((magnitude.length == 0) != (signum == 0))
3070: throw new java.io.StreamCorruptedException(
3071: "BigInteger: signum-magnitude mismatch");
3072:
3073: // Set "cached computation" fields to their initial values
3074: bitCount = bitLength = -1;
3075: lowestSetBit = firstNonzeroByteNum = firstNonzeroIntNum = -2;
3076:
3077: // Calculate mag field from magnitude and discard magnitude
3078: mag = stripLeadingZeroBytes(magnitude);
3079: magnitude = null;
3080: }
3081:
3082: /**
3083: * Ensure that magnitude (the obsolete byte array representation)
3084: * is set prior to serializaing this BigInteger. This provides a
3085: * serialized form that is compatible with older (pre-1.3) versions.
3086: */
3087: private synchronized Object writeReplace() {
3088: if (magnitude == null)
3089: magnitude = magSerializedForm();
3090:
3091: return this ;
3092: }
3093:
3094: /**
3095: * Returns the mag array as an array of bytes.
3096: */
3097: private byte[] magSerializedForm() {
3098: int bitLen = (mag.length == 0 ? 0 : ((mag.length - 1) << 5)
3099: + bitLen(mag[0]));
3100: int byteLen = (bitLen + 7) / 8;
3101: byte[] result = new byte[byteLen];
3102:
3103: for (int i = byteLen - 1, bytesCopied = 4, intIndex = mag.length - 1, nextInt = 0; i >= 0; i--) {
3104: if (bytesCopied == 4) {
3105: nextInt = mag[intIndex--];
3106: bytesCopied = 1;
3107: } else {
3108: nextInt >>>= 8;
3109: bytesCopied++;
3110: }
3111: result[i] = (byte) nextInt;
3112: }
3113: return result;
3114: }
3115: }
|