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