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

Save This Page
Home » openjdk-7 » java » math » [javadoc | source]