home *** CD-ROM | disk | FTP | other *** search
/ Java 1.2 How-To / JavaHowTo.iso / 3rdParty / jbuilder / unsupported / JDK1.2beta3 / SOURCE / SRC.ZIP / java / math / BigInteger.java < prev   
Encoding:
Java Source  |  1998-03-20  |  48.4 KB  |  1,471 lines
  1. /*
  2.  * @(#)BigInteger.java    1.16 98/03/18
  3.  *
  4.  * Copyright 1996, 1997 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.math;
  16.  
  17. import java.util.Random;
  18.  
  19. /**
  20.  * Immutable arbitrary-precision integers.  All operations behave as if
  21.  * BigIntegers were represented in two's-complement notation (like Java's
  22.  * primitive integer types).  BigIntegers provide analogues to all of Java's
  23.  * primitive integer operators, and all relevant static methods from
  24.  * java.lang.Math.  Additionally, BigIntegers provide operations for modular
  25.  * arithmetic, GCD calculation, primality testing, prime generation,
  26.  * single-bit manipulation, and a few other odds and ends.
  27.  *
  28.  * <P>Semantics of arithmetic operations exactly mimic those of java's integer
  29.  * arithmetic operators, as defined in The Java Language Specification.  For
  30.  * example, division by zero throws an ArithmeticException, and division of
  31.  * a negative by a positive yields a negative (or zero) remainder.  All of
  32.  * the details in the Spec concerning overflow are ignored, as BigIntegers
  33.  * are made as large as necessary to accommodate the results of an operation.
  34.  *
  35.  * <P>Semantics of shift operations extend those of Java's shift operators
  36.  * to allow for negative shift distances.  A right-shift with a negative
  37.  * shift distance results in a left shift, and vice-versa.  The unsigned
  38.  * right shift operator (>>>) is omitted, as this operation makes little
  39.  * sense in combination with the "infinite word size" abstraction provided
  40.  * by this class.
  41.  *
  42.  * <P>Semantics of bitwise logical operations are are exactly mimic those of
  43.  * Java's bitwise integer operators.  The Binary operators (and, or, xor)
  44.  * implicitly perform sign extension on the shorter of the two operands
  45.  * prior to performing the operation.
  46.  *
  47.  * <P>Comparison operations perform signed integer comparisons, analogous to
  48.  * those performed by java's relational and equality operators.
  49.  *
  50.  * <P>Modular arithmetic operations are provided to compute residues, perform
  51.  * exponentiation, and compute multiplicative inverses.  These methods always
  52.  * return a non-negative result, between 0 and (modulus - 1), inclusive.
  53.  *
  54.  * <P>Single-bit operations operate on a single bit of the two's-complement
  55.  * representation of their operand.  If necessary, the operand is sign
  56.  * extended so that it contains the designated bit.  None of the single-bit
  57.  * operations can produce a number with a different sign from the the
  58.  * BigInteger being operated on, as they affect only a single bit, and the
  59.  * "infinite word size" abstraction provided by this class ensures that there
  60.  * are infinitely many "virtual sign bits" preceding each BigInteger.
  61.  *
  62.  *
  63.  * @see BigDecimal
  64.  * @version     1.16, 98/03/18
  65.  * @author      Josh Bloch
  66.  */
  67. public class BigInteger extends Number implements Comparable {
  68.  
  69.     /*
  70.      * The number is internally stored in "minimal" sign-magnitude format
  71.      * (i.e., no BigIntegers have a leading zero byte in their magnitudes).
  72.      * Zero is represented with a signum of 0 (and a zero-length magnitude).
  73.      * Thus, there is exactly one representation for each value.
  74.      */
  75.     private int signum;
  76.     private byte[] magnitude;
  77.  
  78.     /*
  79.      * These "redundant fields" are initialized with recognizable nonsense
  80.      * values, and cached the first time they are needed (or never, if they
  81.      * aren't needed).
  82.      */
  83.     private int bitCount =  -1;
  84.     private int bitLength = -1;
  85.     private int firstNonzeroByteNum = -2;  /* Only used for negative numbers */
  86.     private int lowestSetBit = -2;
  87.  
  88.     //Constructors
  89.  
  90.     /**
  91.      * Translates a byte array containing the two's-complement representation
  92.      * of a (signed) integer into a BigInteger.  The input array is assumed to
  93.      * be big-endian (i.e., the most significant byte is in the [0] position).
  94.      * (The most significant bit of the most significant byte is the sign bit.)
  95.      * The array must contain at least one byte or a NumberFormatException
  96.      * will be thrown.
  97.      */
  98.     public BigInteger(byte[] val) throws NumberFormatException{
  99.     if (val.length == 0)
  100.         throw new NumberFormatException("Zero length BigInteger");
  101.  
  102.     if (val[0] < 0) {
  103.         magnitude = makePositive(val);
  104.         signum = -1;
  105.     } else {
  106.         magnitude = stripLeadingZeroBytes(val);
  107.         signum = (magnitude.length == 0 ? 0 : 1);
  108.     }
  109.     }
  110.  
  111.     /**
  112.      * Translates the sign-magnitude representation of an integer into a
  113.      * BigInteger.  The sign is represented as an integer signum value (-1 for
  114.      * negative, 0 for zero, 1 for positive).  The magnitude is represented
  115.      * as a big-endian byte array (i.e., the most significant byte is in the
  116.      * [0] position).  An invalid signum value or a 0 signum value coupled
  117.      * with a nonzero magnitude will result in a NumberFormatException.
  118.      * A zero length magnitude array is permissible, and will result in
  119.      * in a value of 0 (irrespective of the given signum value).
  120.      */
  121.     public BigInteger(int signum, byte[] magnitude)
  122.     throws NumberFormatException{
  123.     this.magnitude = stripLeadingZeroBytes(magnitude);
  124.  
  125.     if (signum < -1 || signum > 1)
  126.         throw(new NumberFormatException("Invalid signum value"));
  127.  
  128.     if (this.magnitude.length==0) {
  129.         this.signum = 0;
  130.     } else {
  131.         if (signum == 0)
  132.         throw(new NumberFormatException("signum-magnitude mismatch"));
  133.         this.signum = signum;
  134.     }
  135.     }
  136.     
  137.     /**
  138.      * Translates a string containing an optional minus sign followed by a
  139.      * sequence of one or more digits in the specified radix into a BigInteger.
  140.      * The character-to-digit mapping is provided by Character.digit.
  141.      * Any extraneous characters (including whitespace), or a radix outside
  142.      * the range from Character.MIN_RADIX(2) to Character.MAX_RADIX(36),
  143.      * inclusive, will result in a NumberFormatException.
  144.      */
  145.     public BigInteger(String val, int radix) throws NumberFormatException {
  146.     int cursor = 0, numDigits;
  147.  
  148.     if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
  149.         throw new NumberFormatException("Radix out of range");
  150.     if (val.length() == 0)
  151.         throw new NumberFormatException("Zero length BigInteger");
  152.  
  153.     /* Check for leading minus sign */
  154.     signum = 1;
  155.     if (val.charAt(0) == '-') {
  156.         if (val.length() == 1)
  157.         throw new NumberFormatException("Zero length BigInteger");
  158.         signum = -1;
  159.         cursor = 1;
  160.     }
  161.  
  162.         /* Skip leading zeros and compute number of digits in magnitude */
  163.     while (cursor<val.length() && 
  164.                Character.digit(val.charAt(cursor),radix) == 0)
  165.         cursor++;
  166.     if (cursor==val.length()) {
  167.         signum = 0;
  168.         magnitude = new byte[0];
  169.         return;
  170.     } else {
  171.         numDigits = val.length() - cursor;
  172.     }
  173.  
  174.     /* Process first (potentially short) digit group, if necessary */
  175.     int firstGroupLen = numDigits % digitsPerLong[radix];
  176.     if (firstGroupLen == 0)
  177.         firstGroupLen = digitsPerLong[radix];
  178.     String group = val.substring(cursor, cursor += firstGroupLen);
  179.     BigInteger tmp = valueOf(Long.parseLong(group, radix));
  180.  
  181.     /* Process remaining digit groups */
  182.     while (cursor < val.length()) {
  183.         group = val.substring(cursor, cursor += digitsPerLong[radix]);
  184.         long groupVal = Long.parseLong(group, radix);
  185.         if (groupVal <0)
  186.         throw new NumberFormatException("Illegal digit");
  187.         tmp = tmp.multiply(longRadix[radix]).add(valueOf(groupVal));
  188.     }
  189.  
  190.     magnitude = tmp.magnitude;
  191.     }
  192.  
  193.     /**
  194.      * Translates a string containing an optional minus sign followed by a
  195.      * sequence of one or more decimal digits into a BigInteger.  The
  196.      * character-to-digit mapping is provided by Character.digit.
  197.      * Any extraneous characters (including whitespace) will result in a
  198.      * NumberFormatException. 
  199.      */
  200.     public BigInteger(String val) throws NumberFormatException {
  201.     this(val, 10);
  202.     }
  203.  
  204.     /**
  205.      * Returns a random number uniformly distributed on [0, 2**numBits - 1]
  206.      * (assuming a fair source of random bits is provided in rndSrc).
  207.      * Note that this constructor always returns a non-negative BigInteger.
  208.      * Throws an IllegalArgumentException if numBits < 0.
  209.      */
  210.     public BigInteger(int numBits, Random rndSrc)
  211.     throws IllegalArgumentException {
  212.     this(1, randomBits(numBits, rndSrc));
  213.     }
  214.  
  215.     private static byte[] randomBits(int numBits, Random rndSrc)
  216.     throws IllegalArgumentException {
  217.     if (numBits < 0)
  218.         throw new IllegalArgumentException("numBits must be non-negative");
  219.     int numBytes = (numBits+7)/8;
  220.     byte[] randomBits = new byte[numBytes];
  221.  
  222.     /* Generate random bytes and mask out any excess bits */
  223.     if (numBytes > 0) {
  224.         rndSrc.nextBytes(randomBits);
  225.         int excessBits = 8*numBytes - numBits;
  226.         randomBits[0] &= (1 << (8-excessBits)) - 1;
  227.     }
  228.     return randomBits;
  229.     }
  230.  
  231.  
  232.     /**
  233.      * Returns a randomly selected BigInteger with the specified bitLength
  234.      * that is probably prime.  The certainty parameter is a measure of
  235.      * the uncertainty that the caller is willing to tolerate: the probability
  236.      * that the number is prime will exceed 1 - 1/2**certainty.  The execution
  237.      * time is proportional to the value of the certainty parameter.  The
  238.      * given random number generator is used to select candidates to be
  239.      * tested for primality.  Throws an ArithmeticException if bitLength < 2.
  240.      */
  241.     public BigInteger(int bitLength, int certainty, Random rnd) {
  242.     if (bitLength < 2)
  243.         throw new ArithmeticException("bitLength < 2");
  244.  
  245.     BigInteger p;
  246.     do {
  247.         /*
  248.          * Select a candidate of exactly the right length.  Note that
  249.          * Plumb's generator doesn't handle bitLength<=16 properly.
  250.          */
  251.         do {
  252.         p = new BigInteger(bitLength-1, rnd).setBit(bitLength-1);
  253.         p = (bitLength <= 16
  254.              ? (bitLength > 2 ? p.setBit(0) : p)
  255.              : new BigInteger(plumbGeneratePrime(p.magnitude), 1));
  256.         } while (p.bitLength() != bitLength);
  257.     } while (!p.isProbablePrime(certainty));
  258.  
  259.     signum = 1;
  260.     magnitude = p.magnitude;
  261.     }
  262.  
  263.  
  264.     /**
  265.      * This private constructor differs from its public cousin
  266.      * with the arguments reversed in two ways: it assumes that its
  267.      * arguments are correct, and it doesn't copy the magnitude array.
  268.      */
  269.     private BigInteger(byte[] magnitude, int signum) {
  270.     this.signum = (magnitude.length==0 ? 0 : signum);
  271.     this.magnitude = magnitude;
  272.     }
  273.  
  274.  
  275.     //Static Factory Methods
  276.  
  277.     /**
  278.      * Returns a BigInteger with the specified value.  This factory is provided
  279.      * in preference to a (long) constructor because it allows for reuse
  280.      * of frequently used BigIntegers (like 0 and 1), obviating the need for
  281.      * exported constants.
  282.      */
  283.     public static BigInteger valueOf(long val) {
  284.     /* If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant */
  285.     if (val == 0)
  286.         return ZERO;
  287.     if (val > 0 && val <= MAX_CONSTANT)
  288.         return posConst[(int) val];
  289.     else if (val < 0 && val >= -MAX_CONSTANT)
  290.         return negConst[(int) -val];
  291.  
  292.     /* Dump two's complement binary into valArray */
  293.     byte valArray[] = new byte[8];
  294.     for (int i=0; i<8; i++, val >>= 8)
  295.         valArray[7-i] = (byte)val;
  296.     return new BigInteger(valArray);
  297.     }
  298.  
  299.     private final static BigInteger ZERO = new BigInteger(new byte[0], 0);
  300.  
  301.     /**
  302.      * Initialize static constant array when class is loaded.
  303.      */
  304.     private final static int MAX_CONSTANT = 16;
  305.     private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
  306.     private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
  307.     static {
  308.     for (int i = 1; i <= MAX_CONSTANT; i++) {
  309.         byte[] magnitude = new byte[1];
  310.         magnitude[0] = (byte) i;
  311.         posConst[i] = new BigInteger(magnitude,  1);
  312.         negConst[i] = new BigInteger(magnitude, -1);
  313.     }
  314.     }
  315.  
  316.     /**
  317.      * Returns a BigInteger with the given two's complement representation.
  318.      * Assumes that the input array will not be modified (the returned
  319.      * BigInteger will reference the input array if feasible).
  320.      */
  321.     private static BigInteger valueOf(byte val[]) {
  322.     return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
  323.     }
  324.  
  325.  
  326.     // Arithmetic Operations
  327.  
  328.     /**
  329.      * Returns a BigInteger whose value is (this + val).
  330.      */
  331.     public BigInteger add(BigInteger val) throws ArithmeticException {
  332.     if (val.signum == 0)
  333.         return this;
  334.     else if (this.signum == 0)
  335.         return val;
  336.     else if (val.signum == signum)
  337.         return new BigInteger(plumbAdd(magnitude, val.magnitude), signum);
  338.     else if (this.signum < 0)
  339.         return plumbSubtract(val.magnitude, magnitude);
  340.     else  /* val.signum < 0 */
  341.         return plumbSubtract(magnitude, val.magnitude);
  342.     }
  343.  
  344.     /**
  345.      * Returns a BigInteger whose value is (this - val).
  346.      */
  347.     public BigInteger subtract(BigInteger val) {
  348.     return add(new BigInteger(val.magnitude, -val.signum));
  349.     }
  350.  
  351.     /**
  352.      * Returns a BigInteger whose value is (this * val).
  353.      */
  354.     public BigInteger multiply(BigInteger val) {
  355.  
  356.     if (val.signum == 0 || this.signum==0)
  357.         return ZERO;
  358.     else
  359.         return new BigInteger(plumbMultiply(magnitude, val.magnitude),
  360.                   signum * val.signum);
  361.     }
  362.  
  363.     /**
  364.      * Returns a BigInteger whose value is (this / val).  Throws an
  365.      * ArithmeticException if val == 0.
  366.      */
  367.     public BigInteger divide(BigInteger val) throws ArithmeticException {
  368.  
  369.     if (val.signum == 0)
  370.         throw new ArithmeticException("BigInteger divide by zero");
  371.     else if (this.signum == 0)
  372.         return ZERO;
  373.     else
  374.         return new BigInteger(plumbDivide(magnitude, val.magnitude),
  375.                   signum * val.signum);
  376.     }
  377.  
  378.     /**
  379.      * Returns a BigInteger whose value is (this % val).  Throws an
  380.      * ArithmeticException if val == 0.
  381.      */
  382.     public BigInteger remainder(BigInteger val) throws ArithmeticException {
  383.  
  384.     if (val.signum == 0)
  385.         throw new ArithmeticException("BigInteger divide by zero");
  386.     else if (this.signum == 0)
  387.         return ZERO;
  388.     else if (this.magnitude.length < val.magnitude.length)
  389.         return this; /*** WORKAROUND FOR BUG IN R1.1 OF PLUMB'S PKG ***/
  390.     else
  391.         return new BigInteger(plumbRemainder(magnitude,val.magnitude),
  392.                   signum);
  393.     }
  394.  
  395.     /**
  396.      * Returns an array of two BigIntegers. The first ([0]) element of
  397.      * the return value is the quotient (this / val), and the second ([1])
  398.      * element is the remainder (this % val).  Throws an ArithmeticException
  399.      * if val == 0.
  400.      */
  401.     public BigInteger[] divideAndRemainder(BigInteger val)
  402.     throws ArithmeticException {
  403.     BigInteger result[] = new BigInteger[2];
  404.  
  405.     if (val.signum == 0) {
  406.         throw new ArithmeticException("BigInteger divide by zero");
  407.     } else if (this.signum == 0) {
  408.         result[0] = result[1] = ZERO;
  409.     } else if (this.magnitude.length < val.magnitude.length) {
  410.         /*** WORKAROUND FOR A BUG IN R1.1 OF PLUMB'S PACKAGE ***/
  411.         result[0] = ZERO;
  412.         result[1] = this;
  413.     } else {
  414.         byte resultMagnitude[][] =
  415.         plumbDivideAndRemainder(magnitude, val.magnitude);
  416.         result[0] = new BigInteger(resultMagnitude[0], signum*val.signum);
  417.         result[1] = new BigInteger(resultMagnitude[1], signum);
  418.     }
  419.     return result;
  420.     }
  421.  
  422.     /**
  423.      * Returns a BigInteger whose value is (this ** exponent).  Throws
  424.      * an ArithmeticException if exponent < 0 (as the operation would yield
  425.      * a non-integer value). Note that exponent is an integer rather than
  426.      * a BigInteger.
  427.      */
  428.     public BigInteger pow(int exponent) throws ArithmeticException {
  429.     if (exponent < 0)
  430.         throw new ArithmeticException("Negative exponent");
  431.     if (signum==0)
  432.         return (exponent==0 ? ONE : this);
  433.  
  434.     /* Perform exponetiation using repeated squaring trick */
  435.     BigInteger result = valueOf(exponent<0 && (exponent&1)==1 ? -1 : 1);
  436.     BigInteger baseToPow2 = this;
  437.     while (exponent != 0) {
  438.         if ((exponent & 1)==1)
  439.         result = result.multiply(baseToPow2);
  440.         if ((exponent >>= 1) != 0)
  441.         baseToPow2 = new BigInteger(
  442.                     plumbSquare(baseToPow2.magnitude), 1);
  443.     }
  444.     return result;
  445.     }
  446.  
  447.     /**
  448.      * Returns a BigInteger whose value is the greatest common denominator
  449.      * of abs(this) and abs(val).  Returns 0 if this == 0 && val == 0.
  450.      */
  451.     public BigInteger gcd(BigInteger val) {
  452.     if (val.signum == 0)
  453.         return this.abs();
  454.     else if (this.signum == 0)
  455.         return val.abs();
  456.     else
  457.         return new BigInteger(plumbGcd(magnitude, val.magnitude), 1);
  458.     }
  459.  
  460.    /**
  461.     * Returns a BigInteger whose value is the absolute value of this
  462.     * number.
  463.     */
  464.     public BigInteger abs() {
  465.     return (signum >= 0 ? this : this.negate());
  466.     }
  467.  
  468.     /**
  469.      * Returns a BigInteger whose value is (-1 * this).
  470.      */
  471.     public BigInteger negate() {
  472.     return new BigInteger(this.magnitude, -this.signum);
  473.     }
  474.  
  475.     /**
  476.      * Returns the signum function of this number (i.e., -1, 0 or 1 as
  477.      * the value of this number is negative, zero or positive).
  478.      */
  479.     public int signum() {
  480.     return this.signum;
  481.     }
  482.  
  483.     // Modular Arithmetic Operations
  484.  
  485.     /**
  486.      * Returns a BigInteger whose value is this mod m. Throws an
  487.      * ArithmeticException if m <= 0.
  488.      */
  489.     public BigInteger mod(BigInteger m) {
  490.     if (m.signum <= 0)
  491.         throw new ArithmeticException("BigInteger: modulus not positive");
  492.  
  493.     BigInteger result = this.remainder(m);
  494.     return (result.signum >= 0 ? result : result.add(m));
  495.     }
  496.  
  497.     /**
  498.      * Returns a BigInteger whose value is (this ** exponent) mod m.  (If
  499.      * exponent == 1, the returned value is (this mod m).  If exponent < 0,
  500.      * the returned value is the modular multiplicative inverse of
  501.      * (this ** -exponent).)  Throws an ArithmeticException if m <= 0.
  502.      */
  503.     public BigInteger modPow(BigInteger exponent, BigInteger m) {
  504.     if (m.signum <= 0)
  505.         throw new ArithmeticException("BigInteger: modulus not positive");
  506.  
  507.     /* Workaround for a bug in Plumb: x^0 (y) dumps core for x != 0 */
  508.     if (exponent.signum == 0)
  509.         return ONE;
  510.  
  511.     boolean invertResult;
  512.     if ((invertResult = (exponent.signum < 0)))
  513.         exponent = exponent.negate();
  514.  
  515.     BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0 
  516.                ? this.mod(m) : this);
  517.     BigInteger result;
  518.     if (m.testBit(0)) { /* Odd modulus: just pass it on to Plumb */
  519.         result = new BigInteger
  520.          (plumbModPow(base.magnitude, exponent.magnitude, m.magnitude), 1);
  521.     } else {
  522.         /*
  523.          * Even modulus.  Plumb only supports odd, so tear it into
  524.          * "odd part" (m1) and power of two (m2), use Plumb to exponentiate
  525.          * mod m1, manually exponentiate mod m2, and use Chinese Remainder
  526.          * Theorem to combine results.
  527.          */
  528.  
  529.         /* Tear m apart into odd part (m1) and power of 2 (m2) */
  530.         int p = m.getLowestSetBit();      /* Max pow of 2 that divides m */
  531.         BigInteger m1 = m.shiftRight(p);  /* m/2**p */
  532.         BigInteger m2 = ONE.shiftLeft(p); /* 2**p */
  533.  
  534.             /* Caculate (base ** exponent) mod m1.
  535.              * Special-case mod 1 to prevent Plumb's pkg from blowing up. */
  536.             BigInteger a1 = (m1.equals(ONE) ? ZERO :
  537.                              new BigInteger(plumbModPow(base.magnitude,
  538.                                         exponent.magnitude, m1.magnitude), 1));
  539.  
  540.         /* Caculate (this ** exponent) mod m2 */
  541.         BigInteger a2 = base.modPow2(exponent, p);
  542.  
  543.         /* Combine results using Chinese Remainder Theorem */
  544.         BigInteger y1 = m2.modInverse(m1);
  545.         BigInteger y2 = m1.modInverse(m2);
  546.         result = a1.multiply(m2).multiply(y1).add
  547.              (a2.multiply(m1).multiply(y2)).mod(m);
  548.     }
  549.  
  550.     return (invertResult ? result.modInverse(m) : result);
  551.     }
  552.     
  553.     /**
  554.      * Returns (this ** exponent) mod(2**p)
  555.      */
  556.     private BigInteger modPow2(BigInteger exponent, int p) {
  557.     /*
  558.      * Perform exponetiation using repeated squaring trick, chopping off
  559.      * high order bits as indicated by modulus.
  560.      */
  561.     BigInteger result = valueOf(1);
  562.     BigInteger baseToPow2 = this.mod2(p);
  563.     while (exponent.signum != 0) {
  564.         if (exponent.testBit(0))
  565.         result = result.multiply(baseToPow2).mod2(p);
  566.         exponent = exponent.shiftRight(1);
  567.         if (exponent.signum != 0)
  568.         baseToPow2 = new BigInteger(
  569.                    plumbSquare(baseToPow2.magnitude), 1).mod2(p);
  570.     }
  571.     return result;
  572.     }
  573.  
  574.     /**
  575.      * Returns this mod(2**p).
  576.      * Assumes that this BigInteger >= 0 and p > 0.
  577.      */
  578.     private BigInteger mod2(int p) {
  579.     if (bitLength() <= p)
  580.         return this;
  581.  
  582.     /* Copy remaining bytes of magnitude */
  583.     int numBytes = (p+7)/8;
  584.     byte[] mag = new byte[numBytes];
  585.     for (int i=0; i<numBytes; i++)
  586.         mag[i] = magnitude[i + (magnitude.length - numBytes)];
  587.  
  588.     /* Mask out any excess bits */
  589.     int excessBits = 8*numBytes - p;
  590.     mag[0] &= (1 << (8-excessBits)) - 1;
  591.  
  592.     return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
  593.     }
  594.  
  595.     /**
  596.      * Returns modular multiplicative inverse of this, mod m.  Throws an
  597.      * ArithmeticException if m <= 0 or this has no multiplicative inverse
  598.      * mod m (i.e., gcd(this, m) != 1).
  599.      */
  600.     public BigInteger modInverse(BigInteger m) throws ArithmeticException {
  601.     if (m.signum != 1)
  602.         throw new ArithmeticException("BigInteger: modulus not positive");
  603.  
  604.     /* Calculate (this mod m) */
  605.     BigInteger modVal = this.remainder(m);
  606.     if (modVal.signum < 0)
  607.         modVal = modVal.add(m);
  608.     if (!modVal.gcd(m).equals(ONE))
  609.         throw new ArithmeticException("BigInteger not invertible");
  610.  
  611.     return new BigInteger(plumbModInverse(modVal.magnitude,m.magnitude),1);
  612.     }
  613.  
  614.  
  615.     // Shift Operations
  616.  
  617.     /**
  618.      * Returns a BigInteger whose value is (this << n).  (Computes
  619.      * floor(this * 2**n).)
  620.      */
  621.     public BigInteger shiftLeft(int n) {
  622.     if (n==0)
  623.         return this;
  624.     if (n<0)
  625.         return shiftRight(-n);
  626.  
  627.     int nBytes = n/8;
  628.     int nBits = n%8;
  629.  
  630.     byte result[] = new byte[(bitLength()+n)/8+1];
  631.     if (nBits == 0) {
  632.         for (int i=nBytes; i<result.length; i++)
  633.         result[result.length-1-i] = getByte(i-nBytes);
  634.     } else {
  635.         for (int i=nBytes; i<result.length; i++)
  636.         result[result.length-1-i] = (byte)
  637.             ((getByte(i-nBytes) << nBits)
  638.             | (i==nBytes ? 0
  639.                : ((getByte(i-nBytes-1)&0xff) >> (8-nBits))));
  640.     }
  641.  
  642.     return valueOf(result);
  643.     }
  644.  
  645.     /**
  646.      * Returns a BigInteger whose value is (this >> n).  Sign extension is
  647.      * performed.  (Computes floor(this / 2**n).)
  648.      */
  649.     public BigInteger shiftRight(int n) {
  650.     if (n==0)
  651.         return this;
  652.     if (n<0)
  653.         return shiftLeft(-n);
  654.     if (n >= bitLength())
  655.         return (signum<0 ? valueOf(-1) : ZERO);
  656.  
  657.     int nBytes = n/8;
  658.     int nBits = n%8;
  659.  
  660.     byte result[] = new byte[(bitLength-n)/8+1];
  661.     if (nBits == 0) {
  662.         for (int i=0; i<result.length; i++)
  663.         result[result.length-1-i] = getByte(nBytes+i);
  664.     } else {
  665.         for (int i=0; i<result.length; i++)
  666.         result[result.length-1-i] = (byte)
  667.         ((getByte(nBytes+i+1)<<8 | (getByte(nBytes+i)&0xff)) >> nBits);
  668.     }
  669.  
  670.     return valueOf(result);
  671.     }
  672.  
  673.  
  674.     // Bitwise Operations
  675.  
  676.     /**
  677.      * Returns a BigInteger whose value is (this & val).  (This method
  678.      * returns a negative number iff this and val are both negative.)
  679.      */
  680.     public BigInteger and(BigInteger val) {
  681.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  682.     for (int i=0; i<result.length; i++)
  683.         result[i] = (byte) (getByte(result.length-i-1)
  684.                 & val.getByte(result.length-i-1));
  685.  
  686.     return valueOf(result);
  687.     }
  688.  
  689.     /**
  690.      * Returns a BigInteger whose value is (this | val).  (This method
  691.      * returns a negative number iff either this or val is negative.)
  692.      */
  693.     public BigInteger or(BigInteger val) {
  694.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  695.     for (int i=0; i<result.length; i++)
  696.         result[i] = (byte) (getByte(result.length-i-1)
  697.                 | val.getByte(result.length-i-1));
  698.  
  699.     return valueOf(result);
  700.     }
  701.  
  702.     /**
  703.      * Returns a BigInteger whose value is (this ^ val).  (This method
  704.      * returns a negative number iff exactly one of this and val are 
  705.      * negative.)
  706.      */
  707.     public BigInteger xor(BigInteger val) {
  708.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  709.     for (int i=0; i<result.length; i++)
  710.         result[i] = (byte) (getByte(result.length-i-1)
  711.                 ^ val.getByte(result.length-i-1));
  712.  
  713.     return valueOf(result);
  714.     }
  715.  
  716.     /**
  717.      * Returns a BigInteger whose value is (~this).  (This method returns
  718.      * a negative value iff this number is non-negative.)
  719.      */
  720.     public BigInteger not() {
  721.     byte[] result = new byte[byteLength()];
  722.     for (int i=0; i<result.length; i++)
  723.         result[i] = (byte) ~getByte(result.length-i-1);
  724.  
  725.     return valueOf(result);
  726.     }
  727.  
  728.     /**
  729.      * Returns a BigInteger whose value is (this & ~val).  This method,
  730.      * which is equivalent to and(val.not()), is provided as a convenience
  731.      * for masking operations.  (This method returns a negative number iff
  732.      * this is negative and val is positive.)
  733.      */
  734.     public BigInteger andNot(BigInteger val) {
  735.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  736.     for (int i=0; i<result.length; i++)
  737.         result[i] = (byte) (getByte(result.length-i-1)
  738.                 & ~val.getByte(result.length-i-1));
  739.  
  740.     return valueOf(result);
  741.     }
  742.  
  743.  
  744.     // Single Bit Operations
  745.  
  746.     /**
  747.      * Returns true iff the designated bit is set. (Computes
  748.      * ((this & (1<<n)) != 0).)
  749.      * Throws an ArithmeticException if n < 0.
  750.      */
  751.     public boolean testBit(int n) throws ArithmeticException {
  752.     if (n<0)
  753.         throw new ArithmeticException("Negative bit address");
  754.  
  755.     return (getByte(n/8) & (1 << (n%8))) != 0;
  756.     }
  757.  
  758.     /**
  759.      * Returns a BigInteger whose value is equivalent to this number
  760.      * with the designated bit set.  (Computes (this | (1<<n)).)
  761.      * Throws an ArithmeticException if n < 0.
  762.      */
  763.     public BigInteger setBit(int n) throws ArithmeticException {
  764.     if (n<0)
  765.         throw new ArithmeticException("Negative bit address");
  766.  
  767.     int byteNum = n/8;
  768.     byte[] result = new byte[Math.max(byteLength(), byteNum+2)];
  769.  
  770.     for (int i=0; i<result.length; i++)
  771.         result[result.length-i-1] = getByte(i);
  772.  
  773.     result[result.length-byteNum-1] |= (1 << (n%8));
  774.  
  775.     return valueOf(result);
  776.     }
  777.  
  778.     /**
  779.      * Returns a BigInteger whose value is equivalent to this number
  780.      * with the designated bit cleared. (Computes (this & ~(1<<n)).)
  781.      * Throws an ArithmeticException if n < 0.
  782.      */
  783.     public BigInteger clearBit(int n) throws ArithmeticException {
  784.     if (n<0)
  785.         throw new ArithmeticException("Negative bit address");
  786.  
  787.     int byteNum = n/8;
  788.     byte[] result = new byte[Math.max(byteLength(), (n+1)/8+1)];
  789.  
  790.     for (int i=0; i<result.length; i++)
  791.         result[result.length-i-1] = getByte(i);
  792.  
  793.     result[result.length-byteNum-1] &= ~(1 << (n%8));
  794.  
  795.     return valueOf(result);
  796.     }
  797.  
  798.     /**
  799.      * Returns a BigInteger whose value is equivalent to this number
  800.      * with the designated bit flipped.  (Computes (this ^ (1<<n)).)
  801.      * Throws an ArithmeticException if n < 0.
  802.      */
  803.     public BigInteger flipBit(int n) throws ArithmeticException {
  804.     if (n<0)
  805.         throw new ArithmeticException("Negative bit address");
  806.  
  807.     int byteNum = n/8;
  808.     byte[] result = new byte[Math.max(byteLength(), byteNum+2)];
  809.  
  810.     for (int i=0; i<result.length; i++)
  811.         result[result.length-i-1] = getByte(i);
  812.  
  813.     result[result.length-byteNum-1] ^= (1 << (n%8));
  814.  
  815.     return valueOf(result);
  816.     }
  817.  
  818.     /**
  819.      * Returns the index of the rightmost (lowest-order) one bit in this
  820.      * number (i.e., the number of zero bits to the right of the rightmost
  821.      * one bit).  Returns -1 if this number contains no one bits.
  822.      * (Computes (this==0? -1 : log2(this & -this)).)
  823.      */
  824.     public int getLowestSetBit() {
  825.     /*
  826.      * Initialize lowestSetBit field the first time this method is
  827.      * executed. This method depends on the atomicity of int modifies;
  828.      * without this guarantee, it would have to be synchronized.
  829.      */
  830.     if (lowestSetBit == -2) {
  831.         if (signum == 0) {
  832.         lowestSetBit = -1;
  833.         } else {
  834.         /* Search for lowest order nonzero byte */
  835.         int i;
  836.         byte b;
  837.         for (i=0; (b = getByte(i))==0; i++)
  838.             ;
  839.         lowestSetBit = 8*i + trailingZeroCnt[b & 0xFF];
  840.         }
  841.     }
  842.     return lowestSetBit;
  843.     }
  844.  
  845.  
  846.     // Miscellaneous Bit Operations
  847.  
  848.     /**
  849.      * Returns the number of bits in the minimal two's-complement
  850.      * representation of this number, *excluding* a sign bit, i.e.,
  851.      * (ceil(log2(this < 0 ? -this : this + 1))).  (For positive
  852.      * numbers, this is equivalent to the number of bits in the
  853.      * ordinary binary representation.)
  854.      */
  855.     public int bitLength() {
  856.     /*
  857.      * Initialize bitLength field the first time this method is executed.
  858.      * This method depends on the atomicity of int modifies; without
  859.      * this guarantee, it would have to be synchronized.
  860.      */
  861.     if (bitLength == -1) {
  862.         if (signum == 0) {
  863.         bitLength = 0;
  864.         } else {
  865.         /* Calculate the bit length of the magnitude */
  866.         int magBitLength = 8*(magnitude.length-1)
  867.                        + bitLen[magnitude[0] & 0xff];
  868.  
  869.         if (signum < 0) {
  870.             /* Check if magnitude is a power of two */
  871.             boolean pow2 = (bitCnt[magnitude[0]&0xff] == 1);
  872.             for(int i=1; i<magnitude.length && pow2; i++)
  873.             pow2 = (magnitude[i]==0);
  874.  
  875.             bitLength = (pow2 ? magBitLength-1 : magBitLength);
  876.         } else {
  877.             bitLength = magBitLength;
  878.         }
  879.         }
  880.     }
  881.     return bitLength;
  882.     }
  883.  
  884.     /*
  885.      * bitLen[i] is the number of bits in the binary representaion of i.
  886.      */
  887.     private final static byte bitLen[] = {
  888.     0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
  889.     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  890.     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  891.     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  892.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  893.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  894.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  895.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  896.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  897.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  898.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  899.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  900.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  901.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  902.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  903.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};
  904.  
  905.     /**
  906.      * Returns the number of bits in the two's complement representation
  907.      * of this number that differ from its sign bit.  This method is
  908.      * useful when implementing bit-vector style sets atop BigIntegers.
  909.      */
  910.     public int bitCount() {
  911.     /*
  912.      * Initialize bitCount field the first time this method is executed.
  913.      * This method depends on the atomicity of int modifies; without
  914.      * this guarantee, it would have to be synchronized.
  915.      */
  916.     if (bitCount == -1) {
  917.         /* Count the bits in the magnitude */
  918.         int magBitCount = 0;
  919.         for (int i=0; i<magnitude.length; i++)
  920.         magBitCount += bitCnt[magnitude[i] & 0xff];
  921.  
  922.         if (signum < 0) {
  923.         /* Count the trailing zeros in the magnitude */
  924.         int magTrailingZeroCount = 0, j;
  925.         for (j=magnitude.length-1; magnitude[j]==0; j--)
  926.             magTrailingZeroCount += 8;
  927.         magTrailingZeroCount += trailingZeroCnt[magnitude[j] & 0xff];
  928.  
  929.         bitCount = magBitCount + magTrailingZeroCount - 1;
  930.         } else {
  931.         bitCount = magBitCount;
  932.         }
  933.     }
  934.     return bitCount;
  935.     }
  936.  
  937.     /*
  938.      * bitCnt[i] is the number of 1 bits in the binary representation of i.
  939.      */
  940.     private final static byte bitCnt[] = {
  941.     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  942.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  943.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  944.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  945.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  946.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  947.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  948.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  949.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  950.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  951.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  952.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  953.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  954.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  955.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  956.     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  957.  
  958.     /*
  959.      * trailingZeroCnt[i] is the number of trailing zero bits in the binary
  960.      * representaion of i.
  961.      */
  962.     private final static byte trailingZeroCnt[] = {
  963.     8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  964.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  965.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  966.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  967.     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  968.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  969.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  970.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  971.     7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  972.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  973.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  974.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  975.     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  976.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  977.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  978.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
  979.  
  980.  
  981.  
  982.     // Primality Testing
  983.  
  984.     /**
  985.      * Returns true if this BigInteger is probably prime, false if it's
  986.      * definitely composite.  The certainty parameter is a measure 
  987.      * of the uncertainty that the caller is willing to tolerate:
  988.      * the method returns true if the probability that this number is
  989.      * is prime exceeds 1 - 1/2**certainty.  The execution time is
  990.      * proportional to the value of the certainty parameter.
  991.      */
  992.     public boolean isProbablePrime(int certainty) {
  993.     /*
  994.      * This test is taken from the DSA spec.
  995.      */
  996.     int n = certainty/2;
  997.     if (n <= 0)
  998.         return true;
  999.     BigInteger w = this.abs();
  1000.     if (w.equals(TWO))
  1001.         return true;
  1002.     if (!w.testBit(0) || w.equals(ONE))
  1003.         return false;
  1004.  
  1005.     /* Find a and m such that m is odd and w == 1 + 2**a * m */
  1006.     BigInteger m = w.subtract(ONE);
  1007.     int a = m.getLowestSetBit();
  1008.     m = m.shiftRight(a);
  1009.  
  1010.     /* Do the tests */
  1011.     Random rnd = new Random();
  1012.     for(int i=0; i<n; i++) {
  1013.         /* Generate a uniform random on (1, w) */
  1014.         BigInteger b;
  1015.         do {
  1016.         b = new BigInteger(w.bitLength(), rnd);
  1017.         } while (b.compareTo(ONE) <= 0 || b.compareTo(w) >= 0);
  1018.  
  1019.         int j = 0;
  1020.         BigInteger z = b.modPow(m, w);
  1021.         while(!((j==0 && z.equals(ONE)) || z.equals(w.subtract(ONE)))) {
  1022.         if (j>0 && z.equals(ONE) || ++j==a)
  1023.             return false;
  1024.         z = z.modPow(TWO, w);
  1025.         }
  1026.     }
  1027.     return true;
  1028.     }
  1029.  
  1030.  
  1031.     // Comparison Operations
  1032.  
  1033.     /**
  1034.      * Returns -1, 0 or 1 as this number is less than, equal to, or
  1035.      * greater than val.  This method is provided in preference to
  1036.      * individual methods for each of the six boolean comparison operators
  1037.      * (<, ==, >, >=, !=, <=).  The suggested idiom for performing
  1038.      * these comparisons is:  (x.compareTo(y) <op> 0), where <op> is
  1039.      * one of the six comparison operators.
  1040.      */
  1041.     public int compareTo(BigInteger val) {
  1042.     return (signum==val.signum
  1043.         ? signum*byteArrayCmp(magnitude, val.magnitude)
  1044.         : (signum>val.signum ? 1 : -1));
  1045.     }
  1046.  
  1047.     /**
  1048.      * Compares this BigInteger to another Object.  If the Object is a
  1049.      * BigInteger, this function behaves like
  1050.      * <code>compareTo(BigInteger)</code>.  Otherwise, it throws a
  1051.      * <code>ClassCastException</code> (as BigIntegers are comparable
  1052.      * only to other BigIntegers).
  1053.      *
  1054.      * @param   o the <code>Object</code> to be compared.
  1055.      * @return  the value <code>0</code> if the argument is a BigInteger
  1056.      *        numerically equal to this BigInteger; a value less than
  1057.      *        <code>0</code> if the argument is a BigInteger numerically
  1058.      *        greater than this BigInteger; and a value greater than
  1059.      *        <code>0</code> if the argument is a BigInteger numerically
  1060.      *        less than this BigInteger.
  1061.      * @exception <code>ClassCastException</code> if the argument is not a
  1062.      *          <code>BigInteger</code>. 
  1063.      * @see     java.lang.Comparable
  1064.      * @since   JDK1.2
  1065.      */
  1066.     public int compareTo(Object o) {
  1067.     return compareTo((BigInteger)o);
  1068.     }
  1069.  
  1070.     /*
  1071.      * Returns -1, 0 or +1 as big-endian unsigned byte array arg1 is
  1072.      * <, == or > arg2.
  1073.      */
  1074.     private static int byteArrayCmp(byte[] arg1, byte[] arg2) {
  1075.     if (arg1.length < arg2.length)
  1076.         return -1;
  1077.     if (arg1.length > arg2.length)
  1078.         return 1;
  1079.  
  1080.     /* Argument lengths are equal; compare the values */
  1081.     for (int i=0; i<arg1.length; i++) {
  1082.         int b1 = arg1[i] & 0xff;
  1083.         int b2 = arg2[i] & 0xff;
  1084.         if (b1 < b2)
  1085.         return -1;
  1086.         if (b1 > b2)
  1087.         return 1;
  1088.     }
  1089.     return 0;
  1090.     }
  1091.  
  1092.     /**
  1093.      * Returns true iff x is a BigInteger whose value is equal to this number.
  1094.      * This method is provided so that BigIntegers can be used as hash keys.
  1095.      */
  1096.     public boolean equals(Object x) {
  1097.     if (!(x instanceof BigInteger))
  1098.         return false;
  1099.     BigInteger xInt = (BigInteger) x;
  1100.  
  1101.     if (xInt.signum != signum || xInt.magnitude.length != magnitude.length)
  1102.         return false;
  1103.  
  1104.     /* This test is just an optimization, which may or may not help */
  1105.     if (xInt == this)
  1106.         return true;
  1107.  
  1108.     for (int i=0; i<magnitude.length; i++)
  1109.         if (xInt.magnitude[i] != magnitude[i])
  1110.         return false;
  1111.  
  1112.     return true;
  1113.     }
  1114.  
  1115.     /**
  1116.      * Returns the BigInteger whose value is the lesser of this and val.
  1117.      * If the values are equal, either may be returned.
  1118.      */
  1119.     public BigInteger min(BigInteger val) {
  1120.     return (compareTo(val)<0 ? this : val);
  1121.     }
  1122.  
  1123.     /**
  1124.      * Returns the BigInteger whose value is the greater of this and val.
  1125.      * If the values are equal, either may be returned.
  1126.      */
  1127.     public BigInteger max(BigInteger val) {
  1128.     return (compareTo(val)>0 ? this : val);
  1129.     }
  1130.  
  1131.  
  1132.     // Hash Function
  1133.  
  1134.     /**
  1135.      * Computes a hash code for this object.
  1136.      */
  1137.     public int hashCode() {
  1138.     int hashCode = 0;
  1139.  
  1140.     for (int i=0; i<magnitude.length; i++)
  1141.         hashCode = 31*hashCode + (magnitude[i] & 0xff);
  1142.  
  1143.     return hashCode * signum;
  1144.     }
  1145.  
  1146.     // Format Converters
  1147.  
  1148.     /**
  1149.      * Returns the string representation of this number in the given radix.
  1150.      * If the radix is outside the range from Character.MIN_RADIX(2) to
  1151.      * Character.MAX_RADIX(36) inclusive, it will default to 10 (as is the
  1152.      * case for Integer.toString).  The digit-to-character mapping provided
  1153.      * by Character.forDigit is used, and a minus sign is prepended if
  1154.      * appropriate.  (This representation is compatible with the (String, int)
  1155.      * constructor.)
  1156.      */
  1157.     public String toString(int radix) {
  1158.     if (signum == 0)
  1159.         return "0";
  1160.     if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
  1161.         radix = 10;
  1162.  
  1163.     /* Compute upper bound on number of digit groups and allocate space */
  1164.     int maxNumDigitGroups = (magnitude.length + 6)/7;
  1165.     String digitGroup[] = new String[maxNumDigitGroups];
  1166.  
  1167.     /* Translate number to string, a digit group at a time */
  1168.     BigInteger tmp = this.abs();
  1169.     int numGroups = 0;
  1170.     while (tmp.signum != 0) {
  1171.         BigInteger b[] = tmp.divideAndRemainder(longRadix[radix]);
  1172.         digitGroup[numGroups++] = Long.toString(b[1].longValue(), radix);
  1173.         tmp = b[0];
  1174.     }
  1175.  
  1176.     /* Put sign (if any) and first digit group into result buffer */
  1177.     StringBuffer buf = new StringBuffer(numGroups*digitsPerLong[radix]+1);
  1178.     if (signum<0)
  1179.         buf.append('-');
  1180.     buf.append(digitGroup[numGroups-1]);
  1181.  
  1182.     /* Append remaining digit groups padded with leading zeros */
  1183.     for (int i=numGroups-2; i>=0; i--) {
  1184.         /* Prepend (any) leading zeros for this digit group */
  1185.         int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
  1186.         if (numLeadingZeros != 0)
  1187.         buf.append(zeros[numLeadingZeros]);
  1188.         buf.append(digitGroup[i]);
  1189.     }
  1190.  
  1191.     return buf.toString();
  1192.     }
  1193.  
  1194.     /* zero[i] is a string of i consecutive zeros. */
  1195.     private static String zeros[] = new String[64];
  1196.     static {
  1197.     zeros[63] =
  1198.         "000000000000000000000000000000000000000000000000000000000000000";
  1199.     for (int i=0; i<63; i++)
  1200.         zeros[i] = zeros[63].substring(0, i);
  1201.     }
  1202.  
  1203.     /**
  1204.      * Returns the string representation of this number, radix 10.  The
  1205.      * digit-to-character mapping provided by Character.forDigit is used,
  1206.      * and a minus sign is prepended if appropriate.  (This representation
  1207.      * is compatible with the (String) constructor, and allows for string
  1208.      * concatenation with Java's + operator.)
  1209.      */
  1210.     public String toString() {
  1211.     return toString(10);
  1212.     }
  1213.  
  1214.     /**
  1215.      * Returns the two's-complement representation of this number.  The array
  1216.      * is big-endian (i.e., the most significant byte is in the [0] position).
  1217.      * The array contains the minimum number of bytes required to represent
  1218.      * the number (ceil((this.bitLength() + 1)/8)).  (This representation is
  1219.      * compatible with the (byte[]) constructor.) 
  1220.      */
  1221.     public byte[] toByteArray() {
  1222.     byte[] result = new byte[byteLength()];
  1223.     for(int i=0; i<result.length; i++)
  1224.         result[i] = getByte(result.length-i-1);
  1225.  
  1226.     return result;
  1227.     }
  1228.  
  1229.     /**
  1230.      * Converts this number to an int.  Standard narrowing primitive conversion
  1231.      * as per The Java Language Specification.
  1232.      */
  1233.     public int intValue() {
  1234.     int result = 0;
  1235.  
  1236.     for (int i=3; i>=0; i--)
  1237.         result = (result << 8) + (getByte(i) & 0xff);
  1238.     return result;
  1239.     }
  1240.  
  1241.     /**
  1242.      * Converts this number to a long.  Standard narrowing primitive conversion
  1243.      * as per The Java Language Specification.
  1244.      */
  1245.     public long longValue() {
  1246.     long result = 0;
  1247.  
  1248.     for (int i=7; i>=0; i--)
  1249.         result = (result << 8) + (getByte(i) & 0xff);
  1250.     return result;
  1251.     }
  1252.  
  1253.     /**
  1254.      * Converts this number to a float.  Similar to the double-to-float
  1255.      * narrowing primitive conversion defined in The Java Language
  1256.      * Specification: if the number has too great a magnitude to represent
  1257.      * as a float, it will be converted to infinity or negative infinity,
  1258.      * as appropriate.
  1259.      */
  1260.     public float floatValue() {
  1261.     /* Somewhat inefficient, but guaranteed to work. */
  1262.     return Float.valueOf(this.toString()).floatValue();
  1263.     }
  1264.  
  1265.     /**
  1266.      * Converts the number to a double.  Similar to the double-to-float
  1267.      * narrowing primitive conversion defined in The Java Language
  1268.      * Specification: if the number has too great a magnitude to represent
  1269.      * as a double, it will be converted to infinity or negative infinity,
  1270.      * as appropriate.
  1271.      */
  1272.     public double doubleValue() {
  1273.     /* Somewhat inefficient, but guaranteed to work. */
  1274.     return Double.valueOf(this.toString()).doubleValue();
  1275.     }
  1276.  
  1277.     static {
  1278.     try {
  1279.         java.security.AccessController.beginPrivileged();
  1280.         System.loadLibrary("math");
  1281.     } finally {
  1282.         java.security.AccessController.endPrivileged();
  1283.     }
  1284.     plumbInit();
  1285.     }
  1286.  
  1287.  
  1288.     private final static BigInteger ONE = valueOf(1);
  1289.     private final static BigInteger TWO = valueOf(2);
  1290.  
  1291.     /**
  1292.      * Returns a copy of the input array stripped of any leading zero bytes.
  1293.      */
  1294.     static private byte[] stripLeadingZeroBytes(byte a[]) {
  1295.     int keep;
  1296.     
  1297.     /* Find first nonzero byte */
  1298.     for (keep=0; keep<a.length && a[keep]==0; keep++)
  1299.         ;
  1300.  
  1301.     /* Allocate new array and copy relevant part of input array */
  1302.     byte result[] = new byte[a.length - keep];
  1303.     for (int i = keep; i<a.length; i++)
  1304.         result[i - keep] = a[i];
  1305.  
  1306.     return result;
  1307.     }
  1308.  
  1309.     /**
  1310.      * Takes an array a representing a negative 2's-complement number and
  1311.      * returns the minimal (no leading zero bytes) unsigned whose value is -a.
  1312.      */
  1313.     static private byte[] makePositive(byte a[]) {
  1314.     int keep, j;
  1315.  
  1316.     /* Find first non-sign (0xff) byte of input */
  1317.     for (keep=0; keep<a.length && a[keep]==-1; keep++)
  1318.         ;
  1319.  
  1320.     /* Allocate output array.  If all non-sign bytes are 0x00, we must
  1321.      * allocate space for one extra output byte. */
  1322.     for (j=keep; j<a.length && a[j]==0; j++)
  1323.         ;
  1324.     int extraByte = (j==a.length ? 1 : 0);
  1325.     byte result[] = new byte[a.length - keep + extraByte];
  1326.  
  1327.     /* Copy one's complement of input into into output, leaving extra
  1328.      * byte (if it exists) == 0x00 */
  1329.     for (int i = keep; i<a.length; i++)
  1330.         result[i - keep + extraByte] = (byte) ~a[i];
  1331.  
  1332.     /* Add one to one's complement to generate two's complement */
  1333.     for (int i=result.length-1; ++result[i]==0; i--)
  1334.         ;
  1335.  
  1336.     return result;
  1337.     }
  1338.  
  1339.     /*
  1340.      * The following two arrays are used for fast String conversions.  Both
  1341.      * are indexed by radix.  The first is the number of digits of the given
  1342.      * radix that can fit in a Java long without "going negative", i.e., the
  1343.      * highest integer n such that radix ** n < 2 ** 63.  The second is the
  1344.      * "long radix" that tears each number into "long digits", each of which
  1345.      * consists of the number of digits in the corresponding element in
  1346.      * digitsPerLong (longRadix[i] = i ** digitPerLong[i]).  Both arrays have
  1347.      * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
  1348.      * used.
  1349.      */
  1350.  
  1351.     private static int digitsPerLong[] = {0, 0,
  1352.     62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
  1353.     14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
  1354.  
  1355.     private static BigInteger longRadix[] = {null, null,
  1356.         valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
  1357.     valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
  1358.     valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
  1359.         valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
  1360.     valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
  1361.     valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
  1362.     valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
  1363.     valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
  1364.     valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
  1365.     valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
  1366.     valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
  1367.     valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
  1368.     valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
  1369.     valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
  1370.     valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
  1371.     valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
  1372.     valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
  1373.     valueOf(0x41c21cb8e1000000L)};
  1374.  
  1375.  
  1376.     /**
  1377.      * These routines provide access to the two's complement representation
  1378.      * of BigIntegers.
  1379.      */
  1380.  
  1381.     /**
  1382.      * Returns the length of the two's complement representation in bytes,
  1383.      * including space for at least one sign bit, 
  1384.      */
  1385.     private int byteLength() {
  1386.     return bitLength()/8 + 1;
  1387.     }
  1388.  
  1389.     /* Returns sign bit */
  1390.     private int signBit() {
  1391.     return (signum < 0 ? 1 : 0);
  1392.     }
  1393.  
  1394.     /* Returns a byte of sign bits */
  1395.     private byte signByte() {
  1396.     return (byte) (signum < 0 ? -1 : 0);
  1397.     }
  1398.  
  1399.     /**
  1400.      * Returns the specified byte of the little-endian two's complement
  1401.      * representation (byte 0 is the LSB).  The byte number can be arbitrarily
  1402.      * high (values are logically preceded by infinitely many sign bytes).
  1403.      */
  1404.     private byte getByte(int n) {
  1405.     if (n >= magnitude.length)
  1406.         return signByte();
  1407.  
  1408.     byte magByte = magnitude[magnitude.length-n-1];
  1409.  
  1410.     return (byte) (signum >= 0 ? magByte :
  1411.                (n <= firstNonzeroByteNum() ? -magByte : ~magByte));
  1412.     }
  1413.  
  1414.     /**
  1415.      * Returns the index of the first nonzero byte in the little-endian 
  1416.      * binary representation of the magnitude (byte 0 is the LSB).  If
  1417.      * the magnitude is zero, return value is undefined.
  1418.      */
  1419.  
  1420.      private int firstNonzeroByteNum() {
  1421.     /*
  1422.      * Initialize bitCount field the first time this method is executed.
  1423.      * This method depends on the atomicity of int modifies; without
  1424.      * this guarantee, it would have to be synchronized.
  1425.      */
  1426.     if (firstNonzeroByteNum == -2) {
  1427.         /* Search for the first nonzero byte */
  1428.         int i;
  1429.         for (i=magnitude.length-1; i>=0 && magnitude[i]==0; i--)
  1430.         ;
  1431.         firstNonzeroByteNum = magnitude.length-i-1;
  1432.     }
  1433.     return firstNonzeroByteNum;
  1434.     }
  1435.  
  1436.  
  1437.     /**
  1438.      * Native method wrappers for Colin Plumb's big positive integer package.
  1439.      * Each of these wrappers (except for plumbInit) behaves as follows:
  1440.      *
  1441.      *     1) Translate input arguments from java byte arrays into plumbNums.
  1442.      *
  1443.      *  2) Perform the requested computation.
  1444.      *
  1445.      *  3) Translate result(s) into Java byte array(s).  (The subtract
  1446.      *       operation translates its result into a BigInteger, as its result
  1447.      *       is, effectively, signed.)
  1448.      *
  1449.      *    4) Deallocate all of the plumbNums.
  1450.      *
  1451.      *  5) Return the resulting Java array(s) (or, in the case of subtract,
  1452.      *       BigInteger).
  1453.      */
  1454.  
  1455.     private static native void plumbInit();
  1456.     private static native byte[] plumbAdd(byte[] a, byte[] b);
  1457.     private static native BigInteger plumbSubtract(byte[] a, byte[] b);
  1458.     private static native byte[] plumbMultiply(byte[] a, byte[] b);
  1459.     private static native byte[] plumbDivide(byte[] a, byte[] b);
  1460.     private static native byte[] plumbRemainder(byte[] a, byte[] b);
  1461.     private static native byte[][] plumbDivideAndRemainder(byte[] a, byte[] b);
  1462.     private static native byte[] plumbGcd(byte[] a, byte[] b);
  1463.     private static native byte[] plumbModPow(byte[] a, byte[] b, byte[] m);
  1464.     private static native byte[] plumbModInverse(byte[] a, byte[] m);
  1465.     private static native byte[] plumbSquare(byte[] a);
  1466.     private static native byte[] plumbGeneratePrime(byte[] a);
  1467.  
  1468.     /** use serialVersionUID from JDK 1.1. for interoperability */
  1469.     private static final long serialVersionUID = -8287574255936472291L;
  1470. }
  1471.