biginteger.java

整体思路 用createkey.java 文件来产生秘钥

/*
 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

/*
 * @(#)BigInteger.java	1.70 05/08/09
 */

package java.math;

import java.util.Random;
import java.io.*;

/**
 * Immutable arbitrary-precision integers.  All operations behave as if
 * BigIntegers were represented in two's-complement notation (like Java's
 * primitive integer types).  BigInteger provides analogues to all of Java's
 * primitive integer operators, and all relevant methods from java.lang.Math.
 * Additionally, BigInteger provides operations for modular arithmetic, GCD
 * calculation, primality testing, prime generation, bit manipulation,
 * and a few other miscellaneous operations.
 * <p>
 * Semantics of arithmetic operations exactly mimic those of Java's integer
 * arithmetic operators, as defined in <i>The Java Language Specification</i>.
 * For example, division by zero throws an <tt>ArithmeticException</tt>, and
 * division of a negative by a positive yields a negative (or zero) remainder.
 * All of the details in the Spec concerning overflow are ignored, as
 * BigIntegers are made as large as necessary to accommodate the results of an
 * operation.
 * <p>
 * Semantics of shift operations extend those of Java's shift operators
 * to allow for negative shift distances.  A right-shift with a negative
 * shift distance results in a left shift, and vice-versa.  The unsigned
 * right shift operator (&gt;&gt;&gt;) is omitted, as this operation makes
 * little sense in combination with the "infinite word size" abstraction
 * provided by this class.
 * <p>
 * Semantics of bitwise logical operations exactly mimic those of Java's
 * bitwise integer operators.  The binary operators (<tt>and</tt>,
 * <tt>or</tt>, <tt>xor</tt>) implicitly perform sign extension on the shorter
 * of the two operands prior to performing the operation.
 * <p>
 * Comparison operations perform signed integer comparisons, analogous to
 * those performed by Java's relational and equality operators.
 * <p>
 * Modular arithmetic operations are provided to compute residues, perform
 * exponentiation, and compute multiplicative inverses.  These methods always
 * return a non-negative result, between <tt>0</tt> and <tt>(modulus - 1)</tt>,
 * inclusive.
 * <p>
 * Bit operations operate on a single bit of the two's-complement
 * representation of their operand.  If necessary, the operand is sign-
 * extended so that it contains the designated bit.  None of the single-bit
 * operations can produce a BigInteger with a different sign from the
 * BigInteger being operated on, as they affect only a single bit, and the
 * "infinite word size" abstraction provided by this class ensures that there
 * are infinitely many "virtual sign bits" preceding each BigInteger.
 * <p>
 * For the sake of brevity and clarity, pseudo-code is used throughout the
 * descriptions of BigInteger methods.  The pseudo-code expression
 * <tt>(i + j)</tt> is shorthand for "a BigInteger whose value is
 * that of the BigInteger <tt>i</tt> plus that of the BigInteger <tt>j</tt>."
 * The pseudo-code expression <tt>(i == j)</tt> is shorthand for
 * "<tt>true</tt> if and only if the BigInteger <tt>i</tt> represents the same
 * value as the BigInteger <tt>j</tt>."  Other pseudo-code expressions are
 * interpreted similarly.
 * <p>
 * All methods and constructors in this class throw
 * <CODE>NullPointerException</CODE> when passed
 * a null object reference for any input parameter.
 *
 * @see     BigDecimal
 * @version 1.70, 08/09/05
 * @author  Josh Bloch
 * @author  Michael McCloskey
 * @since JDK1.1
 */

public class BigInteger extends Number implements Comparable<BigInteger> {
    /**
     * The signum of this BigInteger: -1 for negative, 0 for zero, or
     * 1 for positive.  Note that the BigInteger zero <i>must</i> have
     * a signum of 0.  This is necessary to ensures that there is exactly one
     * representation for each BigInteger value.
     *
     * @serial
     */
    int signum;

    /**
     * The magnitude of this BigInteger, in <i>big-endian</i> order: the
     * zeroth element of this array is the most-significant int of the
     * magnitude.  The magnitude must be "minimal" in that the most-significant
     * int (<tt>mag[0]</tt>) must be non-zero.  This is necessary to
     * ensure that there is exactly one representation for each BigInteger
     * value.  Note that this implies that the BigInteger zero has a
     * zero-length mag array.
     */
    int[] mag;

    // These "redundant fields" are initialized with recognizable nonsense
    // values, and cached the first time they are needed (or never, if they
    // aren't needed).

