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