1 /*
   2  * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 /*
  27  * Portions Copyright (c) 1995  Colin Plumb.  All rights reserved.
  28  */
  29 
  30 package java.math;
  31 
  32 import java.util.Random;
  33 import java.io.*;
  34 import java.util.Arrays;
  35 
  36 /**
  37  * Immutable arbitrary-precision integers.  All operations behave as if
  38  * BigIntegers were represented in two's-complement notation (like Java's
  39  * primitive integer types).  BigInteger provides analogues to all of Java's
  40  * primitive integer operators, and all relevant methods from java.lang.Math.
  41  * Additionally, BigInteger provides operations for modular arithmetic, GCD
  42  * calculation, primality testing, prime generation, bit manipulation,
  43  * and a few other miscellaneous operations.
  44  *
  45  * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
  46  * arithmetic operators, as defined in <i>The Java Language Specification</i>.
  47  * For example, division by zero throws an {@code ArithmeticException}, and
  48  * division of a negative by a positive yields a negative (or zero) remainder.
  49  * All of the details in the Spec concerning overflow are ignored, as
  50  * BigIntegers are made as large as necessary to accommodate the results of an
  51  * operation.
  52  *
  53  * <p>Semantics of shift operations extend those of Java's shift operators
  54  * to allow for negative shift distances.  A right-shift with a negative
  55  * shift distance results in a left shift, and vice-versa.  The unsigned
  56  * right shift operator ({@code >>>}) is omitted, as this operation makes
  57  * little sense in combination with the "infinite word size" abstraction
  58  * provided by this class.
  59  *
  60  * <p>Semantics of bitwise logical operations exactly mimic those of Java's
  61  * bitwise integer operators.  The binary operators ({@code and},
  62  * {@code or}, {@code xor}) implicitly perform sign extension on the shorter
  63  * of the two operands prior to performing the operation.
  64  *
  65  * <p>Comparison operations perform signed integer comparisons, analogous to
  66  * those performed by Java's relational and equality operators.
  67  *
  68  * <p>Modular arithmetic operations are provided to compute residues, perform
  69  * exponentiation, and compute multiplicative inverses.  These methods always
  70  * return a non-negative result, between {@code 0} and {@code (modulus - 1)},
  71  * inclusive.
  72  *
  73  * <p>Bit operations operate on a single bit of the two's-complement
  74  * representation of their operand.  If necessary, the operand is sign-
  75  * extended so that it contains the designated bit.  None of the single-bit
  76  * operations can produce a BigInteger with a different sign from the
  77  * BigInteger being operated on, as they affect only a single bit, and the
  78  * "infinite word size" abstraction provided by this class ensures that there
  79  * are infinitely many "virtual sign bits" preceding each BigInteger.
  80  *
  81  * <p>For the sake of brevity and clarity, pseudo-code is used throughout the
  82  * descriptions of BigInteger methods.  The pseudo-code expression
  83  * {@code (i + j)} is shorthand for "a BigInteger whose value is
  84  * that of the BigInteger {@code i} plus that of the BigInteger {@code j}."
  85  * The pseudo-code expression {@code (i == j)} is shorthand for
  86  * "{@code true} if and only if the BigInteger {@code i} represents the same
  87  * value as the BigInteger {@code j}."  Other pseudo-code expressions are
  88  * interpreted similarly.
  89  *
  90  * <p>All methods and constructors in this class throw
  91  * {@code NullPointerException} when passed
  92  * a null object reference for any input parameter.
  93  *
  94  * @see     BigDecimal
  95  * @author  Josh Bloch
  96  * @author  Michael McCloskey
  97  * @since JDK1.1
  98  */
  99 
 100 public class BigInteger extends Number implements Comparable<BigInteger> {
 101     /**
 102      * The signum of this BigInteger: -1 for negative, 0 for zero, or
 103      * 1 for positive.  Note that the BigInteger zero <i>must</i> have
 104      * a signum of 0.  This is necessary to ensures that there is exactly one
 105      * representation for each BigInteger value.
 106      *
 107      * @serial
 108      */
 109     final int signum;
 110 
 111     /**
 112      * The magnitude of this BigInteger, in <i>big-endian</i> order: the
 113      * zeroth element of this array is the most-significant int of the
 114      * magnitude.  The magnitude must be "minimal" in that the most-significant
 115      * int ({@code mag[0]}) must be non-zero.  This is necessary to
 116      * ensure that there is exactly one representation for each BigInteger
 117      * value.  Note that this implies that the BigInteger zero has a
 118      * zero-length mag array.
 119      */
 120     final int[] mag;
 121 
 122     // These "redundant fields" are initialized with recognizable nonsense
 123     // values, and cached the first time they are needed (or never, if they
 124     // aren't needed).
 125 
 126      /**
 127      * One plus the bitCount of this BigInteger. Zeros means unitialized.
 128      *
 129      * @serial
 130      * @see #bitCount
 131      * @deprecated Deprecated since logical value is offset from stored
 132      * value and correction factor is applied in accessor method.
 133      */
 134     @Deprecated
 135     private int bitCount;
 136 
 137     /**
 138      * One plus the bitLength of this BigInteger. Zeros means unitialized.
 139      * (either value is acceptable).
 140      *
 141      * @serial
 142      * @see #bitLength()
 143      * @deprecated Deprecated since logical value is offset from stored
 144      * value and correction factor is applied in accessor method.
 145      */
 146     @Deprecated
 147     private int bitLength;
 148 
 149     /**
 150      * Two plus the lowest set bit of this BigInteger, as returned by
 151      * getLowestSetBit().
 152      *
 153      * @serial
 154      * @see #getLowestSetBit
 155      * @deprecated Deprecated since logical value is offset from stored
 156      * value and correction factor is applied in accessor method.
 157      */
 158     @Deprecated
 159     private int lowestSetBit;
 160 
 161     /**
 162      * Two plus the index of the lowest-order int in the magnitude of this
 163      * BigInteger that contains a nonzero int, or -2 (either value is acceptable).
 164      * The least significant int has int-number 0, the next int in order of
 165      * increasing significance has int-number 1, and so forth.
 166      * @deprecated Deprecated since logical value is offset from stored
 167      * value and correction factor is applied in accessor method.
 168      */
 169     @Deprecated
 170     private int firstNonzeroIntNum;
 171 
 172     /**
 173      * This mask is used to obtain the value of an int as if it were unsigned.
 174      */
 175     final static long LONG_MASK = 0xffffffffL;
 176 
 177     //Constructors
 178 
 179     /**
 180      * Translates a byte array containing the two's-complement binary
 181      * representation of a BigInteger into a BigInteger.  The input array is
 182      * assumed to be in <i>big-endian</i> byte-order: the most significant
 183      * byte is in the zeroth element.
 184      *
 185      * @param  val big-endian two's-complement binary representation of
 186      *         BigInteger.
 187      * @throws NumberFormatException {@code val} is zero bytes long.
 188      */
 189     public BigInteger(byte[] val) {
 190         if (val.length == 0)
 191             throw new NumberFormatException("Zero length BigInteger");
 192 
 193         if (val[0] < 0) {
 194             mag = makePositive(val);
 195             signum = -1;
 196         } else {
 197             mag = stripLeadingZeroBytes(val);
 198             signum = (mag.length == 0 ? 0 : 1);
 199         }
 200     }
 201 
 202     /**
 203      * This private constructor translates an int array containing the
 204      * two's-complement binary representation of a BigInteger into a
 205      * BigInteger. The input array is assumed to be in <i>big-endian</i>
 206      * int-order: the most significant int is in the zeroth element.
 207      */
 208     private BigInteger(int[] val) {
 209         if (val.length == 0)
 210             throw new NumberFormatException("Zero length BigInteger");
 211 
 212         if (val[0] < 0) {
 213             mag = makePositive(val);
 214             signum = -1;
 215         } else {
 216             mag = trustedStripLeadingZeroInts(val);
 217             signum = (mag.length == 0 ? 0 : 1);
 218         }
 219     }
 220 
 221     /**
 222      * Translates the sign-magnitude representation of a BigInteger into a
 223      * BigInteger.  The sign is represented as an integer signum value: -1 for
 224      * negative, 0 for zero, or 1 for positive.  The magnitude is a byte array
 225      * in <i>big-endian</i> byte-order: the most significant byte is in the
 226      * zeroth element.  A zero-length magnitude array is permissible, and will
 227      * result in a BigInteger value of 0, whether signum is -1, 0 or 1.
 228      *
 229      * @param  signum signum of the number (-1 for negative, 0 for zero, 1
 230      *         for positive).
 231      * @param  magnitude big-endian binary representation of the magnitude of
 232      *         the number.
 233      * @throws NumberFormatException {@code signum} is not one of the three
 234      *         legal values (-1, 0, and 1), or {@code signum} is 0 and
 235      *         {@code magnitude} contains one or more non-zero bytes.
 236      */
 237     public BigInteger(int signum, byte[] magnitude) {
 238         this.mag = stripLeadingZeroBytes(magnitude);
 239 
 240         if (signum < -1 || signum > 1)
 241             throw(new NumberFormatException("Invalid signum value"));
 242 
 243         if (this.mag.length==0) {
 244             this.signum = 0;
 245         } else {
 246             if (signum == 0)
 247                 throw(new NumberFormatException("signum-magnitude mismatch"));
 248             this.signum = signum;
 249         }
 250     }
 251 
 252     /**
 253      * A constructor for internal use that translates the sign-magnitude
 254      * representation of a BigInteger into a BigInteger. It checks the
 255      * arguments and copies the magnitude so this constructor would be
 256      * safe for external use.
 257      */
 258     private BigInteger(int signum, int[] magnitude) {
 259         this.mag = stripLeadingZeroInts(magnitude);
 260 
 261         if (signum < -1 || signum > 1)
 262             throw(new NumberFormatException("Invalid signum value"));
 263 
 264         if (this.mag.length==0) {
 265             this.signum = 0;
 266         } else {
 267             if (signum == 0)
 268                 throw(new NumberFormatException("signum-magnitude mismatch"));
 269             this.signum = signum;
 270         }
 271     }
 272 
 273     /**
 274      * Translates the String representation of a BigInteger in the
 275      * specified radix into a BigInteger.  The String representation
 276      * consists of an optional minus or plus sign followed by a
 277      * sequence of one or more digits in the specified radix.  The
 278      * character-to-digit mapping is provided by {@code
 279      * Character.digit}.  The String may not contain any extraneous
 280      * characters (whitespace, for example).
 281      *
 282      * @param val String representation of BigInteger.
 283      * @param radix radix to be used in interpreting {@code val}.
 284      * @throws NumberFormatException {@code val} is not a valid representation
 285      *         of a BigInteger in the specified radix, or {@code radix} is
 286      *         outside the range from {@link Character#MIN_RADIX} to
 287      *         {@link Character#MAX_RADIX}, inclusive.
 288      * @see    Character#digit
 289      */
 290     public BigInteger(String val, int radix) {
 291         int cursor = 0, numDigits;
 292         final int len = val.length();
 293 
 294         if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
 295             throw new NumberFormatException("Radix out of range");
 296         if (len == 0)
 297             throw new NumberFormatException("Zero length BigInteger");
 298 
 299         // Check for at most one leading sign
 300         int sign = 1;
 301         int index1 = val.lastIndexOf('-');
 302         int index2 = val.lastIndexOf('+');
 303         if ((index1 + index2) <= -1) {
 304             // No leading sign character or at most one leading sign character
 305             if (index1 == 0 || index2 == 0) {
 306                 cursor = 1;
 307                 if (len == 1)
 308                     throw new NumberFormatException("Zero length BigInteger");
 309             }
 310             if (index1 == 0)
 311                 sign = -1;
 312         } else
 313             throw new NumberFormatException("Illegal embedded sign character");
 314 
 315         // Skip leading zeros and compute number of digits in magnitude
 316         while (cursor < len &&
 317                Character.digit(val.charAt(cursor), radix) == 0)
 318             cursor++;
 319         if (cursor == len) {
 320             signum = 0;
 321             mag = ZERO.mag;
 322             return;
 323         }
 324 
 325         numDigits = len - cursor;
 326         signum = sign;
 327 
 328         // Pre-allocate array of expected size. May be too large but can
 329         // never be too small. Typically exact.
 330         int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1);
 331         int numWords = (numBits + 31) >>> 5;
 332         int[] magnitude = new int[numWords];
 333 
 334         // Process first (potentially short) digit group
 335         int firstGroupLen = numDigits % digitsPerInt[radix];
 336         if (firstGroupLen == 0)
 337             firstGroupLen = digitsPerInt[radix];
 338         String group = val.substring(cursor, cursor += firstGroupLen);
 339         magnitude[numWords - 1] = Integer.parseInt(group, radix);
 340         if (magnitude[numWords - 1] < 0)
 341             throw new NumberFormatException("Illegal digit");
 342 
 343         // Process remaining digit groups
 344         int superRadix = intRadix[radix];
 345         int groupVal = 0;
 346         while (cursor < len) {
 347             group = val.substring(cursor, cursor += digitsPerInt[radix]);
 348             groupVal = Integer.parseInt(group, radix);
 349             if (groupVal < 0)
 350                 throw new NumberFormatException("Illegal digit");
 351             destructiveMulAdd(magnitude, superRadix, groupVal);
 352         }
 353         // Required for cases where the array was overallocated.
 354         mag = trustedStripLeadingZeroInts(magnitude);
 355     }
 356 
 357     /*
 358      * Constructs a new BigInteger using a char array with radix=10.
 359      * Sign is precalculated outside and not allowed in the val.
 360      */
 361     BigInteger(char[] val, int sign, int len) {
 362         int cursor = 0, numDigits;
 363 
 364         // Skip leading zeros and compute number of digits in magnitude
 365         while (cursor < len && Character.digit(val[cursor], 10) == 0) {
 366             cursor++;
 367         }
 368         if (cursor == len) {
 369             signum = 0;
 370             mag = ZERO.mag;
 371             return;
 372         }
 373 
 374         numDigits = len - cursor;
 375         signum = sign;
 376         // Pre-allocate array of expected size
 377         int numWords;
 378         if (len < 10) {
 379             numWords = 1;
 380         } else {
 381             int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);
 382             numWords = (numBits + 31) >>> 5;
 383         }
 384         int[] magnitude = new int[numWords];
 385 
 386         // Process first (potentially short) digit group
 387         int firstGroupLen = numDigits % digitsPerInt[10];
 388         if (firstGroupLen == 0)
 389             firstGroupLen = digitsPerInt[10];
 390         magnitude[numWords - 1] = parseInt(val, cursor,  cursor += firstGroupLen);
 391 
 392         // Process remaining digit groups
 393         while (cursor < len) {
 394             int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
 395             destructiveMulAdd(magnitude, intRadix[10], groupVal);
 396         }
 397         mag = trustedStripLeadingZeroInts(magnitude);
 398     }
 399 
 400     // Create an integer with the digits between the two indexes
 401     // Assumes start < end. The result may be negative, but it
 402     // is to be treated as an unsigned value.
 403     private int parseInt(char[] source, int start, int end) {
 404         int result = Character.digit(source[start++], 10);
 405         if (result == -1)
 406             throw new NumberFormatException(new String(source));
 407 
 408         for (int index = start; index<end; index++) {
 409             int nextVal = Character.digit(source[index], 10);
 410             if (nextVal == -1)
 411                 throw new NumberFormatException(new String(source));
 412             result = 10*result + nextVal;
 413         }
 414 
 415         return result;
 416     }
 417 
 418     // bitsPerDigit in the given radix times 1024
 419     // Rounded up to avoid underallocation.
 420     private static long bitsPerDigit[] = { 0, 0,
 421         1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
 422         3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
 423         4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
 424                                            5253, 5295};
 425 
 426     // Multiply x array times word y in place, and add word z
 427     private static void destructiveMulAdd(int[] x, int y, int z) {
 428         // Perform the multiplication word by word
 429         long ylong = y & LONG_MASK;
 430         long zlong = z & LONG_MASK;
 431         int len = x.length;
 432 
 433         long product = 0;
 434         long carry = 0;
 435         for (int i = len-1; i >= 0; i--) {
 436             product = ylong * (x[i] & LONG_MASK) + carry;
 437             x[i] = (int)product;
 438             carry = product >>> 32;
 439         }
 440 
 441         // Perform the addition
 442         long sum = (x[len-1] & LONG_MASK) + zlong;
 443         x[len-1] = (int)sum;
 444         carry = sum >>> 32;
 445         for (int i = len-2; i >= 0; i--) {
 446             sum = (x[i] & LONG_MASK) + carry;
 447             x[i] = (int)sum;
 448             carry = sum >>> 32;
 449         }
 450     }
 451 
 452     /**
 453      * Translates the decimal String representation of a BigInteger into a
 454      * BigInteger.  The String representation consists of an optional minus
 455      * sign followed by a sequence of one or more decimal digits.  The
 456      * character-to-digit mapping is provided by {@code Character.digit}.
 457      * The String may not contain any extraneous characters (whitespace, for
 458      * example).
 459      *
 460      * @param val decimal String representation of BigInteger.
 461      * @throws NumberFormatException {@code val} is not a valid representation
 462      *         of a BigInteger.
 463      * @see    Character#digit
 464      */
 465     public BigInteger(String val) {
 466         this(val, 10);
 467     }
 468 
 469     /**
 470      * Constructs a randomly generated BigInteger, uniformly distributed over
 471      * the range 0 to (2<sup>{@code numBits}</sup> - 1), inclusive.
 472      * The uniformity of the distribution assumes that a fair source of random
 473      * bits is provided in {@code rnd}.  Note that this constructor always
 474      * constructs a non-negative BigInteger.
 475      *
 476      * @param  numBits maximum bitLength of the new BigInteger.
 477      * @param  rnd source of randomness to be used in computing the new
 478      *         BigInteger.
 479      * @throws IllegalArgumentException {@code numBits} is negative.
 480      * @see #bitLength()
 481      */
 482     public BigInteger(int numBits, Random rnd) {
 483         this(1, randomBits(numBits, rnd));
 484     }
 485 
 486     private static byte[] randomBits(int numBits, Random rnd) {
 487         if (numBits < 0)
 488             throw new IllegalArgumentException("numBits must be non-negative");
 489         int numBytes = (int)(((long)numBits+7)/8); // avoid overflow
 490         byte[] randomBits = new byte[numBytes];
 491 
 492         // Generate random bytes and mask out any excess bits
 493         if (numBytes > 0) {
 494             rnd.nextBytes(randomBits);
 495             int excessBits = 8*numBytes - numBits;
 496             randomBits[0] &= (1 << (8-excessBits)) - 1;
 497         }
 498         return randomBits;
 499     }
 500 
 501     /**
 502      * Constructs a randomly generated positive BigInteger that is probably
 503      * prime, with the specified bitLength.
 504      *
 505      * <p>It is recommended that the {@link #probablePrime probablePrime}
 506      * method be used in preference to this constructor unless there
 507      * is a compelling need to specify a certainty.
 508      *
 509      * @param  bitLength bitLength of the returned BigInteger.
 510      * @param  certainty a measure of the uncertainty that the caller is
 511      *         willing to tolerate.  The probability that the new BigInteger
 512      *         represents a prime number will exceed
 513      *         (1 - 1/2<sup>{@code certainty}</sup>).  The execution time of
 514      *         this constructor is proportional to the value of this parameter.
 515      * @param  rnd source of random bits used to select candidates to be
 516      *         tested for primality.
 517      * @throws ArithmeticException {@code bitLength < 2}.
 518      * @see    #bitLength()
 519      */
 520     public BigInteger(int bitLength, int certainty, Random rnd) {
 521         BigInteger prime;
 522 
 523         if (bitLength < 2)
 524             throw new ArithmeticException("bitLength < 2");
 525         // The cutoff of 95 was chosen empirically for best performance
 526         prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
 527                                 : largePrime(bitLength, certainty, rnd));
 528         signum = 1;
 529         mag = prime.mag;
 530     }
 531 
 532     // Minimum size in bits that the requested prime number has
 533     // before we use the large prime number generating algorithms
 534     private static final int SMALL_PRIME_THRESHOLD = 95;
 535 
 536     // Certainty required to meet the spec of probablePrime
 537     private static final int DEFAULT_PRIME_CERTAINTY = 100;
 538 
 539     /**
 540      * Returns a positive BigInteger that is probably prime, with the
 541      * specified bitLength. The probability that a BigInteger returned
 542      * by this method is composite does not exceed 2<sup>-100</sup>.
 543      *
 544      * @param  bitLength bitLength of the returned BigInteger.
 545      * @param  rnd source of random bits used to select candidates to be
 546      *         tested for primality.
 547      * @return a BigInteger of {@code bitLength} bits that is probably prime
 548      * @throws ArithmeticException {@code bitLength < 2}.
 549      * @see    #bitLength()
 550      * @since 1.4
 551      */
 552     public static BigInteger probablePrime(int bitLength, Random rnd) {
 553         if (bitLength < 2)
 554             throw new ArithmeticException("bitLength < 2");
 555 
 556         // The cutoff of 95 was chosen empirically for best performance
 557         return (bitLength < SMALL_PRIME_THRESHOLD ?
 558                 smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
 559                 largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
 560     }
 561 
 562     /**
 563      * Find a random number of the specified bitLength that is probably prime.
 564      * This method is used for smaller primes, its performance degrades on
 565      * larger bitlengths.
 566      *
 567      * This method assumes bitLength > 1.
 568      */
 569     private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) {
 570         int magLen = (bitLength + 31) >>> 5;
 571         int temp[] = new int[magLen];
 572         int highBit = 1 << ((bitLength+31) & 0x1f);  // High bit of high int
 573         int highMask = (highBit << 1) - 1;  // Bits to keep in high int
 574 
 575         while(true) {
 576             // Construct a candidate
 577             for (int i=0; i<magLen; i++)
 578                 temp[i] = rnd.nextInt();
 579             temp[0] = (temp[0] & highMask) | highBit;  // Ensure exact length
 580             if (bitLength > 2)
 581                 temp[magLen-1] |= 1;  // Make odd if bitlen > 2
 582 
 583             BigInteger p = new BigInteger(temp, 1);
 584 
 585             // Do cheap "pre-test" if applicable
 586             if (bitLength > 6) {
 587                 long r = p.remainder(SMALL_PRIME_PRODUCT).longValue();
 588                 if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
 589                     (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
 590                     (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0))
 591                     continue; // Candidate is composite; try another
 592             }
 593 
 594             // All candidates of bitLength 2 and 3 are prime by this point
 595             if (bitLength < 4)
 596                 return p;
 597 
 598             // Do expensive test if we survive pre-test (or it's inapplicable)
 599             if (p.primeToCertainty(certainty, rnd))
 600                 return p;
 601         }
 602     }
 603 
 604     private static final BigInteger SMALL_PRIME_PRODUCT
 605                        = valueOf(3L*5*7*11*13*17*19*23*29*31*37*41);
 606 
 607     /**
 608      * Find a random number of the specified bitLength that is probably prime.
 609      * This method is more appropriate for larger bitlengths since it uses
 610      * a sieve to eliminate most composites before using a more expensive
 611      * test.
 612      */
 613     private static BigInteger largePrime(int bitLength, int certainty, Random rnd) {
 614         BigInteger p;
 615         p = new BigInteger(bitLength, rnd).setBit(bitLength-1);
 616         p.mag[p.mag.length-1] &= 0xfffffffe;
 617 
 618         // Use a sieve length likely to contain the next prime number
 619         int searchLen = (bitLength / 20) * 64;
 620         BitSieve searchSieve = new BitSieve(p, searchLen);
 621         BigInteger candidate = searchSieve.retrieve(p, certainty, rnd);
 622 
 623         while ((candidate == null) || (candidate.bitLength() != bitLength)) {
 624             p = p.add(BigInteger.valueOf(2*searchLen));
 625             if (p.bitLength() != bitLength)
 626                 p = new BigInteger(bitLength, rnd).setBit(bitLength-1);
 627             p.mag[p.mag.length-1] &= 0xfffffffe;
 628             searchSieve = new BitSieve(p, searchLen);
 629             candidate = searchSieve.retrieve(p, certainty, rnd);
 630         }
 631         return candidate;
 632     }
 633 
 634    /**
 635     * Returns the first integer greater than this {@code BigInteger} that
 636     * is probably prime.  The probability that the number returned by this
 637     * method is composite does not exceed 2<sup>-100</sup>. This method will
 638     * never skip over a prime when searching: if it returns {@code p}, there
 639     * is no prime {@code q} such that {@code this < q < p}.
 640     *
 641     * @return the first integer greater than this {@code BigInteger} that
 642     *         is probably prime.
 643     * @throws ArithmeticException {@code this < 0}.
 644     * @since 1.5
 645     */
 646     public BigInteger nextProbablePrime() {
 647         if (this.signum < 0)
 648             throw new ArithmeticException("start < 0: " + this);
 649 
 650         // Handle trivial cases
 651         if ((this.signum == 0) || this.equals(ONE))
 652             return TWO;
 653 
 654         BigInteger result = this.add(ONE);
 655 
 656         // Fastpath for small numbers
 657         if (result.bitLength() < SMALL_PRIME_THRESHOLD) {
 658 
 659             // Ensure an odd number
 660             if (!result.testBit(0))
 661                 result = result.add(ONE);
 662 
 663             while(true) {
 664                 // Do cheap "pre-test" if applicable
 665                 if (result.bitLength() > 6) {
 666                     long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
 667                     if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) ||
 668                         (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
 669                         (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
 670                         result = result.add(TWO);
 671                         continue; // Candidate is composite; try another
 672                     }
 673                 }
 674 
 675                 // All candidates of bitLength 2 and 3 are prime by this point
 676                 if (result.bitLength() < 4)
 677                     return result;
 678 
 679                 // The expensive test
 680                 if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
 681                     return result;
 682 
 683                 result = result.add(TWO);
 684             }
 685         }
 686 
 687         // Start at previous even number
 688         if (result.testBit(0))
 689             result = result.subtract(ONE);
 690 
 691         // Looking for the next large prime
 692         int searchLen = (result.bitLength() / 20) * 64;
 693 
 694         while(true) {
 695            BitSieve searchSieve = new BitSieve(result, searchLen);
 696            BigInteger candidate = searchSieve.retrieve(result,
 697                                                  DEFAULT_PRIME_CERTAINTY, null);
 698            if (candidate != null)
 699                return candidate;
 700            result = result.add(BigInteger.valueOf(2 * searchLen));
 701         }
 702     }
 703 
 704     /**
 705      * Returns {@code true} if this BigInteger is probably prime,
 706      * {@code false} if it's definitely composite.
 707      *
 708      * This method assumes bitLength > 2.
 709      *
 710      * @param  certainty a measure of the uncertainty that the caller is
 711      *         willing to tolerate: if the call returns {@code true}
 712      *         the probability that this BigInteger is prime exceeds
 713      *         {@code (1 - 1/2<sup>certainty</sup>)}.  The execution time of
 714      *         this method is proportional to the value of this parameter.
 715      * @return {@code true} if this BigInteger is probably prime,
 716      *         {@code false} if it's definitely composite.
 717      */
 718     boolean primeToCertainty(int certainty, Random random) {
 719         int rounds = 0;
 720         int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;
 721 
 722         // The relationship between the certainty and the number of rounds
 723         // we perform is given in the draft standard ANSI X9.80, "PRIME
 724         // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
 725         int sizeInBits = this.bitLength();
 726         if (sizeInBits < 100) {
 727             rounds = 50;
 728             rounds = n < rounds ? n : rounds;
 729             return passesMillerRabin(rounds, random);
 730         }
 731 
 732         if (sizeInBits < 256) {
 733             rounds = 27;
 734         } else if (sizeInBits < 512) {
 735             rounds = 15;
 736         } else if (sizeInBits < 768) {
 737             rounds = 8;
 738         } else if (sizeInBits < 1024) {
 739             rounds = 4;
 740         } else {
 741             rounds = 2;
 742         }
 743         rounds = n < rounds ? n : rounds;
 744 
 745         return passesMillerRabin(rounds, random) && passesLucasLehmer();
 746     }
 747 
 748     /**
 749      * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
 750      *
 751      * The following assumptions are made:
 752      * This BigInteger is a positive, odd number.
 753      */
 754     private boolean passesLucasLehmer() {
 755         BigInteger thisPlusOne = this.add(ONE);
 756 
 757         // Step 1
 758         int d = 5;
 759         while (jacobiSymbol(d, this) != -1) {
 760             // 5, -7, 9, -11, ...
 761             d = (d<0) ? Math.abs(d)+2 : -(d+2);
 762         }
 763 
 764         // Step 2
 765         BigInteger u = lucasLehmerSequence(d, thisPlusOne, this);
 766 
 767         // Step 3
 768         return u.mod(this).equals(ZERO);
 769     }
 770 
 771     /**
 772      * Computes Jacobi(p,n).
 773      * Assumes n positive, odd, n>=3.
 774      */
 775     private static int jacobiSymbol(int p, BigInteger n) {
 776         if (p == 0)
 777             return 0;
 778 
 779         // Algorithm and comments adapted from Colin Plumb's C library.
 780         int j = 1;
 781         int u = n.mag[n.mag.length-1];
 782 
 783         // Make p positive
 784         if (p < 0) {
 785             p = -p;
 786             int n8 = u & 7;
 787             if ((n8 == 3) || (n8 == 7))
 788                 j = -j; // 3 (011) or 7 (111) mod 8
 789         }
 790 
 791         // Get rid of factors of 2 in p
 792         while ((p & 3) == 0)
 793             p >>= 2;
 794         if ((p & 1) == 0) {
 795             p >>= 1;
 796             if (((u ^ (u>>1)) & 2) != 0)
 797                 j = -j; // 3 (011) or 5 (101) mod 8
 798         }
 799         if (p == 1)
 800             return j;
 801         // Then, apply quadratic reciprocity
 802         if ((p & u & 2) != 0)   // p = u = 3 (mod 4)?
 803             j = -j;
 804         // And reduce u mod p
 805         u = n.mod(BigInteger.valueOf(p)).intValue();
 806 
 807         // Now compute Jacobi(u,p), u < p
 808         while (u != 0) {
 809             while ((u & 3) == 0)
 810                 u >>= 2;
 811             if ((u & 1) == 0) {
 812                 u >>= 1;
 813                 if (((p ^ (p>>1)) & 2) != 0)
 814                     j = -j;     // 3 (011) or 5 (101) mod 8
 815             }
 816             if (u == 1)
 817                 return j;
 818             // Now both u and p are odd, so use quadratic reciprocity
 819             assert (u < p);
 820             int t = u; u = p; p = t;
 821             if ((u & p & 2) != 0) // u = p = 3 (mod 4)?
 822                 j = -j;
 823             // Now u >= p, so it can be reduced
 824             u %= p;
 825         }
 826         return 0;
 827     }
 828 
 829     private static BigInteger lucasLehmerSequence(int z, BigInteger k, BigInteger n) {
 830         BigInteger d = BigInteger.valueOf(z);
 831         BigInteger u = ONE; BigInteger u2;
 832         BigInteger v = ONE; BigInteger v2;
 833 
 834         for (int i=k.bitLength()-2; i>=0; i--) {
 835             u2 = u.multiply(v).mod(n);
 836 
 837             v2 = v.square().add(d.multiply(u.square())).mod(n);
 838             if (v2.testBit(0))
 839                 v2 = v2.subtract(n);
 840 
 841             v2 = v2.shiftRight(1);
 842 
 843             u = u2; v = v2;
 844             if (k.testBit(i)) {
 845                 u2 = u.add(v).mod(n);
 846                 if (u2.testBit(0))
 847                     u2 = u2.subtract(n);
 848 
 849                 u2 = u2.shiftRight(1);
 850                 v2 = v.add(d.multiply(u)).mod(n);
 851                 if (v2.testBit(0))
 852                     v2 = v2.subtract(n);
 853                 v2 = v2.shiftRight(1);
 854 
 855                 u = u2; v = v2;
 856             }
 857         }
 858         return u;
 859     }
 860 
 861     private static volatile Random staticRandom;
 862 
 863     private static Random getSecureRandom() {
 864         if (staticRandom == null) {
 865             staticRandom = new java.security.SecureRandom();
 866         }
 867         return staticRandom;
 868     }
 869 
 870     /**
 871      * Returns true iff this BigInteger passes the specified number of
 872      * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
 873      * 186-2).
 874      *
 875      * The following assumptions are made:
 876      * This BigInteger is a positive, odd number greater than 2.
 877      * iterations<=50.
 878      */
 879     private boolean passesMillerRabin(int iterations, Random rnd) {
 880         // Find a and m such that m is odd and this == 1 + 2**a * m
 881         BigInteger thisMinusOne = this.subtract(ONE);
 882         BigInteger m = thisMinusOne;
 883         int a = m.getLowestSetBit();
 884         m = m.shiftRight(a);
 885 
 886         // Do the tests
 887         if (rnd == null) {
 888             rnd = getSecureRandom();
 889         }
 890         for (int i=0; i<iterations; i++) {
 891             // Generate a uniform random on (1, this)
 892             BigInteger b;
 893             do {
 894                 b = new BigInteger(this.bitLength(), rnd);
 895             } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);
 896 
 897             int j = 0;
 898             BigInteger z = b.modPow(m, this);
 899             while(!((j==0 && z.equals(ONE)) || z.equals(thisMinusOne))) {
 900                 if (j>0 && z.equals(ONE) || ++j==a)
 901                     return false;
 902                 z = z.modPow(TWO, this);
 903             }
 904         }
 905         return true;
 906     }
 907 
 908     /**
 909      * This internal constructor differs from its public cousin
 910      * with the arguments reversed in two ways: it assumes that its
 911      * arguments are correct, and it doesn't copy the magnitude array.
 912      */
 913     BigInteger(int[] magnitude, int signum) {
 914         this.signum = (magnitude.length==0 ? 0 : signum);
 915         this.mag = magnitude;
 916     }
 917 
 918     /**
 919      * This private constructor is for internal use and assumes that its
 920      * arguments are correct.
 921      */
 922     private BigInteger(byte[] magnitude, int signum) {
 923         this.signum = (magnitude.length==0 ? 0 : signum);
 924         this.mag = stripLeadingZeroBytes(magnitude);
 925     }
 926 
 927     //Static Factory Methods
 928 
 929     /**
 930      * Returns a BigInteger whose value is equal to that of the
 931      * specified {@code long}.  This "static factory method" is
 932      * provided in preference to a ({@code long}) constructor
 933      * because it allows for reuse of frequently used BigIntegers.
 934      *
 935      * @param  val value of the BigInteger to return.
 936      * @return a BigInteger with the specified value.
 937      */
 938     public static BigInteger valueOf(long val) {
 939         // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
 940         if (val == 0)
 941             return ZERO;
 942         if (val > 0 && val <= MAX_CONSTANT)
 943             return posConst[(int) val];
 944         else if (val < 0 && val >= -MAX_CONSTANT)
 945             return negConst[(int) -val];
 946 
 947         return new BigInteger(val);
 948     }
 949 
 950     /**
 951      * Constructs a BigInteger with the specified value, which may not be zero.
 952      */
 953     private BigInteger(long val) {
 954         if (val < 0) {
 955             val = -val;
 956             signum = -1;
 957         } else {
 958             signum = 1;
 959         }
 960 
 961         int highWord = (int)(val >>> 32);
 962         if (highWord==0) {
 963             mag = new int[1];
 964             mag[0] = (int)val;
 965         } else {
 966             mag = new int[2];
 967             mag[0] = highWord;
 968             mag[1] = (int)val;
 969         }
 970     }
 971 
 972     /**
 973      * Returns a BigInteger with the given two's complement representation.
 974      * Assumes that the input array will not be modified (the returned
 975      * BigInteger will reference the input array if feasible).
 976      */
 977     private static BigInteger valueOf(int val[]) {
 978         return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
 979     }
 980 
 981     // Constants
 982 
 983     /**
 984      * Initialize static constant array when class is loaded.
 985      */
 986     private final static int MAX_CONSTANT = 16;
 987     private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
 988     private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
 989     static {
 990         for (int i = 1; i <= MAX_CONSTANT; i++) {
 991             int[] magnitude = new int[1];
 992             magnitude[0] = i;
 993             posConst[i] = new BigInteger(magnitude,  1);
 994             negConst[i] = new BigInteger(magnitude, -1);
 995         }
 996     }
 997 
 998     /**
 999      * The BigInteger constant zero.
1000      *
1001      * @since   1.2
1002      */
1003     public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1004 
1005     /**
1006      * The BigInteger constant one.
1007      *
1008      * @since   1.2
1009      */
1010     public static final BigInteger ONE = valueOf(1);
1011 
1012     /**
1013      * The BigInteger constant two.  (Not exported.)
1014      */
1015     private static final BigInteger TWO = valueOf(2);
1016 
1017     /**
1018      * The BigInteger constant ten.
1019      *
1020      * @since   1.5
1021      */
1022     public static final BigInteger TEN = valueOf(10);
1023 
1024     // Arithmetic Operations
1025 
1026     /**
1027      * Returns a BigInteger whose value is {@code (this + val)}.
1028      *
1029      * @param  val value to be added to this BigInteger.
1030      * @return {@code this + val}
1031      */
1032     public BigInteger add(BigInteger val) {
1033         if (val.signum == 0)
1034             return this;
1035         if (signum == 0)
1036             return val;
1037         if (val.signum == signum)
1038             return new BigInteger(add(mag, val.mag), signum);
1039 
1040         int cmp = compareMagnitude(val);
1041         if (cmp == 0)
1042             return ZERO;
1043         int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1044                            : subtract(val.mag, mag));
1045         resultMag = trustedStripLeadingZeroInts(resultMag);
1046 
1047         return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1048     }
1049 
1050     /**
1051      * Package private methods used by BigDecimal code to add a BigInteger
1052      * with a long. Assumes val is not equal to INFLATED.
1053      */
1054     BigInteger add(long val) {
1055         if (val == 0)
1056             return this;
1057         if (signum == 0)
1058             return valueOf(val);
1059         if (Long.signum(val) == signum)
1060             return new BigInteger(add(mag, Math.abs(val)), signum);
1061         int cmp = compareMagnitude(val);
1062         if (cmp == 0)
1063             return ZERO;
1064         int[] resultMag = (cmp > 0 ? subtract(mag, Math.abs(val)) : subtract(Math.abs(val), mag));
1065         resultMag = trustedStripLeadingZeroInts(resultMag);
1066         return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1067     }
1068 
1069     /**
1070      * Adds the contents of the int array x and long value val. This
1071      * method allocates a new int array to hold the answer and returns
1072      * a reference to that array.  Assumes x.length &gt; 0 and val is
1073      * non-negative
1074      */
1075     private static int[] add(int[] x, long val) {
1076         int[] y;
1077         long sum = 0;
1078         int xIndex = x.length;
1079         int[] result;
1080         int highWord = (int)(val >>> 32);
1081         if (highWord==0) {
1082             result = new int[xIndex];
1083             sum = (x[--xIndex] & LONG_MASK) + val;
1084             result[xIndex] = (int)sum;
1085         } else {
1086             if (xIndex == 1) {
1087                 result = new int[2];
1088                 sum = val  + (x[0] & LONG_MASK);
1089                 result[1] = (int)sum;
1090                 result[0] = (int)(sum >>> 32);
1091                 return result;
1092             } else {
1093                 result = new int[xIndex];
1094                 sum = (x[--xIndex] & LONG_MASK) + (val & LONG_MASK);
1095                 result[xIndex] = (int)sum;
1096                 sum = (x[--xIndex] & LONG_MASK) + (highWord & LONG_MASK) + (sum >>> 32);
1097                 result[xIndex] = (int)sum;
1098             }
1099         }
1100         // Copy remainder of longer number while carry propagation is required
1101         boolean carry = (sum >>> 32 != 0);
1102         while (xIndex > 0 && carry)
1103             carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1104         // Copy remainder of longer number
1105         while (xIndex > 0)
1106             result[--xIndex] = x[xIndex];
1107         // Grow result if necessary
1108         if (carry) {
1109             int bigger[] = new int[result.length + 1];
1110             System.arraycopy(result, 0, bigger, 1, result.length);
1111             bigger[0] = 0x01;
1112             return bigger;
1113         }
1114         return result;
1115     }
1116 
1117     /**
1118      * Adds the contents of the int arrays x and y. This method allocates
1119      * a new int array to hold the answer and returns a reference to that
1120      * array.
1121      */
1122     private static int[] add(int[] x, int[] y) {
1123         // If x is shorter, swap the two arrays
1124         if (x.length < y.length) {
1125             int[] tmp = x;
1126             x = y;
1127             y = tmp;
1128         }
1129 
1130         int xIndex = x.length;
1131         int yIndex = y.length;
1132         int result[] = new int[xIndex];
1133         long sum = 0;
1134         if(yIndex==1) {
1135             sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ;
1136             result[xIndex] = (int)sum;
1137         } else {
1138             // Add common parts of both numbers
1139             while(yIndex > 0) {
1140                 sum = (x[--xIndex] & LONG_MASK) +
1141                       (y[--yIndex] & LONG_MASK) + (sum >>> 32);
1142                 result[xIndex] = (int)sum;
1143             }
1144         }
1145         // Copy remainder of longer number while carry propagation is required
1146         boolean carry = (sum >>> 32 != 0);
1147         while (xIndex > 0 && carry)
1148             carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1149 
1150         // Copy remainder of longer number
1151         while (xIndex > 0)
1152             result[--xIndex] = x[xIndex];
1153 
1154         // Grow result if necessary
1155         if (carry) {
1156             int bigger[] = new int[result.length + 1];
1157             System.arraycopy(result, 0, bigger, 1, result.length);
1158             bigger[0] = 0x01;
1159             return bigger;
1160         }
1161         return result;
1162     }
1163 
1164     private static int[] subtract(long val, int[] little) {
1165         int highWord = (int)(val >>> 32);
1166         if (highWord==0) {
1167             int result[] = new int[1];
1168             result[0] = (int)(val - (little[0] & LONG_MASK));
1169             return result;
1170         } else {
1171             int result[] = new int[2];
1172             if(little.length==1) {
1173                 long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK);
1174                 result[1] = (int)difference;
1175                 // Subtract remainder of longer number while borrow propagates
1176                 boolean borrow = (difference >> 32 != 0);
1177                 if(borrow) {
1178                     result[0] = highWord - 1;
1179                 } else {        // Copy remainder of longer number
1180                     result[0] = highWord;
1181                 }
1182                 return result;
1183             } else { // little.length==2
1184                 long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK);
1185                 result[1] = (int)difference;
1186                 difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32);
1187                 result[0] = (int)difference;
1188                 return result;
1189             }
1190         }
1191     }
1192 
1193     /**
1194      * Subtracts the contents of the second argument (val) from the
1195      * first (big).  The first int array (big) must represent a larger number
1196      * than the second.  This method allocates the space necessary to hold the
1197      * answer.
1198      * assumes val &gt;= 0
1199      */
1200     private static int[] subtract(int[] big, long val) {
1201         int highWord = (int)(val >>> 32);
1202         int bigIndex = big.length;
1203         int result[] = new int[bigIndex];
1204         long difference = 0;
1205 
1206         if (highWord==0) {
1207             difference = (big[--bigIndex] & LONG_MASK) - val;
1208             result[bigIndex] = (int)difference;
1209         } else {
1210             difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK);
1211             result[bigIndex] = (int)difference;
1212             difference = (big[--bigIndex] & LONG_MASK) - (highWord & LONG_MASK) + (difference >> 32);
1213             result[bigIndex] = (int)difference;
1214         }
1215 
1216 
1217         // Subtract remainder of longer number while borrow propagates
1218         boolean borrow = (difference >> 32 != 0);
1219         while (bigIndex > 0 && borrow)
1220             borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1221 
1222         // Copy remainder of longer number
1223         while (bigIndex > 0)
1224             result[--bigIndex] = big[bigIndex];
1225 
1226         return result;
1227     }
1228 
1229     /**
1230      * Returns a BigInteger whose value is {@code (this - val)}.
1231      *
1232      * @param  val value to be subtracted from this BigInteger.
1233      * @return {@code this - val}
1234      */
1235     public BigInteger subtract(BigInteger val) {
1236         if (val.signum == 0)
1237             return this;
1238         if (signum == 0)
1239             return val.negate();
1240         if (val.signum != signum)
1241             return new BigInteger(add(mag, val.mag), signum);
1242 
1243         int cmp = compareMagnitude(val);
1244         if (cmp == 0)
1245             return ZERO;
1246         int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1247                            : subtract(val.mag, mag));
1248         resultMag = trustedStripLeadingZeroInts(resultMag);
1249         return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1250     }
1251 
1252     /**
1253      * Subtracts the contents of the second int arrays (little) from the
1254      * first (big).  The first int array (big) must represent a larger number
1255      * than the second.  This method allocates the space necessary to hold the
1256      * answer.
1257      */
1258     private static int[] subtract(int[] big, int[] little) {
1259         int bigIndex = big.length;
1260         int result[] = new int[bigIndex];
1261         int littleIndex = little.length;
1262         long difference = 0;
1263 
1264         // Subtract common parts of both numbers
1265         while(littleIndex > 0) {
1266             difference = (big[--bigIndex] & LONG_MASK) -
1267                          (little[--littleIndex] & LONG_MASK) +
1268                          (difference >> 32);
1269             result[bigIndex] = (int)difference;
1270         }
1271 
1272         // Subtract remainder of longer number while borrow propagates
1273         boolean borrow = (difference >> 32 != 0);
1274         while (bigIndex > 0 && borrow)
1275             borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1276 
1277         // Copy remainder of longer number
1278         while (bigIndex > 0)
1279             result[--bigIndex] = big[bigIndex];
1280 
1281         return result;
1282     }
1283 
1284     /**
1285      * Returns a BigInteger whose value is {@code (this * val)}.
1286      *
1287      * @param  val value to be multiplied by this BigInteger.
1288      * @return {@code this * val}
1289      */
1290     public BigInteger multiply(BigInteger val) {
1291         if (val.signum == 0 || signum == 0)
1292             return ZERO;
1293         int resultSign = signum == val.signum ? 1 : -1;
1294         if (val.mag.length == 1) {
1295             return  multiplyByInt(mag,val.mag[0], resultSign);
1296         }
1297         if(mag.length == 1) {
1298             return multiplyByInt(val.mag,mag[0], resultSign);
1299         }
1300         int[] result = multiplyToLen(mag, mag.length,
1301                                      val.mag, val.mag.length, null);
1302         result = trustedStripLeadingZeroInts(result);
1303         return new BigInteger(result, resultSign);
1304     }
1305 
1306     private static BigInteger multiplyByInt(int[] x, int y, int sign) {
1307         if(Integer.bitCount(y)==1) {
1308             return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign);
1309         }
1310         int xlen = x.length;
1311         int[] rmag =  new int[xlen + 1];
1312         long carry = 0;
1313         long yl = y & LONG_MASK;
1314         int rstart = rmag.length - 1;
1315         for (int i = xlen - 1; i >= 0; i--) {
1316             long product = (x[i] & LONG_MASK) * yl + carry;
1317             rmag[rstart--] = (int)product;
1318             carry = product >>> 32;
1319         }
1320         if (carry == 0L) {
1321             rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
1322         } else {
1323             rmag[rstart] = (int)carry;
1324         }
1325         return new BigInteger(rmag, sign);
1326     }
1327 
1328     /**
1329      * Package private methods used by BigDecimal code to multiply a BigInteger
1330      * with a long. Assumes v is not equal to INFLATED.
1331      */
1332     BigInteger multiply(long v) {
1333         if (v == 0 || signum == 0)
1334           return ZERO;
1335         if (v == BigDecimal.INFLATED)
1336             return multiply(BigInteger.valueOf(v));
1337         int rsign = (v > 0 ? signum : -signum);
1338         if (v < 0)
1339             v = -v;
1340         long dh = v >>> 32;      // higher order bits
1341         long dl = v & LONG_MASK; // lower order bits
1342 
1343         int xlen = mag.length;
1344         int[] value = mag;
1345         int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]);
1346         long carry = 0;
1347         int rstart = rmag.length - 1;
1348         for (int i = xlen - 1; i >= 0; i--) {
1349             long product = (value[i] & LONG_MASK) * dl + carry;
1350             rmag[rstart--] = (int)product;
1351             carry = product >>> 32;
1352         }
1353         rmag[rstart] = (int)carry;
1354         if (dh != 0L) {
1355             carry = 0;
1356             rstart = rmag.length - 2;
1357             for (int i = xlen - 1; i >= 0; i--) {
1358                 long product = (value[i] & LONG_MASK) * dh +
1359                     (rmag[rstart] & LONG_MASK) + carry;
1360                 rmag[rstart--] = (int)product;
1361                 carry = product >>> 32;
1362             }
1363             rmag[0] = (int)carry;
1364         }
1365         if (carry == 0L)
1366             rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
1367         return new BigInteger(rmag, rsign);
1368     }
1369 
1370     /**
1371      * Multiplies int arrays x and y to the specified lengths and places
1372      * the result into z. There will be no leading zeros in the resultant array.
1373      */
1374     private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
1375         int xstart = xlen - 1;
1376         int ystart = ylen - 1;
1377 
1378         if (z == null || z.length < (xlen+ ylen))
1379             z = new int[xlen+ylen];
1380 
1381         long carry = 0;
1382         for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) {
1383             long product = (y[j] & LONG_MASK) *
1384                            (x[xstart] & LONG_MASK) + carry;
1385             z[k] = (int)product;
1386             carry = product >>> 32;
1387         }
1388         z[xstart] = (int)carry;
1389 
1390         for (int i = xstart-1; i >= 0; i--) {
1391             carry = 0;
1392             for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {
1393                 long product = (y[j] & LONG_MASK) *
1394                                (x[i] & LONG_MASK) +
1395                                (z[k] & LONG_MASK) + carry;
1396                 z[k] = (int)product;
1397                 carry = product >>> 32;
1398             }
1399             z[i] = (int)carry;
1400         }
1401         return z;
1402     }
1403 
1404     /**
1405      * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
1406      *
1407      * @return {@code this<sup>2</sup>}
1408      */
1409     private BigInteger square() {
1410         if (signum == 0)
1411             return ZERO;
1412         int[] z = squareToLen(mag, mag.length, null);
1413         return new BigInteger(trustedStripLeadingZeroInts(z), 1);
1414     }
1415 
1416     /**
1417      * Squares the contents of the int array x. The result is placed into the
1418      * int array z.  The contents of x are not changed.
1419      */
1420     private static final int[] squareToLen(int[] x, int len, int[] z) {
1421         /*
1422          * The algorithm used here is adapted from Colin Plumb's C library.
1423          * Technique: Consider the partial products in the multiplication
1424          * of "abcde" by itself:
1425          *
1426          *               a  b  c  d  e
1427          *            *  a  b  c  d  e
1428          *          ==================
1429          *              ae be ce de ee
1430          *           ad bd cd dd de
1431          *        ac bc cc cd ce
1432          *     ab bb bc bd be
1433          *  aa ab ac ad ae
1434          *
1435          * Note that everything above the main diagonal:
1436          *              ae be ce de = (abcd) * e
1437          *           ad bd cd       = (abc) * d
1438          *        ac bc             = (ab) * c
1439          *     ab                   = (a) * b
1440          *
1441          * is a copy of everything below the main diagonal:
1442          *                       de
1443          *                 cd ce
1444          *           bc bd be
1445          *     ab ac ad ae
1446          *
1447          * Thus, the sum is 2 * (off the diagonal) + diagonal.
1448          *
1449          * This is accumulated beginning with the diagonal (which
1450          * consist of the squares of the digits of the input), which is then
1451          * divided by two, the off-diagonal added, and multiplied by two
1452          * again.  The low bit is simply a copy of the low bit of the
1453          * input, so it doesn't need special care.
1454          */
1455         int zlen = len << 1;
1456         if (z == null || z.length < zlen)
1457             z = new int[zlen];
1458 
1459         // Store the squares, right shifted one bit (i.e., divided by 2)
1460         int lastProductLowWord = 0;
1461         for (int j=0, i=0; j<len; j++) {
1462             long piece = (x[j] & LONG_MASK);
1463             long product = piece * piece;
1464             z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33);
1465             z[i++] = (int)(product >>> 1);
1466             lastProductLowWord = (int)product;
1467         }
1468 
1469         // Add in off-diagonal sums
1470         for (int i=len, offset=1; i>0; i--, offset+=2) {
1471             int t = x[i-1];
1472             t = mulAdd(z, x, offset, i-1, t);
1473             addOne(z, offset-1, i, t);
1474         }
1475 
1476         // Shift back up and set low bit
1477         primitiveLeftShift(z, zlen, 1);
1478         z[zlen-1] |= x[len-1] & 1;
1479 
1480         return z;
1481     }
1482 
1483     /**
1484      * Returns a BigInteger whose value is {@code (this / val)}.
1485      *
1486      * @param  val value by which this BigInteger is to be divided.
1487      * @return {@code this / val}
1488      * @throws ArithmeticException if {@code val} is zero.
1489      */
1490     public BigInteger divide(BigInteger val) {
1491         MutableBigInteger q = new MutableBigInteger(),
1492                           a = new MutableBigInteger(this.mag),
1493                           b = new MutableBigInteger(val.mag);
1494 
1495         a.divide(b, q, false);
1496         return q.toBigInteger(this.signum * val.signum);
1497     }
1498 
1499     /**
1500      * Returns an array of two BigIntegers containing {@code (this / val)}
1501      * followed by {@code (this % val)}.
1502      *
1503      * @param  val value by which this BigInteger is to be divided, and the
1504      *         remainder computed.
1505      * @return an array of two BigIntegers: the quotient {@code (this / val)}
1506      *         is the initial element, and the remainder {@code (this % val)}
1507      *         is the final element.
1508      * @throws ArithmeticException if {@code val} is zero.
1509      */
1510     public BigInteger[] divideAndRemainder(BigInteger val) {
1511         BigInteger[] result = new BigInteger[2];
1512         MutableBigInteger q = new MutableBigInteger(),
1513                           a = new MutableBigInteger(this.mag),
1514                           b = new MutableBigInteger(val.mag);
1515         MutableBigInteger r = a.divide(b, q);
1516         result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
1517         result[1] = r.toBigInteger(this.signum);
1518         return result;
1519     }
1520 
1521     /**
1522      * Returns a BigInteger whose value is {@code (this % val)}.
1523      *
1524      * @param  val value by which this BigInteger is to be divided, and the
1525      *         remainder computed.
1526      * @return {@code this % val}
1527      * @throws ArithmeticException if {@code val} is zero.
1528      */
1529     public BigInteger remainder(BigInteger val) {
1530         MutableBigInteger q = new MutableBigInteger(),
1531                           a = new MutableBigInteger(this.mag),
1532                           b = new MutableBigInteger(val.mag);
1533 
1534         return a.divide(b, q).toBigInteger(this.signum);
1535     }
1536 
1537     /**
1538      * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
1539      * Note that {@code exponent} is an integer rather than a BigInteger.
1540      *
1541      * @param  exponent exponent to which this BigInteger is to be raised.
1542      * @return <tt>this<sup>exponent</sup></tt>
1543      * @throws ArithmeticException {@code exponent} is negative.  (This would
1544      *         cause the operation to yield a non-integer value.)
1545      */
1546     public BigInteger pow(int exponent) {
1547         if (exponent < 0)
1548             throw new ArithmeticException("Negative exponent");
1549         if (signum==0)
1550             return (exponent==0 ? ONE : this);
1551 
1552         // Perform exponentiation using repeated squaring trick
1553         int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
1554         int[] baseToPow2 = this.mag;
1555         int[] result = {1};
1556 
1557         while (exponent != 0) {
1558             if ((exponent & 1)==1) {
1559                 result = multiplyToLen(result, result.length,
1560                                        baseToPow2, baseToPow2.length, null);
1561                 result = trustedStripLeadingZeroInts(result);
1562             }
1563             if ((exponent >>>= 1) != 0) {
1564                 baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
1565                 baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
1566             }
1567         }
1568         return new BigInteger(result, newSign);
1569     }
1570 
1571     /**
1572      * Returns a BigInteger whose value is the greatest common divisor of
1573      * {@code abs(this)} and {@code abs(val)}.  Returns 0 if
1574      * {@code this==0 && val==0}.
1575      *
1576      * @param  val value with which the GCD is to be computed.
1577      * @return {@code GCD(abs(this), abs(val))}
1578      */
1579     public BigInteger gcd(BigInteger val) {
1580         if (val.signum == 0)
1581             return this.abs();
1582         else if (this.signum == 0)
1583             return val.abs();
1584 
1585         MutableBigInteger a = new MutableBigInteger(this);
1586         MutableBigInteger b = new MutableBigInteger(val);
1587 
1588         MutableBigInteger result = a.hybridGCD(b);
1589 
1590         return result.toBigInteger(1);
1591     }
1592 
1593     /**
1594      * Package private method to return bit length for an integer.
1595      */
1596     static int bitLengthForInt(int n) {
1597         return 32 - Integer.numberOfLeadingZeros(n);
1598     }
1599 
1600     /**
1601      * Left shift int array a up to len by n bits. Returns the array that
1602      * results from the shift since space may have to be reallocated.
1603      */
1604     private static int[] leftShift(int[] a, int len, int n) {
1605         int nInts = n >>> 5;
1606         int nBits = n&0x1F;
1607         int bitsInHighWord = bitLengthForInt(a[0]);
1608 
1609         // If shift can be done without recopy, do so
1610         if (n <= (32-bitsInHighWord)) {
1611             primitiveLeftShift(a, len, nBits);
1612             return a;
1613         } else { // Array must be resized
1614             if (nBits <= (32-bitsInHighWord)) {
1615                 int result[] = new int[nInts+len];
1616                 System.arraycopy(a, 0, result, 0, len);
1617                 primitiveLeftShift(result, result.length, nBits);
1618                 return result;
1619             } else {
1620                 int result[] = new int[nInts+len+1];
1621                 System.arraycopy(a, 0, result, 0, len);
1622                 primitiveRightShift(result, result.length, 32 - nBits);
1623                 return result;
1624             }
1625         }
1626     }
1627 
1628     // shifts a up to len right n bits assumes no leading zeros, 0<n<32
1629     static void primitiveRightShift(int[] a, int len, int n) {
1630         int n2 = 32 - n;
1631         for (int i=len-1, c=a[i]; i>0; i--) {
1632             int b = c;
1633             c = a[i-1];
1634             a[i] = (c << n2) | (b >>> n);
1635         }
1636         a[0] >>>= n;
1637     }
1638 
1639     // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
1640     static void primitiveLeftShift(int[] a, int len, int n) {
1641         if (len == 0 || n == 0)
1642             return;
1643 
1644         int n2 = 32 - n;
1645         for (int i=0, c=a[i], m=i+len-1; i<m; i++) {
1646             int b = c;
1647             c = a[i+1];
1648             a[i] = (b << n) | (c >>> n2);
1649         }
1650         a[len-1] <<= n;
1651     }
1652 
1653     /**
1654      * Calculate bitlength of contents of the first len elements an int array,
1655      * assuming there are no leading zero ints.
1656      */
1657     private static int bitLength(int[] val, int len) {
1658         if (len == 0)
1659             return 0;
1660         return ((len - 1) << 5) + bitLengthForInt(val[0]);
1661     }
1662 
1663     /**
1664      * Returns a BigInteger whose value is the absolute value of this
1665      * BigInteger.
1666      *
1667      * @return {@code abs(this)}
1668      */
1669     public BigInteger abs() {
1670         return (signum >= 0 ? this : this.negate());
1671     }
1672 
1673     /**
1674      * Returns a BigInteger whose value is {@code (-this)}.
1675      *
1676      * @return {@code -this}
1677      */
1678     public BigInteger negate() {
1679         return new BigInteger(this.mag, -this.signum);
1680     }
1681 
1682     /**
1683      * Returns the signum function of this BigInteger.
1684      *
1685      * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
1686      *         positive.
1687      */
1688     public int signum() {
1689         return this.signum;
1690     }
1691 
1692     // Modular Arithmetic Operations
1693 
1694     /**
1695      * Returns a BigInteger whose value is {@code (this mod m}).  This method
1696      * differs from {@code remainder} in that it always returns a
1697      * <i>non-negative</i> BigInteger.
1698      *
1699      * @param  m the modulus.
1700      * @return {@code this mod m}
1701      * @throws ArithmeticException {@code m} &le; 0
1702      * @see    #remainder
1703      */
1704     public BigInteger mod(BigInteger m) {
1705         if (m.signum <= 0)
1706             throw new ArithmeticException("BigInteger: modulus not positive");
1707 
1708         BigInteger result = this.remainder(m);
1709         return (result.signum >= 0 ? result : result.add(m));
1710     }
1711 
1712     /**
1713      * Returns a BigInteger whose value is
1714      * <tt>(this<sup>exponent</sup> mod m)</tt>.  (Unlike {@code pow}, this
1715      * method permits negative exponents.)
1716      *
1717      * @param  exponent the exponent.
1718      * @param  m the modulus.
1719      * @return <tt>this<sup>exponent</sup> mod m</tt>
1720      * @throws ArithmeticException {@code m} &le; 0 or the exponent is
1721      *         negative and this BigInteger is not <i>relatively
1722      *         prime</i> to {@code m}.
1723      * @see    #modInverse
1724      */
1725     public BigInteger modPow(BigInteger exponent, BigInteger m) {
1726         if (m.signum <= 0)
1727             throw new ArithmeticException("BigInteger: modulus not positive");
1728 
1729         // Trivial cases
1730         if (exponent.signum == 0)
1731             return (m.equals(ONE) ? ZERO : ONE);
1732 
1733         if (this.equals(ONE))
1734             return (m.equals(ONE) ? ZERO : ONE);
1735 
1736         if (this.equals(ZERO) && exponent.signum >= 0)
1737             return ZERO;
1738 
1739         if (this.equals(negConst[1]) && (!exponent.testBit(0)))
1740             return (m.equals(ONE) ? ZERO : ONE);
1741 
1742         boolean invertResult;
1743         if ((invertResult = (exponent.signum < 0)))
1744             exponent = exponent.negate();
1745 
1746         BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
1747                            ? this.mod(m) : this);
1748         BigInteger result;
1749         if (m.testBit(0)) { // odd modulus
1750             result = base.oddModPow(exponent, m);
1751         } else {
1752             /*
1753              * Even modulus.  Tear it into an "odd part" (m1) and power of two
1754              * (m2), exponentiate mod m1, manually exponentiate mod m2, and
1755              * use Chinese Remainder Theorem to combine results.
1756              */
1757 
1758             // Tear m apart into odd part (m1) and power of 2 (m2)
1759             int p = m.getLowestSetBit();   // Max pow of 2 that divides m
1760 
1761             BigInteger m1 = m.shiftRight(p);  // m/2**p
1762             BigInteger m2 = ONE.shiftLeft(p); // 2**p
1763 
1764             // Calculate new base from m1
1765             BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
1766                                 ? this.mod(m1) : this);
1767 
1768             // Caculate (base ** exponent) mod m1.
1769             BigInteger a1 = (m1.equals(ONE) ? ZERO :
1770                              base2.oddModPow(exponent, m1));
1771 
1772             // Calculate (this ** exponent) mod m2
1773             BigInteger a2 = base.modPow2(exponent, p);
1774 
1775             // Combine results using Chinese Remainder Theorem
1776             BigInteger y1 = m2.modInverse(m1);
1777             BigInteger y2 = m1.modInverse(m2);
1778 
1779             result = a1.multiply(m2).multiply(y1).add
1780                      (a2.multiply(m1).multiply(y2)).mod(m);
1781         }
1782 
1783         return (invertResult ? result.modInverse(m) : result);
1784     }
1785 
1786     static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793,
1787                                                 Integer.MAX_VALUE}; // Sentinel
1788 
1789     /**
1790      * Returns a BigInteger whose value is x to the power of y mod z.
1791      * Assumes: z is odd && x < z.
1792      */
1793     private BigInteger oddModPow(BigInteger y, BigInteger z) {
1794     /*
1795      * The algorithm is adapted from Colin Plumb's C library.
1796      *
1797      * The window algorithm:
1798      * The idea is to keep a running product of b1 = n^(high-order bits of exp)
1799      * and then keep appending exponent bits to it.  The following patterns
1800      * apply to a 3-bit window (k = 3):
1801      * To append   0: square
1802      * To append   1: square, multiply by n^1
1803      * To append  10: square, multiply by n^1, square
1804      * To append  11: square, square, multiply by n^3
1805      * To append 100: square, multiply by n^1, square, square
1806      * To append 101: square, square, square, multiply by n^5
1807      * To append 110: square, square, multiply by n^3, square
1808      * To append 111: square, square, square, multiply by n^7
1809      *
1810      * Since each pattern involves only one multiply, the longer the pattern
1811      * the better, except that a 0 (no multiplies) can be appended directly.
1812      * We precompute a table of odd powers of n, up to 2^k, and can then
1813      * multiply k bits of exponent at a time.  Actually, assuming random
1814      * exponents, there is on average one zero bit between needs to
1815      * multiply (1/2 of the time there's none, 1/4 of the time there's 1,
1816      * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so
1817      * you have to do one multiply per k+1 bits of exponent.
1818      *
1819      * The loop walks down the exponent, squaring the result buffer as
1820      * it goes.  There is a wbits+1 bit lookahead buffer, buf, that is
1821      * filled with the upcoming exponent bits.  (What is read after the
1822      * end of the exponent is unimportant, but it is filled with zero here.)
1823      * When the most-significant bit of this buffer becomes set, i.e.
1824      * (buf & tblmask) != 0, we have to decide what pattern to multiply
1825      * by, and when to do it.  We decide, remember to do it in future
1826      * after a suitable number of squarings have passed (e.g. a pattern
1827      * of "100" in the buffer requires that we multiply by n^1 immediately;
1828      * a pattern of "110" calls for multiplying by n^3 after one more
1829      * squaring), clear the buffer, and continue.
1830      *
1831      * When we start, there is one more optimization: the result buffer
1832      * is implcitly one, so squaring it or multiplying by it can be
1833      * optimized away.  Further, if we start with a pattern like "100"
1834      * in the lookahead window, rather than placing n into the buffer
1835      * and then starting to square it, we have already computed n^2
1836      * to compute the odd-powers table, so we can place that into
1837      * the buffer and save a squaring.
1838      *
1839      * This means that if you have a k-bit window, to compute n^z,
1840      * where z is the high k bits of the exponent, 1/2 of the time
1841      * it requires no squarings.  1/4 of the time, it requires 1
1842      * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
1843      * And the remaining 1/2^(k-1) of the time, the top k bits are a
1844      * 1 followed by k-1 0 bits, so it again only requires k-2
1845      * squarings, not k-1.  The average of these is 1.  Add that
1846      * to the one squaring we have to do to compute the table,
1847      * and you'll see that a k-bit window saves k-2 squarings
1848      * as well as reducing the multiplies.  (It actually doesn't
1849      * hurt in the case k = 1, either.)
1850      */
1851         // Special case for exponent of one
1852         if (y.equals(ONE))
1853             return this;
1854 
1855         // Special case for base of zero
1856         if (signum==0)
1857             return ZERO;
1858 
1859         int[] base = mag.clone();
1860         int[] exp = y.mag;
1861         int[] mod = z.mag;
1862         int modLen = mod.length;
1863 
1864         // Select an appropriate window size
1865         int wbits = 0;
1866         int ebits = bitLength(exp, exp.length);
1867         // if exponent is 65537 (0x10001), use minimum window size
1868         if ((ebits != 17) || (exp[0] != 65537)) {
1869             while (ebits > bnExpModThreshTable[wbits]) {
1870                 wbits++;
1871             }
1872         }
1873 
1874         // Calculate appropriate table size
1875         int tblmask = 1 << wbits;
1876 
1877         // Allocate table for precomputed odd powers of base in Montgomery form
1878         int[][] table = new int[tblmask][];
1879         for (int i=0; i<tblmask; i++)
1880             table[i] = new int[modLen];
1881 
1882         // Compute the modular inverse
1883         int inv = -MutableBigInteger.inverseMod32(mod[modLen-1]);
1884 
1885         // Convert base to Montgomery form
1886         int[] a = leftShift(base, base.length, modLen << 5);
1887 
1888         MutableBigInteger q = new MutableBigInteger(),
1889                           a2 = new MutableBigInteger(a),
1890                           b2 = new MutableBigInteger(mod);
1891 
1892         MutableBigInteger r= a2.divide(b2, q);
1893         table[0] = r.toIntArray();
1894 
1895         // Pad table[0] with leading zeros so its length is at least modLen
1896         if (table[0].length < modLen) {
1897            int offset = modLen - table[0].length;
1898            int[] t2 = new int[modLen];
1899            for (int i=0; i<table[0].length; i++)
1900                t2[i+offset] = table[0][i];
1901            table[0] = t2;
1902         }
1903 
1904         // Set b to the square of the base
1905         int[] b = squareToLen(table[0], modLen, null);
1906         b = montReduce(b, mod, modLen, inv);
1907 
1908         // Set t to high half of b
1909         int[] t = Arrays.copyOf(b, modLen);
1910 
1911         // Fill in the table with odd powers of the base
1912         for (int i=1; i<tblmask; i++) {
1913             int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null);
1914             table[i] = montReduce(prod, mod, modLen, inv);
1915         }
1916 
1917         // Pre load the window that slides over the exponent
1918         int bitpos = 1 << ((ebits-1) & (32-1));
1919 
1920         int buf = 0;
1921         int elen = exp.length;
1922         int eIndex = 0;
1923         for (int i = 0; i <= wbits; i++) {
1924             buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0)?1:0);
1925             bitpos >>>= 1;
1926             if (bitpos == 0) {
1927                 eIndex++;
1928                 bitpos = 1 << (32-1);
1929                 elen--;
1930             }
1931         }
1932 
1933         int multpos = ebits;
1934 
1935         // The first iteration, which is hoisted out of the main loop
1936         ebits--;
1937         boolean isone = true;
1938 
1939         multpos = ebits - wbits;
1940         while ((buf & 1) == 0) {
1941             buf >>>= 1;
1942             multpos++;
1943         }
1944 
1945         int[] mult = table[buf >>> 1];
1946 
1947         buf = 0;
1948         if (multpos == ebits)
1949             isone = false;
1950 
1951         // The main loop
1952         while(true) {
1953             ebits--;
1954             // Advance the window
1955             buf <<= 1;
1956 
1957             if (elen != 0) {
1958                 buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0;
1959                 bitpos >>>= 1;
1960                 if (bitpos == 0) {
1961                     eIndex++;
1962                     bitpos = 1 << (32-1);
1963                     elen--;
1964                 }
1965             }
1966 
1967             // Examine the window for pending multiplies
1968             if ((buf & tblmask) != 0) {
1969                 multpos = ebits - wbits;
1970                 while ((buf & 1) == 0) {
1971                     buf >>>= 1;
1972                     multpos++;
1973                 }
1974                 mult = table[buf >>> 1];
1975                 buf = 0;
1976             }
1977 
1978             // Perform multiply
1979             if (ebits == multpos) {
1980                 if (isone) {
1981                     b = mult.clone();
1982                     isone = false;
1983                 } else {
1984                     t = b;
1985                     a = multiplyToLen(t, modLen, mult, modLen, a);
1986                     a = montReduce(a, mod, modLen, inv);
1987                     t = a; a = b; b = t;
1988                 }
1989             }
1990 
1991             // Check if done
1992             if (ebits == 0)
1993                 break;
1994 
1995             // Square the input
1996             if (!isone) {
1997                 t = b;
1998                 a = squareToLen(t, modLen, a);
1999                 a = montReduce(a, mod, modLen, inv);
2000                 t = a; a = b; b = t;
2001             }
2002         }
2003 
2004         // Convert result out of Montgomery form and return
2005         int[] t2 = new int[2*modLen];
2006         System.arraycopy(b, 0, t2, modLen, modLen);
2007 
2008         b = montReduce(t2, mod, modLen, inv);
2009 
2010         t2 = Arrays.copyOf(b, modLen);
2011 
2012         return new BigInteger(1, t2);
2013     }
2014 
2015     /**
2016      * Montgomery reduce n, modulo mod.  This reduces modulo mod and divides
2017      * by 2^(32*mlen). Adapted from Colin Plumb's C library.
2018      */
2019     private static int[] montReduce(int[] n, int[] mod, int mlen, int inv) {
2020         int c=0;
2021         int len = mlen;
2022         int offset=0;
2023 
2024         do {
2025             int nEnd = n[n.length-1-offset];
2026             int carry = mulAdd(n, mod, offset, mlen, inv * nEnd);
2027             c += addOne(n, offset, mlen, carry);
2028             offset++;
2029         } while(--len > 0);
2030 
2031         while(c>0)
2032             c += subN(n, mod, mlen);
2033 
2034         while (intArrayCmpToLen(n, mod, mlen) >= 0)
2035             subN(n, mod, mlen);
2036 
2037         return n;
2038     }
2039 
2040 
2041     /*
2042      * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than,
2043      * equal to, or greater than arg2 up to length len.
2044      */
2045     private static int intArrayCmpToLen(int[] arg1, int[] arg2, int len) {
2046         for (int i=0; i<len; i++) {
2047             long b1 = arg1[i] & LONG_MASK;
2048             long b2 = arg2[i] & LONG_MASK;
2049             if (b1 < b2)
2050                 return -1;
2051             if (b1 > b2)
2052                 return 1;
2053         }
2054         return 0;
2055     }
2056 
2057     /**
2058      * Subtracts two numbers of same length, returning borrow.
2059      */
2060     private static int subN(int[] a, int[] b, int len) {
2061         long sum = 0;
2062 
2063         while(--len >= 0) {
2064             sum = (a[len] & LONG_MASK) -
2065                  (b[len] & LONG_MASK) + (sum >> 32);
2066             a[len] = (int)sum;
2067         }
2068 
2069         return (int)(sum >> 32);
2070     }
2071 
2072     /**
2073      * Multiply an array by one word k and add to result, return the carry
2074      */
2075     static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
2076         long kLong = k & LONG_MASK;
2077         long carry = 0;
2078 
2079         offset = out.length-offset - 1;
2080         for (int j=len-1; j >= 0; j--) {
2081             long product = (in[j] & LONG_MASK) * kLong +
2082                            (out[offset] & LONG_MASK) + carry;
2083             out[offset--] = (int)product;
2084             carry = product >>> 32;
2085         }
2086         return (int)carry;
2087     }
2088 
2089     /**
2090      * Add one word to the number a mlen words into a. Return the resulting
2091      * carry.
2092      */
2093     static int addOne(int[] a, int offset, int mlen, int carry) {
2094         offset = a.length-1-mlen-offset;
2095         long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
2096 
2097         a[offset] = (int)t;
2098         if ((t >>> 32) == 0)
2099             return 0;
2100         while (--mlen >= 0) {
2101             if (--offset < 0) { // Carry out of number
2102                 return 1;
2103             } else {
2104                 a[offset]++;
2105                 if (a[offset] != 0)
2106                     return 0;
2107             }
2108         }
2109         return 1;
2110     }
2111 
2112     /**
2113      * Returns a BigInteger whose value is (this ** exponent) mod (2**p)
2114      */
2115     private BigInteger modPow2(BigInteger exponent, int p) {
2116         /*
2117          * Perform exponentiation using repeated squaring trick, chopping off
2118          * high order bits as indicated by modulus.
2119          */
2120         BigInteger result = valueOf(1);
2121         BigInteger baseToPow2 = this.mod2(p);
2122         int expOffset = 0;
2123 
2124         int limit = exponent.bitLength();
2125 
2126         if (this.testBit(0))
2127            limit = (p-1) < limit ? (p-1) : limit;
2128 
2129         while (expOffset < limit) {
2130             if (exponent.testBit(expOffset))
2131                 result = result.multiply(baseToPow2).mod2(p);
2132             expOffset++;
2133             if (expOffset < limit)
2134                 baseToPow2 = baseToPow2.square().mod2(p);
2135         }
2136 
2137         return result;
2138     }
2139 
2140     /**
2141      * Returns a BigInteger whose value is this mod(2**p).
2142      * Assumes that this {@code BigInteger >= 0} and {@code p > 0}.
2143      */
2144     private BigInteger mod2(int p) {
2145         if (bitLength() <= p)
2146             return this;
2147 
2148         // Copy remaining ints of mag
2149         int numInts = (p + 31) >>> 5;
2150         int[] mag = new int[numInts];
2151         System.arraycopy(this.mag, (this.mag.length - numInts), mag, 0, numInts);
2152 
2153         // Mask out any excess bits
2154         int excessBits = (numInts << 5) - p;
2155         mag[0] &= (1L << (32-excessBits)) - 1;
2156 
2157         return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
2158     }
2159 
2160     /**
2161      * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
2162      *
2163      * @param  m the modulus.
2164      * @return {@code this}<sup>-1</sup> {@code mod m}.
2165      * @throws ArithmeticException {@code  m} &le; 0, or this BigInteger
2166      *         has no multiplicative inverse mod m (that is, this BigInteger
2167      *         is not <i>relatively prime</i> to m).
2168      */
2169     public BigInteger modInverse(BigInteger m) {
2170         if (m.signum != 1)
2171             throw new ArithmeticException("BigInteger: modulus not positive");
2172 
2173         if (m.equals(ONE))
2174             return ZERO;
2175 
2176         // Calculate (this mod m)
2177         BigInteger modVal = this;
2178         if (signum < 0 || (this.compareMagnitude(m) >= 0))
2179             modVal = this.mod(m);
2180 
2181         if (modVal.equals(ONE))
2182             return ONE;
2183 
2184         MutableBigInteger a = new MutableBigInteger(modVal);
2185         MutableBigInteger b = new MutableBigInteger(m);
2186 
2187         MutableBigInteger result = a.mutableModInverse(b);
2188         return result.toBigInteger(1);
2189     }
2190 
2191     // Shift Operations
2192 
2193     /**
2194      * Returns a BigInteger whose value is {@code (this << n)}.
2195      * The shift distance, {@code n}, may be negative, in which case
2196      * this method performs a right shift.
2197      * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
2198      *
2199      * @param  n shift distance, in bits.
2200      * @return {@code this << n}
2201      * @throws ArithmeticException if the shift distance is {@code
2202      *         Integer.MIN_VALUE}.
2203      * @see #shiftRight
2204      */
2205     public BigInteger shiftLeft(int n) {
2206         if (signum == 0)
2207             return ZERO;
2208         if (n==0)
2209             return this;
2210         if (n<0) {
2211             if (n == Integer.MIN_VALUE) {
2212                 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2213             } else {
2214                 return shiftRight(-n);
2215             }
2216         }
2217         int[] newMag = shiftLeft(mag, n);
2218 
2219         return new BigInteger(newMag, signum);
2220     }
2221 
2222     private static int[] shiftLeft(int[] mag, int n) {
2223         int nInts = n >>> 5;
2224         int nBits = n & 0x1f;
2225         int magLen = mag.length;
2226         int newMag[] = null;
2227 
2228         if (nBits == 0) {
2229             newMag = new int[magLen + nInts];
2230             System.arraycopy(mag, 0, newMag, 0, magLen);
2231         } else {
2232             int i = 0;
2233             int nBits2 = 32 - nBits;
2234             int highBits = mag[0] >>> nBits2;
2235             if (highBits != 0) {
2236                 newMag = new int[magLen + nInts + 1];
2237                 newMag[i++] = highBits;
2238             } else {
2239                 newMag = new int[magLen + nInts];
2240             }
2241             int j=0;
2242             while (j < magLen-1)
2243                 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
2244             newMag[i] = mag[j] << nBits;
2245         }
2246         return newMag;
2247     }
2248 
2249     /**
2250      * Returns a BigInteger whose value is {@code (this >> n)}.  Sign
2251      * extension is performed.  The shift distance, {@code n}, may be
2252      * negative, in which case this method performs a left shift.
2253      * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.)
2254      *
2255      * @param  n shift distance, in bits.
2256      * @return {@code this >> n}
2257      * @throws ArithmeticException if the shift distance is {@code
2258      *         Integer.MIN_VALUE}.
2259      * @see #shiftLeft
2260      */
2261     public BigInteger shiftRight(int n) {
2262         if (n==0)
2263             return this;
2264         if (n<0) {
2265             if (n == Integer.MIN_VALUE) {
2266                 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
2267             } else {
2268                 return shiftLeft(-n);
2269             }
2270         }
2271 
2272         int nInts = n >>> 5;
2273         int nBits = n & 0x1f;
2274         int magLen = mag.length;
2275         int newMag[] = null;
2276 
2277         // Special case: entire contents shifted off the end
2278         if (nInts >= magLen)
2279             return (signum >= 0 ? ZERO : negConst[1]);
2280 
2281         if (nBits == 0) {
2282             int newMagLen = magLen - nInts;
2283             newMag = Arrays.copyOf(mag, newMagLen);
2284         } else {
2285             int i = 0;
2286             int highBits = mag[0] >>> nBits;
2287             if (highBits != 0) {
2288                 newMag = new int[magLen - nInts];
2289                 newMag[i++] = highBits;
2290             } else {
2291                 newMag = new int[magLen - nInts -1];
2292             }
2293 
2294             int nBits2 = 32 - nBits;
2295             int j=0;
2296             while (j < magLen - nInts - 1)
2297                 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
2298         }
2299 
2300         if (signum < 0) {
2301             // Find out whether any one-bits were shifted off the end.
2302             boolean onesLost = false;
2303             for (int i=magLen-1, j=magLen-nInts; i>=j && !onesLost; i--)
2304                 onesLost = (mag[i] != 0);
2305             if (!onesLost && nBits != 0)
2306                 onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0);
2307 
2308             if (onesLost)
2309                 newMag = javaIncrement(newMag);
2310         }
2311 
2312         return new BigInteger(newMag, signum);
2313     }
2314 
2315     int[] javaIncrement(int[] val) {
2316         int lastSum = 0;
2317         for (int i=val.length-1;  i >= 0 && lastSum == 0; i--)
2318             lastSum = (val[i] += 1);
2319         if (lastSum == 0) {
2320             val = new int[val.length+1];
2321             val[0] = 1;
2322         }
2323         return val;
2324     }
2325 
2326     // Bitwise Operations
2327 
2328     /**
2329      * Returns a BigInteger whose value is {@code (this & val)}.  (This
2330      * method returns a negative BigInteger if and only if this and val are
2331      * both negative.)
2332      *
2333      * @param val value to be AND'ed with this BigInteger.
2334      * @return {@code this & val}
2335      */
2336     public BigInteger and(BigInteger val) {
2337         int[] result = new int[Math.max(intLength(), val.intLength())];
2338         for (int i=0; i<result.length; i++)
2339             result[i] = (getInt(result.length-i-1)
2340                          & val.getInt(result.length-i-1));
2341 
2342         return valueOf(result);
2343     }
2344 
2345     /**
2346      * Returns a BigInteger whose value is {@code (this | val)}.  (This method
2347      * returns a negative BigInteger if and only if either this or val is
2348      * negative.)
2349      *
2350      * @param val value to be OR'ed with this BigInteger.
2351      * @return {@code this | val}
2352      */
2353     public BigInteger or(BigInteger val) {
2354         int[] result = new int[Math.max(intLength(), val.intLength())];
2355         for (int i=0; i<result.length; i++)
2356             result[i] = (getInt(result.length-i-1)
2357                          | val.getInt(result.length-i-1));
2358 
2359         return valueOf(result);
2360     }
2361 
2362     /**
2363      * Returns a BigInteger whose value is {@code (this ^ val)}.  (This method
2364      * returns a negative BigInteger if and only if exactly one of this and
2365      * val are negative.)
2366      *
2367      * @param val value to be XOR'ed with this BigInteger.
2368      * @return {@code this ^ val}
2369      */
2370     public BigInteger xor(BigInteger val) {
2371         int[] result = new int[Math.max(intLength(), val.intLength())];
2372         for (int i=0; i<result.length; i++)
2373             result[i] = (getInt(result.length-i-1)
2374                          ^ val.getInt(result.length-i-1));
2375 
2376         return valueOf(result);
2377     }
2378 
2379     /**
2380      * Returns a BigInteger whose value is {@code (~this)}.  (This method
2381      * returns a negative value if and only if this BigInteger is
2382      * non-negative.)
2383      *
2384      * @return {@code ~this}
2385      */
2386     public BigInteger not() {
2387         int[] result = new int[intLength()];
2388         for (int i=0; i<result.length; i++)
2389             result[i] = ~getInt(result.length-i-1);
2390 
2391         return valueOf(result);
2392     }
2393 
2394     /**
2395      * Returns a BigInteger whose value is {@code (this & ~val)}.  This
2396      * method, which is equivalent to {@code and(val.not())}, is provided as
2397      * a convenience for masking operations.  (This method returns a negative
2398      * BigInteger if and only if {@code this} is negative and {@code val} is
2399      * positive.)
2400      *
2401      * @param val value to be complemented and AND'ed with this BigInteger.
2402      * @return {@code this & ~val}
2403      */
2404     public BigInteger andNot(BigInteger val) {
2405         int[] result = new int[Math.max(intLength(), val.intLength())];
2406         for (int i=0; i<result.length; i++)
2407             result[i] = (getInt(result.length-i-1)
2408                          & ~val.getInt(result.length-i-1));
2409 
2410         return valueOf(result);
2411     }
2412 
2413 
2414     // Single Bit Operations
2415 
2416     /**
2417      * Returns {@code true} if and only if the designated bit is set.
2418      * (Computes {@code ((this & (1<<n)) != 0)}.)
2419      *
2420      * @param  n index of bit to test.
2421      * @return {@code true} if and only if the designated bit is set.
2422      * @throws ArithmeticException {@code n} is negative.
2423      */
2424     public boolean testBit(int n) {
2425         if (n<0)
2426             throw new ArithmeticException("Negative bit address");
2427 
2428         return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
2429     }
2430 
2431     /**
2432      * Returns a BigInteger whose value is equivalent to this BigInteger
2433      * with the designated bit set.  (Computes {@code (this | (1<<n))}.)
2434      *
2435      * @param  n index of bit to set.
2436      * @return {@code this | (1<<n)}
2437      * @throws ArithmeticException {@code n} is negative.
2438      */
2439     public BigInteger setBit(int n) {
2440         if (n<0)
2441             throw new ArithmeticException("Negative bit address");
2442 
2443         int intNum = n >>> 5;
2444         int[] result = new int[Math.max(intLength(), intNum+2)];
2445 
2446         for (int i=0; i<result.length; i++)
2447             result[result.length-i-1] = getInt(i);
2448 
2449         result[result.length-intNum-1] |= (1 << (n & 31));
2450 
2451         return valueOf(result);
2452     }
2453 
2454     /**
2455      * Returns a BigInteger whose value is equivalent to this BigInteger
2456      * with the designated bit cleared.
2457      * (Computes {@code (this & ~(1<<n))}.)
2458      *
2459      * @param  n index of bit to clear.
2460      * @return {@code this & ~(1<<n)}
2461      * @throws ArithmeticException {@code n} is negative.
2462      */
2463     public BigInteger clearBit(int n) {
2464         if (n<0)
2465             throw new ArithmeticException("Negative bit address");
2466 
2467         int intNum = n >>> 5;
2468         int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)];
2469 
2470         for (int i=0; i<result.length; i++)
2471             result[result.length-i-1] = getInt(i);
2472 
2473         result[result.length-intNum-1] &= ~(1 << (n & 31));
2474 
2475         return valueOf(result);
2476     }
2477 
2478     /**
2479      * Returns a BigInteger whose value is equivalent to this BigInteger
2480      * with the designated bit flipped.
2481      * (Computes {@code (this ^ (1<<n))}.)
2482      *
2483      * @param  n index of bit to flip.
2484      * @return {@code this ^ (1<<n)}
2485      * @throws ArithmeticException {@code n} is negative.
2486      */
2487     public BigInteger flipBit(int n) {
2488         if (n<0)
2489             throw new ArithmeticException("Negative bit address");
2490 
2491         int intNum = n >>> 5;
2492         int[] result = new int[Math.max(intLength(), intNum+2)];
2493 
2494         for (int i=0; i<result.length; i++)
2495             result[result.length-i-1] = getInt(i);
2496 
2497         result[result.length-intNum-1] ^= (1 << (n & 31));
2498 
2499         return valueOf(result);
2500     }
2501 
2502     /**
2503      * Returns the index of the rightmost (lowest-order) one bit in this
2504      * BigInteger (the number of zero bits to the right of the rightmost
2505      * one bit).  Returns -1 if this BigInteger contains no one bits.
2506      * (Computes {@code (this==0? -1 : log2(this & -this))}.)
2507      *
2508      * @return index of the rightmost one bit in this BigInteger.
2509      */
2510     public int getLowestSetBit() {
2511         @SuppressWarnings("deprecation") int lsb = lowestSetBit - 2;
2512         if (lsb == -2) {  // lowestSetBit not initialized yet
2513             lsb = 0;
2514             if (signum == 0) {
2515                 lsb -= 1;
2516             } else {
2517                 // Search for lowest order nonzero int
2518                 int i,b;
2519                 for (i=0; (b = getInt(i))==0; i++)
2520                     ;
2521                 lsb += (i << 5) + Integer.numberOfTrailingZeros(b);
2522             }
2523             lowestSetBit = lsb + 2;
2524         }
2525         return lsb;
2526     }
2527 
2528 
2529     // Miscellaneous Bit Operations
2530 
2531     /**
2532      * Returns the number of bits in the minimal two's-complement
2533      * representation of this BigInteger, <i>excluding</i> a sign bit.
2534      * For positive BigIntegers, this is equivalent to the number of bits in
2535      * the ordinary binary representation.  (Computes
2536      * {@code (ceil(log2(this < 0 ? -this : this+1)))}.)
2537      *
2538      * @return number of bits in the minimal two's-complement
2539      *         representation of this BigInteger, <i>excluding</i> a sign bit.
2540      */
2541     public int bitLength() {
2542         @SuppressWarnings("deprecation") int n = bitLength - 1;
2543         if (n == -1) { // bitLength not initialized yet
2544             int[] m = mag;
2545             int len = m.length;
2546             if (len == 0) {
2547                 n = 0; // offset by one to initialize
2548             }  else {
2549                 // Calculate the bit length of the magnitude
2550                 int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]);
2551                  if (signum < 0) {
2552                      // Check if magnitude is a power of two
2553                      boolean pow2 = (Integer.bitCount(mag[0]) == 1);
2554                      for (int i=1; i< len && pow2; i++)
2555                          pow2 = (mag[i] == 0);
2556 
2557                      n = (pow2 ? magBitLength -1 : magBitLength);
2558                  } else {
2559                      n = magBitLength;
2560                  }
2561             }
2562             bitLength = n + 1;
2563         }
2564         return n;
2565     }
2566 
2567     /**
2568      * Returns the number of bits in the two's complement representation
2569      * of this BigInteger that differ from its sign bit.  This method is
2570      * useful when implementing bit-vector style sets atop BigIntegers.
2571      *
2572      * @return number of bits in the two's complement representation
2573      *         of this BigInteger that differ from its sign bit.
2574      */
2575     public int bitCount() {
2576         @SuppressWarnings("deprecation") int bc = bitCount - 1;
2577         if (bc == -1) {  // bitCount not initialized yet
2578             bc = 0;      // offset by one to initialize
2579             // Count the bits in the magnitude
2580             for (int i=0; i<mag.length; i++)
2581                 bc += Integer.bitCount(mag[i]);
2582             if (signum < 0) {
2583                 // Count the trailing zeros in the magnitude
2584                 int magTrailingZeroCount = 0, j;
2585                 for (j=mag.length-1; mag[j]==0; j--)
2586                     magTrailingZeroCount += 32;
2587                 magTrailingZeroCount += Integer.numberOfTrailingZeros(mag[j]);
2588                 bc += magTrailingZeroCount - 1;
2589             }
2590             bitCount = bc + 1;
2591         }
2592         return bc;
2593     }
2594 
2595     // Primality Testing
2596 
2597     /**
2598      * Returns {@code true} if this BigInteger is probably prime,
2599      * {@code false} if it's definitely composite.  If
2600      * {@code certainty} is &le; 0, {@code true} is
2601      * returned.
2602      *
2603      * @param  certainty a measure of the uncertainty that the caller is
2604      *         willing to tolerate: if the call returns {@code true}
2605      *         the probability that this BigInteger is prime exceeds
2606      *         (1 - 1/2<sup>{@code certainty}</sup>).  The execution time of
2607      *         this method is proportional to the value of this parameter.
2608      * @return {@code true} if this BigInteger is probably prime,
2609      *         {@code false} if it's definitely composite.
2610      */
2611     public boolean isProbablePrime(int certainty) {
2612         if (certainty <= 0)
2613             return true;
2614         BigInteger w = this.abs();
2615         if (w.equals(TWO))
2616             return true;
2617         if (!w.testBit(0) || w.equals(ONE))
2618             return false;
2619 
2620         return w.primeToCertainty(certainty, null);
2621     }
2622 
2623     // Comparison Operations
2624 
2625     /**
2626      * Compares this BigInteger with the specified BigInteger.  This
2627      * method is provided in preference to individual methods for each
2628      * of the six boolean comparison operators ({@literal <}, ==,
2629      * {@literal >}, {@literal >=}, !=, {@literal <=}).  The suggested
2630      * idiom for performing these comparisons is: {@code
2631      * (x.compareTo(y)} &lt;<i>op</i>&gt; {@code 0)}, where
2632      * &lt;<i>op</i>&gt; is one of the six comparison operators.
2633      *
2634      * @param  val BigInteger to which this BigInteger is to be compared.
2635      * @return -1, 0 or 1 as this BigInteger is numerically less than, equal
2636      *         to, or greater than {@code val}.
2637      */
2638     public int compareTo(BigInteger val) {
2639         if (signum == val.signum) {
2640             switch (signum) {
2641             case 1:
2642                 return compareMagnitude(val);
2643             case -1:
2644                 return val.compareMagnitude(this);
2645             default:
2646                 return 0;
2647             }
2648         }
2649         return signum > val.signum ? 1 : -1;
2650     }
2651 
2652     /**
2653      * Compares the magnitude array of this BigInteger with the specified
2654      * BigInteger's. This is the version of compareTo ignoring sign.
2655      *
2656      * @param val BigInteger whose magnitude array to be compared.
2657      * @return -1, 0 or 1 as this magnitude array is less than, equal to or
2658      *         greater than the magnitude aray for the specified BigInteger's.
2659      */
2660     final int compareMagnitude(BigInteger val) {
2661         int[] m1 = mag;
2662         int len1 = m1.length;
2663         int[] m2 = val.mag;
2664         int len2 = m2.length;
2665         if (len1 < len2)
2666             return -1;
2667         if (len1 > len2)
2668             return 1;
2669         for (int i = 0; i < len1; i++) {
2670             int a = m1[i];
2671             int b = m2[i];
2672             if (a != b)
2673                 return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
2674         }
2675         return 0;
2676     }
2677 
2678     /**
2679      * Version of compareMagnitude that compares magnitude with long value.
2680      * val can't be Long.MIN_VALUE.
2681      */
2682     final int compareMagnitude(long val) {
2683         assert val != Long.MIN_VALUE;
2684         int[] m1 = mag;
2685         int len = m1.length;
2686         if(len > 2) {
2687             return 1;
2688         }
2689         if (val < 0) {
2690             val = -val;
2691         }
2692         int highWord = (int)(val >>> 32);
2693         if (highWord==0) {
2694             if (len < 1)
2695                 return -1;
2696             if (len > 1)
2697                 return 1;
2698             int a = m1[0];
2699             int b = (int)val;
2700             if (a != b) {
2701                 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1;
2702             }
2703             return 0;
2704         } else {
2705             if (len < 2)
2706                 return -1;
2707             int a = m1[0];
2708             int b = highWord;
2709             if (a != b) {
2710                 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1;
2711             }
2712             a = m1[1];
2713             b = (int)val;
2714             if (a != b) {
2715                 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1;
2716             }
2717             return 0;
2718         }
2719     }
2720 
2721     /**
2722      * Compares this BigInteger with the specified Object for equality.
2723      *
2724      * @param  x Object to which this BigInteger is to be compared.
2725      * @return {@code true} if and only if the specified Object is a
2726      *         BigInteger whose value is numerically equal to this BigInteger.
2727      */
2728     public boolean equals(Object x) {
2729         // This test is just an optimization, which may or may not help
2730         if (x == this)
2731             return true;
2732 
2733         if (!(x instanceof BigInteger))
2734             return false;
2735 
2736         BigInteger xInt = (BigInteger) x;
2737         if (xInt.signum != signum)
2738             return false;
2739 
2740         int[] m = mag;
2741         int len = m.length;
2742         int[] xm = xInt.mag;
2743         if (len != xm.length)
2744             return false;
2745 
2746         for (int i = 0; i < len; i++)
2747             if (xm[i] != m[i])
2748                 return false;
2749 
2750         return true;
2751     }
2752 
2753     /**
2754      * Returns the minimum of this BigInteger and {@code val}.
2755      *
2756      * @param  val value with which the minimum is to be computed.
2757      * @return the BigInteger whose value is the lesser of this BigInteger and
2758      *         {@code val}.  If they are equal, either may be returned.
2759      */
2760     public BigInteger min(BigInteger val) {
2761         return (compareTo(val)<0 ? this : val);
2762     }
2763 
2764     /**
2765      * Returns the maximum of this BigInteger and {@code val}.
2766      *
2767      * @param  val value with which the maximum is to be computed.
2768      * @return the BigInteger whose value is the greater of this and
2769      *         {@code val}.  If they are equal, either may be returned.
2770      */
2771     public BigInteger max(BigInteger val) {
2772         return (compareTo(val)>0 ? this : val);
2773     }
2774 
2775 
2776     // Hash Function
2777 
2778     /**
2779      * Returns the hash code for this BigInteger.
2780      *
2781      * @return hash code for this BigInteger.
2782      */
2783     public int hashCode() {
2784         int hashCode = 0;
2785 
2786         for (int i=0; i<mag.length; i++)
2787             hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK));
2788 
2789         return hashCode * signum;
2790     }
2791 
2792     /**
2793      * Returns the String representation of this BigInteger in the
2794      * given radix.  If the radix is outside the range from {@link
2795      * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
2796      * it will default to 10 (as is the case for
2797      * {@code Integer.toString}).  The digit-to-character mapping
2798      * provided by {@code Character.forDigit} is used, and a minus
2799      * sign is prepended if appropriate.  (This representation is
2800      * compatible with the {@link #BigInteger(String, int) (String,
2801      * int)} constructor.)
2802      *
2803      * @param  radix  radix of the String representation.
2804      * @return String representation of this BigInteger in the given radix.
2805      * @see    Integer#toString
2806      * @see    Character#forDigit
2807      * @see    #BigInteger(java.lang.String, int)
2808      */
2809     public String toString(int radix) {
2810         if (signum == 0)
2811             return "0";
2812         if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
2813             radix = 10;
2814 
2815         // Compute upper bound on number of digit groups and allocate space
2816         int maxNumDigitGroups = (4*mag.length + 6)/7;
2817         String digitGroup[] = new String[maxNumDigitGroups];
2818 
2819         // Translate number to string, a digit group at a time
2820         BigInteger tmp = this.abs();
2821         int numGroups = 0;
2822         while (tmp.signum != 0) {
2823             BigInteger d = longRadix[radix];
2824 
2825             MutableBigInteger q = new MutableBigInteger(),
2826                               a = new MutableBigInteger(tmp.mag),
2827                               b = new MutableBigInteger(d.mag);
2828             MutableBigInteger r = a.divide(b, q);
2829             BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
2830             BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
2831 
2832             digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
2833             tmp = q2;
2834         }
2835 
2836         // Put sign (if any) and first digit group into result buffer
2837         StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
2838         if (signum<0)
2839             buf.append('-');
2840         buf.append(digitGroup[numGroups-1]);
2841 
2842         // Append remaining digit groups padded with leading zeros
2843         for (int i=numGroups-2; i>=0; i--) {
2844             // Prepend (any) leading zeros for this digit group
2845             int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
2846             if (numLeadingZeros != 0)
2847                 buf.append(zeros[numLeadingZeros]);
2848             buf.append(digitGroup[i]);
2849         }
2850         return buf.toString();
2851     }
2852 
2853     /* zero[i] is a string of i consecutive zeros. */
2854     private static String zeros[] = new String[64];
2855     static {
2856         zeros[63] =
2857             "000000000000000000000000000000000000000000000000000000000000000";
2858         for (int i=0; i<63; i++)
2859             zeros[i] = zeros[63].substring(0, i);
2860     }
2861 
2862     /**
2863      * Returns the decimal String representation of this BigInteger.
2864      * The digit-to-character mapping provided by
2865      * {@code Character.forDigit} is used, and a minus sign is
2866      * prepended if appropriate.  (This representation is compatible
2867      * with the {@link #BigInteger(String) (String)} constructor, and
2868      * allows for String concatenation with Java's + operator.)
2869      *
2870      * @return decimal String representation of this BigInteger.
2871      * @see    Character#forDigit
2872      * @see    #BigInteger(java.lang.String)
2873      */
2874     public String toString() {
2875         return toString(10);
2876     }
2877 
2878     /**
2879      * Returns a byte array containing the two's-complement
2880      * representation of this BigInteger.  The byte array will be in
2881      * <i>big-endian</i> byte-order: the most significant byte is in
2882      * the zeroth element.  The array will contain the minimum number
2883      * of bytes required to represent this BigInteger, including at
2884      * least one sign bit, which is {@code (ceil((this.bitLength() +
2885      * 1)/8))}.  (This representation is compatible with the
2886      * {@link #BigInteger(byte[]) (byte[])} constructor.)
2887      *
2888      * @return a byte array containing the two's-complement representation of
2889      *         this BigInteger.
2890      * @see    #BigInteger(byte[])
2891      */
2892     public byte[] toByteArray() {
2893         int byteLen = bitLength()/8 + 1;
2894         byte[] byteArray = new byte[byteLen];
2895 
2896         for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i>=0; i--) {
2897             if (bytesCopied == 4) {
2898                 nextInt = getInt(intIndex++);
2899                 bytesCopied = 1;
2900             } else {
2901                 nextInt >>>= 8;
2902                 bytesCopied++;
2903             }
2904             byteArray[i] = (byte)nextInt;
2905         }
2906         return byteArray;
2907     }
2908 
2909     /**
2910      * Converts this BigInteger to an {@code int}.  This
2911      * conversion is analogous to a
2912      * <i>narrowing primitive conversion</i> from {@code long} to
2913      * {@code int} as defined in section 5.1.3 of
2914      * <cite>The Java&trade; Language Specification</cite>:
2915      * if this BigInteger is too big to fit in an
2916      * {@code int}, only the low-order 32 bits are returned.
2917      * Note that this conversion can lose information about the
2918      * overall magnitude of the BigInteger value as well as return a
2919      * result with the opposite sign.
2920      *
2921      * @return this BigInteger converted to an {@code int}.
2922      * @see #intValueExact()
2923      */
2924     public int intValue() {
2925         int result = 0;
2926         result = getInt(0);
2927         return result;
2928     }
2929 
2930     /**
2931      * Converts this BigInteger to a {@code long}.  This
2932      * conversion is analogous to a
2933      * <i>narrowing primitive conversion</i> from {@code long} to
2934      * {@code int} as defined in section 5.1.3 of
2935      * <cite>The Java&trade; Language Specification</cite>:
2936      * if this BigInteger is too big to fit in a
2937      * {@code long}, only the low-order 64 bits are returned.
2938      * Note that this conversion can lose information about the
2939      * overall magnitude of the BigInteger value as well as return a
2940      * result with the opposite sign.
2941      *
2942      * @return this BigInteger converted to a {@code long}.
2943      * @see #longValueExact()
2944      */
2945     public long longValue() {
2946         long result = 0;
2947 
2948         for (int i=1; i>=0; i--)
2949             result = (result << 32) + (getInt(i) & LONG_MASK);
2950         return result;
2951     }
2952 
2953     /**
2954      * Converts this BigInteger to a {@code float}.  This
2955      * conversion is similar to the
2956      * <i>narrowing primitive conversion</i> from {@code double} to
2957      * {@code float} as defined in section 5.1.3 of
2958      * <cite>The Java&trade; Language Specification</cite>:
2959      * if this BigInteger has too great a magnitude
2960      * to represent as a {@code float}, it will be converted to
2961      * {@link Float#NEGATIVE_INFINITY} or {@link
2962      * Float#POSITIVE_INFINITY} as appropriate.  Note that even when
2963      * the return value is finite, this conversion can lose
2964      * information about the precision of the BigInteger value.
2965      *
2966      * @return this BigInteger converted to a {@code float}.
2967      */
2968     public float floatValue() {
2969         // Somewhat inefficient, but guaranteed to work.
2970         return Float.parseFloat(this.toString());
2971     }
2972 
2973     /**
2974      * Converts this BigInteger to a {@code double}.  This
2975      * conversion is similar to the
2976      * <i>narrowing primitive conversion</i> from {@code double} to
2977      * {@code float} as defined in section 5.1.3 of
2978      * <cite>The Java&trade; Language Specification</cite>:
2979      * if this BigInteger has too great a magnitude
2980      * to represent as a {@code double}, it will be converted to
2981      * {@link Double#NEGATIVE_INFINITY} or {@link
2982      * Double#POSITIVE_INFINITY} as appropriate.  Note that even when
2983      * the return value is finite, this conversion can lose
2984      * information about the precision of the BigInteger value.
2985      *
2986      * @return this BigInteger converted to a {@code double}.
2987      */
2988     public double doubleValue() {
2989         // Somewhat inefficient, but guaranteed to work.
2990         return Double.parseDouble(this.toString());
2991     }
2992 
2993     /**
2994      * Returns a copy of the input array stripped of any leading zero bytes.
2995      */
2996     private static int[] stripLeadingZeroInts(int val[]) {
2997         int vlen = val.length;
2998         int keep;
2999 
3000         // Find first nonzero byte
3001         for (keep = 0; keep < vlen && val[keep] == 0; keep++)
3002             ;
3003         return java.util.Arrays.copyOfRange(val, keep, vlen);
3004     }
3005 
3006     /**
3007      * Returns the input array stripped of any leading zero bytes.
3008      * Since the source is trusted the copying may be skipped.
3009      */
3010     private static int[] trustedStripLeadingZeroInts(int val[]) {
3011         int vlen = val.length;
3012         int keep;
3013 
3014         // Find first nonzero byte
3015         for (keep = 0; keep < vlen && val[keep] == 0; keep++)
3016             ;
3017         return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
3018     }
3019 
3020     /**
3021      * Returns a copy of the input array stripped of any leading zero bytes.
3022      */
3023     private static int[] stripLeadingZeroBytes(byte a[]) {
3024         int byteLength = a.length;
3025         int keep;
3026 
3027         // Find first nonzero byte
3028         for (keep = 0; keep < byteLength && a[keep]==0; keep++)
3029             ;
3030 
3031         // Allocate new array and copy relevant part of input array
3032         int intLength = ((byteLength - keep) + 3) >>> 2;
3033         int[] result = new int[intLength];
3034         int b = byteLength - 1;
3035         for (int i = intLength-1; i >= 0; i--) {
3036             result[i] = a[b--] & 0xff;
3037             int bytesRemaining = b - keep + 1;
3038             int bytesToTransfer = Math.min(3, bytesRemaining);
3039             for (int j=8; j <= (bytesToTransfer << 3); j += 8)
3040                 result[i] |= ((a[b--] & 0xff) << j);
3041         }
3042         return result;
3043     }
3044 
3045     /**
3046      * Takes an array a representing a negative 2's-complement number and
3047      * returns the minimal (no leading zero bytes) unsigned whose value is -a.
3048      */
3049     private static int[] makePositive(byte a[]) {
3050         int keep, k;
3051         int byteLength = a.length;
3052 
3053         // Find first non-sign (0xff) byte of input
3054         for (keep=0; keep<byteLength && a[keep]==-1; keep++)
3055             ;
3056 
3057 
3058         /* Allocate output array.  If all non-sign bytes are 0x00, we must
3059          * allocate space for one extra output byte. */
3060         for (k=keep; k<byteLength && a[k]==0; k++)
3061             ;
3062 
3063         int extraByte = (k==byteLength) ? 1 : 0;
3064         int intLength = ((byteLength - keep + extraByte) + 3)/4;
3065         int result[] = new int[intLength];
3066 
3067         /* Copy one's complement of input into output, leaving extra
3068          * byte (if it exists) == 0x00 */
3069         int b = byteLength - 1;
3070         for (int i = intLength-1; i >= 0; i--) {
3071             result[i] = a[b--] & 0xff;
3072             int numBytesToTransfer = Math.min(3, b-keep+1);
3073             if (numBytesToTransfer < 0)
3074                 numBytesToTransfer = 0;
3075             for (int j=8; j <= 8*numBytesToTransfer; j += 8)
3076                 result[i] |= ((a[b--] & 0xff) << j);
3077 
3078             // Mask indicates which bits must be complemented
3079             int mask = -1 >>> (8*(3-numBytesToTransfer));
3080             result[i] = ~result[i] & mask;
3081         }
3082 
3083         // Add one to one's complement to generate two's complement
3084         for (int i=result.length-1; i>=0; i--) {
3085             result[i] = (int)((result[i] & LONG_MASK) + 1);
3086             if (result[i] != 0)
3087                 break;
3088         }
3089 
3090         return result;
3091     }
3092 
3093     /**
3094      * Takes an array a representing a negative 2's-complement number and
3095      * returns the minimal (no leading zero ints) unsigned whose value is -a.
3096      */
3097     private static int[] makePositive(int a[]) {
3098         int keep, j;
3099 
3100         // Find first non-sign (0xffffffff) int of input
3101         for (keep=0; keep<a.length && a[keep]==-1; keep++)
3102             ;
3103 
3104         /* Allocate output array.  If all non-sign ints are 0x00, we must
3105          * allocate space for one extra output int. */
3106         for (j=keep; j<a.length && a[j]==0; j++)
3107             ;
3108         int extraInt = (j==a.length ? 1 : 0);
3109         int result[] = new int[a.length - keep + extraInt];
3110 
3111         /* Copy one's complement of input into output, leaving extra
3112          * int (if it exists) == 0x00 */
3113         for (int i = keep; i<a.length; i++)
3114             result[i - keep + extraInt] = ~a[i];
3115 
3116         // Add one to one's complement to generate two's complement
3117         for (int i=result.length-1; ++result[i]==0; i--)
3118             ;
3119 
3120         return result;
3121     }
3122 
3123     /*
3124      * The following two arrays are used for fast String conversions.  Both
3125      * are indexed by radix.  The first is the number of digits of the given
3126      * radix that can fit in a Java long without "going negative", i.e., the
3127      * highest integer n such that radix**n < 2**63.  The second is the
3128      * "long radix" that tears each number into "long digits", each of which
3129      * consists of the number of digits in the corresponding element in
3130      * digitsPerLong (longRadix[i] = i**digitPerLong[i]).  Both arrays have
3131      * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
3132      * used.
3133      */
3134     private static int digitsPerLong[] = {0, 0,
3135         62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
3136         14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
3137 
3138     private static BigInteger longRadix[] = {null, null,
3139         valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
3140         valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
3141         valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
3142         valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
3143         valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
3144         valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
3145         valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
3146         valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
3147         valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
3148         valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
3149         valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
3150         valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
3151         valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
3152         valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
3153         valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
3154         valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
3155         valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
3156         valueOf(0x41c21cb8e1000000L)};
3157 
3158     /*
3159      * These two arrays are the integer analogue of above.
3160      */
3161     private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
3162         11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
3163         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
3164 
3165     private static int intRadix[] = {0, 0,
3166         0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
3167         0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
3168         0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f,  0x10000000,
3169         0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
3170         0x6c20a40,  0x8d2d931,  0xb640000,  0xe8d4a51,  0x1269ae40,
3171         0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
3172         0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
3173     };
3174 
3175     /**
3176      * These routines provide access to the two's complement representation
3177      * of BigIntegers.
3178      */
3179 
3180     /**
3181      * Returns the length of the two's complement representation in ints,
3182      * including space for at least one sign bit.
3183      */
3184     private int intLength() {
3185         return (bitLength() >>> 5) + 1;
3186     }
3187 
3188     /* Returns sign bit */
3189     private int signBit() {
3190         return signum < 0 ? 1 : 0;
3191     }
3192 
3193     /* Returns an int of sign bits */
3194     private int signInt() {
3195         return signum < 0 ? -1 : 0;
3196     }
3197 
3198     /**
3199      * Returns the specified int of the little-endian two's complement
3200      * representation (int 0 is the least significant).  The int number can
3201      * be arbitrarily high (values are logically preceded by infinitely many
3202      * sign ints).
3203      */
3204     private int getInt(int n) {
3205         if (n < 0)
3206             return 0;
3207         if (n >= mag.length)
3208             return signInt();
3209 
3210         int magInt = mag[mag.length-n-1];
3211 
3212         return (signum >= 0 ? magInt :
3213                 (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
3214     }
3215 
3216     /**
3217      * Returns the index of the int that contains the first nonzero int in the
3218      * little-endian binary representation of the magnitude (int 0 is the
3219      * least significant). If the magnitude is zero, return value is undefined.
3220      */
3221      private int firstNonzeroIntNum() {
3222          int fn = firstNonzeroIntNum - 2;
3223          if (fn == -2) { // firstNonzeroIntNum not initialized yet
3224              fn = 0;
3225 
3226              // Search for the first nonzero int
3227              int i;
3228              int mlen = mag.length;
3229              for (i = mlen - 1; i >= 0 && mag[i] == 0; i--)
3230                  ;
3231              fn = mlen - i - 1;
3232              firstNonzeroIntNum = fn + 2; // offset by two to initialize
3233          }
3234          return fn;
3235      }
3236 
3237     /** use serialVersionUID from JDK 1.1. for interoperability */
3238     private static final long serialVersionUID = -8287574255936472291L;
3239 
3240     /**
3241      * Serializable fields for BigInteger.
3242      *
3243      * @serialField signum  int
3244      *              signum of this BigInteger.
3245      * @serialField magnitude int[]
3246      *              magnitude array of this BigInteger.
3247      * @serialField bitCount  int
3248      *              number of bits in this BigInteger
3249      * @serialField bitLength int
3250      *              the number of bits in the minimal two's-complement
3251      *              representation of this BigInteger
3252      * @serialField lowestSetBit int
3253      *              lowest set bit in the twos complement representation
3254      */
3255     private static final ObjectStreamField[] serialPersistentFields = {
3256         new ObjectStreamField("signum", Integer.TYPE),
3257         new ObjectStreamField("magnitude", byte[].class),
3258         new ObjectStreamField("bitCount", Integer.TYPE),
3259         new ObjectStreamField("bitLength", Integer.TYPE),
3260         new ObjectStreamField("firstNonzeroByteNum", Integer.TYPE),
3261         new ObjectStreamField("lowestSetBit", Integer.TYPE)
3262         };
3263 
3264     /**
3265      * Reconstitute the {@code BigInteger} instance from a stream (that is,
3266      * deserialize it). The magnitude is read in as an array of bytes
3267      * for historical reasons, but it is converted to an array of ints
3268      * and the byte array is discarded.
3269      * Note:
3270      * The current convention is to initialize the cache fields, bitCount,
3271      * bitLength and lowestSetBit, to 0 rather than some other marker value.
3272      * Therefore, no explicit action to set these fields needs to be taken in
3273      * readObject because those fields already have a 0 value be default since
3274      * defaultReadObject is not being used.
3275      */
3276     private void readObject(java.io.ObjectInputStream s)
3277         throws java.io.IOException, ClassNotFoundException {
3278         /*
3279          * In order to maintain compatibility with previous serialized forms,
3280          * the magnitude of a BigInteger is serialized as an array of bytes.
3281          * The magnitude field is used as a temporary store for the byte array
3282          * that is deserialized. The cached computation fields should be
3283          * transient but are serialized for compatibility reasons.
3284          */
3285 
3286         // prepare to read the alternate persistent fields
3287         ObjectInputStream.GetField fields = s.readFields();
3288 
3289         // Read the alternate persistent fields that we care about
3290         int sign = fields.get("signum", -2);
3291         byte[] magnitude = (byte[])fields.get("magnitude", null);
3292 
3293         // Validate signum
3294         if (sign < -1 || sign > 1) {
3295             String message = "BigInteger: Invalid signum value";
3296             if (fields.defaulted("signum"))
3297                 message = "BigInteger: Signum not present in stream";
3298             throw new java.io.StreamCorruptedException(message);
3299         }
3300         if ((magnitude.length == 0) != (sign == 0)) {
3301             String message = "BigInteger: signum-magnitude mismatch";
3302             if (fields.defaulted("magnitude"))
3303                 message = "BigInteger: Magnitude not present in stream";
3304             throw new java.io.StreamCorruptedException(message);
3305         }
3306 
3307         // Commit final fields via Unsafe
3308         UnsafeHolder.putSign(this, sign);
3309 
3310         // Calculate mag field from magnitude and discard magnitude
3311         UnsafeHolder.putMag(this, stripLeadingZeroBytes(magnitude));
3312     }
3313 
3314     // Support for resetting final fields while deserializing
3315     private static class UnsafeHolder {
3316         private static final sun.misc.Unsafe unsafe;
3317         private static final long signumOffset;
3318         private static final long magOffset;
3319         static {
3320             try {
3321                 unsafe = sun.misc.Unsafe.getUnsafe();
3322                 signumOffset = unsafe.objectFieldOffset
3323                     (BigInteger.class.getDeclaredField("signum"));
3324                 magOffset = unsafe.objectFieldOffset
3325                     (BigInteger.class.getDeclaredField("mag"));
3326             } catch (Exception ex) {
3327                 throw new ExceptionInInitializerError(ex);
3328             }
3329         }
3330 
3331         static void putSign(BigInteger bi, int sign) {
3332             unsafe.putIntVolatile(bi, signumOffset, sign);
3333         }
3334 
3335         static void putMag(BigInteger bi, int[] magnitude) {
3336             unsafe.putObjectVolatile(bi, magOffset, magnitude);
3337         }
3338     }
3339 
3340     /**
3341      * Save the {@code BigInteger} instance to a stream.
3342      * The magnitude of a BigInteger is serialized as a byte array for
3343      * historical reasons.
3344      *
3345      * @serialData two necessary fields are written as well as obsolete
3346      *             fields for compatibility with older versions.
3347      */
3348     private void writeObject(ObjectOutputStream s) throws IOException {
3349         // set the values of the Serializable fields
3350         ObjectOutputStream.PutField fields = s.putFields();
3351         fields.put("signum", signum);
3352         fields.put("magnitude", magSerializedForm());
3353         // The values written for cached fields are compatible with older
3354         // versions, but are ignored in readObject so don't otherwise matter.
3355         fields.put("bitCount", -1);
3356         fields.put("bitLength", -1);
3357         fields.put("lowestSetBit", -2);
3358         fields.put("firstNonzeroByteNum", -2);
3359 
3360         // save them
3361         s.writeFields();
3362 }
3363 
3364     /**
3365      * Returns the mag array as an array of bytes.
3366      */
3367     private byte[] magSerializedForm() {
3368         int len = mag.length;
3369 
3370         int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0]));
3371         int byteLen = (bitLen + 7) >>> 3;
3372         byte[] result = new byte[byteLen];
3373 
3374         for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0;
3375              i>=0; i--) {
3376             if (bytesCopied == 4) {
3377                 nextInt = mag[intIndex--];
3378                 bytesCopied = 1;
3379             } else {
3380                 nextInt >>>= 8;
3381                 bytesCopied++;
3382             }
3383             result[i] = (byte)nextInt;
3384         }
3385         return result;
3386     }
3387 
3388     /**
3389      * Converts this {@code BigInteger} to a {@code long}, checking
3390      * for lost information.  If the value of this {@code BigInteger}
3391      * is out of the range of the {@code long} type, then an
3392      * {@code ArithmeticException} is thrown.
3393      *
3394      * @return this {@code BigInteger} converted to a {@code long}.
3395      * @throws ArithmeticException if the value of {@code this} will
3396      * not exactly fit in a {@code long}.
3397      * @see BigInteger#longValue
3398      * @since  1.8
3399      */
3400     public long longValueExact() {
3401         if (mag.length <= 2 && bitLength() <= 63)
3402             return longValue();
3403         else
3404             throw new ArithmeticException("BigInteger out of long range");
3405     }
3406 
3407     /**
3408      * Converts this {@code BigInteger} to an {@code int}, checking
3409      * for lost information.  If the value of this {@code BigInteger}
3410      * is out of the range of the {@code int} type, then an
3411      * {@code ArithmeticException} is thrown.
3412      *
3413      * @return this {@code BigInteger} converted to an {@code int}.
3414      * @throws ArithmeticException if the value of {@code this} will
3415      * not exactly fit in a {@code int}.
3416      * @see BigInteger#intValue
3417      * @since  1.8
3418      */
3419     public int intValueExact() {
3420         if (mag.length <= 1 && bitLength() <= 31)
3421             return intValue();
3422         else
3423             throw new ArithmeticException("BigInteger out of int range");
3424     }
3425 
3426     /**
3427      * Converts this {@code BigInteger} to a {@code short}, checking
3428      * for lost information.  If the value of this {@code BigInteger}
3429      * is out of the range of the {@code short} type, then an
3430      * {@code ArithmeticException} is thrown.
3431      *
3432      * @return this {@code BigInteger} converted to a {@code short}.
3433      * @throws ArithmeticException if the value of {@code this} will
3434      * not exactly fit in a {@code short}.
3435      * @see BigInteger#shortValue
3436      * @since  1.8
3437      */
3438     public short shortValueExact() {
3439         if (mag.length <= 1 && bitLength() <= 31) {
3440             int value = intValue();
3441             if (value >= Short.MIN_VALUE && value <= Short.MAX_VALUE)
3442                 return shortValue();
3443         }
3444         throw new ArithmeticException("BigInteger out of short range");
3445     }
3446 
3447     /**
3448      * Converts this {@code BigInteger} to a {@code byte}, checking
3449      * for lost information.  If the value of this {@code BigInteger}
3450      * is out of the range of the {@code byte} type, then an
3451      * {@code ArithmeticException} is thrown.
3452      *
3453      * @return this {@code BigInteger} converted to a {@code byte}.
3454      * @throws ArithmeticException if the value of {@code this} will
3455      * not exactly fit in a {@code byte}.
3456      * @see BigInteger#byteValue
3457      * @since  1.8
3458      */
3459     public byte byteValueExact() {
3460         if (mag.length <= 1 && bitLength() <= 31) {
3461             int value = intValue();
3462             if (value >= Byte.MIN_VALUE && value <= Byte.MAX_VALUE)
3463                 return byteValue();
3464         }
3465         throw new ArithmeticException("BigInteger out of byte range");
3466     }
3467 }