    /**
     * The bitCount of this BigInteger, as returned by bitCount(), or -1
     * (either value is acceptable).
     *
     * @serial
     * @see #bitCount
     */
    private int bitCount =  -1;

    /**
     * The bitLength of this BigInteger, as returned by bitLength(), or -1
     * (either value is acceptable).
     *
     * @serial
     * @see #bitLength
     */
    private int bitLength = -1;

    /**
     * The lowest set bit of this BigInteger, as returned by getLowestSetBit(),
     * or -2 (either value is acceptable).
     *
     * @serial
     * @see #getLowestSetBit
     */
    private int lowestSetBit = -2;

    /**
     * The index of the lowest-order byte in the magnitude of this BigInteger
     * that contains a nonzero byte, or -2 (either value is acceptable).  The
     * least significant byte has int-number 0, the next byte in order of
     * increasing significance has byte-number 1, and so forth.
     *
     * @serial
     */
    private int firstNonzeroByteNum = -2;

    /**
     * The index of the lowest-order int in the magnitude of this BigInteger
     * that contains a nonzero int, or -2 (either value is acceptable).  The
     * least significant int has int-number 0, the next int in order of
     * increasing significance has int-number 1, and so forth.
     */
    private int firstNonzeroIntNum = -2;

    /**
     * This mask is used to obtain the value of an int as if it were unsigned.
     */
    private final static long LONG_MASK = 0xffffffffL;

    //Constructors

    /**
     * Translates a byte array containing the two's-complement binary
     * representation of a BigInteger into a BigInteger.  The input array is
     * assumed to be in <i>big-endian</i> byte-order: the most significant
     * byte is in the zeroth element.
     *
     * @param  val big-endian two's-complement binary representation of
     *	       BigInteger.
     * @throws NumberFormatException <tt>val</tt> is zero bytes long.
     */
    public BigInteger(byte[] val) {
	if (val.length == 0)
	    throw new NumberFormatException("Zero length BigInteger");

	if (val[0] < 0) {
            mag = makePositive(val);
	    signum = -1;
	} else {
	    mag = stripLeadingZeroBytes(val);
	    signum = (mag.length == 0 ? 0 : 1);
	}
    }

    /**
     * This private constructor translates an int array containing the
     * two's-complement binary representation of a BigInteger into a
     * BigInteger. The input array is assumed to be in <i>big-endian</i>
     * int-order: the most significant int is in the zeroth element.
     */
    private BigInteger(int[] val) {
	if (val.length == 0)
	    throw new NumberFormatException("Zero length BigInteger");

	if (val[0] < 0) {
            mag = makePositive(val);
	    signum = -1;
	} else {
	    mag = trustedStripLeadingZeroInts(val);
	    signum = (mag.length == 0 ? 0 : 1);
	}
    }

    /**
     * Translates the sign-magnitude representation of a BigInteger into a
     * BigInteger.  The sign is represented as an integer signum value: -1 for
     * negative, 0 for zero, or 1 for positive.  The magnitude is a byte array
     * in <i>big-endian</i> byte-order: the most significant byte is in the
     * zeroth element.  A zero-length magnitude array is permissible, and will
     * result inin a BigInteger value of 0, whether signum is -1, 0 or 1.
     *
     * @param  signum signum of the number (-1 for negative, 0 for zero, 1
     * 	       for positive).
     * @param  magnitude big-endian binary representation of the magnitude of
     * 	       the number.
     * @throws NumberFormatException <tt>signum</tt> is not one of the three
     *	       legal values (-1, 0, and 1), or <tt>signum</tt> is 0 and
     *	       <tt>magnitude</tt> contains one or more non-zero bytes.
     */
    public BigInteger(int signum, byte[] magnitude) {
	this.mag = stripLeadingZeroBytes(magnitude);

	if (signum < -1 || signum > 1)
	    throw(new NumberFormatException("Invalid signum value"));

	if (this.mag.length==0) {
	    this.signum = 0;
	} else {
	    if (signum == 0)
		throw(new NumberFormatException("signum-magnitude mismatch"));
	    this.signum = signum;
	}
    }

    /**
     * A constructor for internal use that translates the sign-magnitude
     * representation of a BigInteger into a BigInteger. It checks the
     * arguments and copies the magnitude so this constructor would be
     * safe for external use.
     */
    private BigInteger(int signum, int[] magnitude) {
	this.mag = stripLeadingZeroInts(magnitude);

	if (signum < -1 || signum > 1)
	    throw(new NumberFormatException("Invalid signum value"));

	if (this.mag.length==0) {
	    this.signum = 0;
	} else {
	    if (signum == 0)
		throw(new NumberFormatException("signum-magnitude mismatch"));
	    this.signum = signum;
	}
    }

    /**
     * Translates the String representation of a BigInteger in the specified
     * radix into a BigInteger.  The String representation consists of an
     * optional minus sign followed by a sequence of one or more digits in the
     * specified radix.  The character-to-digit mapping is provided by
     * <tt>Character.digit</tt>.  The String may not contain any extraneous
     * characters (whitespace, for example).
     *
     * @param val String representation of BigInteger.
     * @param radix radix to be used in interpreting <tt>val</tt>.
     * @throws NumberFormatException <tt>val</tt> is not a valid representation
     *	       of a BigInteger in the specified radix, or <tt>radix</tt> is
     *	       outside the range from {@link Character#MIN_RADIX} to
     *	       {@link Character#MAX_RADIX}, inclusive.
     * @see    Character#digit
     */
    public BigInteger(String val, int radix) {
	int cursor = 0, numDigits;
        int len = val.length();

	if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
	    throw new NumberFormatException("Radix out of range");
	if (val.length() == 0)
	    throw new NumberFormatException("Zero length BigInteger");

	// Check for minus sign
	signum = 1;
        int index = val.lastIndexOf("-");
        if (index != -1) {
            if (index == 0) {
                if (val.length() == 1)
                    throw new NumberFormatException("Zero length BigInteger");
                signum = -1;
                cursor = 1;
            } else {
                throw new NumberFormatException("Illegal embedded minus sign");
            }
        }

        // Skip leading zeros and compute number of digits in magnitude
	while (cursor < len &&
               Character.digit(val.charAt(cursor),radix) == 0)
	    cursor++;
	if (cursor == len) {
	    signum = 0;
	    mag = ZERO.mag;
	    return;
	} else {
	    numDigits = len - cursor;
	}

        // Pre-allocate array of expected size. May be too large but can
        // never be too small. Typically exact.
        int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1);
        int numWords = (numBits + 31) /32;
        mag = new int[numWords];

	// Process first (potentially short) digit group
	int firstGroupLen = numDigits % digitsPerInt[radix];
	if (firstGroupLen == 0)
	    firstGroupLen = digitsPerInt[radix];
	String group = val.substring(cursor, cursor += firstGroupLen);
        mag[mag.length - 1] = Integer.parseInt(group, radix);
	if (mag[mag.length - 1] < 0)
	    throw new NumberFormatException("Illegal digit");
        
	// Process remaining digit groups
        int superRadix = intRadix[radix];
        int groupVal = 0;
	while (cursor < val.length()) {
	    group = val.substring(cursor, cursor += digitsPerInt[radix]);
	    groupVal = Integer.parseInt(group, radix);
	    if (groupVal < 0)
		throw new NumberFormatException("Illegal digit");
            destructiveMulAdd(mag, superRadix, groupVal);
	}
        // Required for cases where the array was overallocated.
        mag = trustedStripLeadingZeroInts(mag);
    }

    // Constructs a new BigInteger using a char array with radix=10
    BigInteger(char[] val) {
        int cursor = 0, numDigits;
        int len = val.length;

	// Check for leading minus sign
	signum = 1;
	if (val[0] == '-') {
	    if (len == 1)
		throw new NumberFormatException("Zero length BigInteger");
	    signum = -1;
	    cursor = 1;
	}

        // Skip leading zeros and compute number of digits in magnitude
	while (cursor < len && Character.digit(val[cursor], 10) == 0)
	    cursor++;
	if (cursor == len) {
	    signum = 0;
	    mag = ZERO.mag;
	    return;
	} else {
	    numDigits = len - cursor;
	}

        // Pre-allocate array of expected size
        int numWords;
        if (len < 10) {
            numWords = 1;
        } else {    
            int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);
            numWords = (numBits + 31) /32;
        }
        mag = new int[numWords];
 
	// Process first (potentially short) digit group
	int firstGroupLen = numDigits % digitsPerInt[10];
	if (firstGroupLen == 0)
	    firstGroupLen = digitsPerInt[10];
        mag[mag.length-1] = parseInt(val, cursor,  cursor += firstGroupLen);
        
	// Process remaining digit groups
	while (cursor < len) {
	    int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
            destructiveMulAdd(mag, intRadix[10], groupVal);
	}
        mag = trustedStripLeadingZeroInts(mag);