binaryinteger.java

非常完整的rsa加密解密软件 有多完整？自己看吧

/******************************************************
 *COPYRIGHT@author YIMINGHE , 创建日期 : 2005-12-10
 *
 *         @FUDAN UNIVERSITY
 *
 *Email : [e-mail],[e-mail]
 *
 *MSN   : [e-mail] 
 *
 *TODO
 ******************************************************/

package tool;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.ObjectStreamField;
import java.util.Random;

/**
 * 可表示任意大的整数，位运算效率也不差。
 * 
 * 
 */
public class BinaryInteger extends Number implements Comparable<BinaryInteger> {
	/**
	 * -1,代表负数，1，代表正数，0，表示 0 只能取这三个数
	 * 
	 * @serial
	 */
	int signum;

	/**
	 * 二进制的存放处，若为负数，则取补存储，用整数32位存储，利用位操作来运算， 0位置存放最高位的
	 */
	int[] mag;

	/**
	 * 存放的二进制位数
	 * 
	 * @serial
	 * @see #bitCount
	 */
	private int bitCount = -1;

	/**
	 * 存放的二进制位数
	 * 
	 * @serial
	 * @see #bitLength
	 */
	private int bitLength = -1;

	/**
	 * 最低二进制位数所在的整数数组位置
	 * 
	 * @serial
	 * @see #getLowestSetBit
	 */
	private int lowestSetBit = -2;

	/**
	 * 字节数组中第一个不是零的位置
	 * 
	 * @serial
	 */
	private int firstNonzeroByteNum = -2;

	/**
	 * 整数数组中第一个不是零的位置
	 */
	private int firstNonzeroIntNum = -2;

	/**
	 * 用位操作来得到整数的无符号表示
	 */
	private final static long LONG_MASK = 0xffffffffL;

	// Constructors

	/**
	 * 从字节数数组中得到，0字节组存放最高位，补码表示
	 * 
	 * @param val
	 *            big-endian two's-complement binary representation of
	 *            BinaryInteger.
	 * @throws NumberFormatException
	 *             <tt>val</tt> is zero bytes long.
	 */
	public BinaryInteger(byte[] val) {
		if (val.length == 0)
			throw new NumberFormatException("Zero length BinaryInteger");

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

	/**
	 * 从整数数数组中得到，0字节组存放最高位，补码表示
	 */
	private BinaryInteger(int[] val) {
		if (val.length == 0)
			throw new NumberFormatException("Zero length BinaryInteger");

		if (val[0] < 0) {
			mag = makePositive(val);
			signum = -1;
		} else {
			mag = trustedStripLeadingZeroInts(val);
			signum = (mag.length == 0 ? 0 : 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 BinaryInteger(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;
		}
	}

	/**
	 * 由正数的二进制整数表示和符号未来组建
	 */
	private BinaryInteger(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;
		}
	}

	/**
	 * 由数字字符串和他的进制数来组建
	 * 
	 * @param val
	 *            String representation of BinaryInteger.
	 * @param radix
	 *            radix to be used in interpreting <tt>val</tt>.
	 * @throws NumberFormatException
	 *             <tt>val</tt> is not a valid representation of a
	 *             BinaryInteger 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 BinaryInteger(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 BinaryInteger");

		// 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 BinaryInteger");
				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);
	}

	/**
	 * 由正数的十进制字符表示来组建
	 * 
	 * @param val
	 */
	BinaryInteger(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 BinaryInteger");
			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);
	}

	// 有一个数字字符数组，有它的开始位置和结束位置得到所表示的整数值
	private int parseInt(char[] source, int start, int end) {
		int result = Character.digit(source[start++], 10);
		if (result == -1)
			throw new NumberFormatException(new String(source));

		for (int index = start; index < end; index++) {
			int nextVal = Character.digit(source[index], 10);
			if (nextVal == -1)
				throw new NumberFormatException(new String(source));
			result = 10 * result + nextVal;
		}

		return result;
	}

	// bitsPerDigit in the given radix times 1024
	// Rounded up to avoid underallocation.
	private static long bitsPerDigit[] = { 0, 0, 1024, 1624, 2048, 2378, 2648,
			2875, 3072, 3247, 3402, 3543, 3672, 3790, 3899, 4001, 4096, 4186,
			4271, 4350, 4426, 4498, 4567, 4633, 4696, 4756, 4814, 4870, 4923,
			4975, 5025, 5074, 5120, 5166, 5210, 5253, 5295 };

	// 得到x*y+z的结果
	private static void destructiveMulAdd(int[] x, int y, int z) {
		// Perform the multiplication word by word
		long ylong = y & LONG_MASK;
		long zlong = z & LONG_MASK;
		int len = x.length;

		long product = 0;
		long carry = 0;
		for (int i = len - 1; i >= 0; i--) {
			product = ylong * (x[i] & LONG_MASK) + carry;
			x[i] = (int) product;
			carry = product >>> 32;
		}

		// Perform the addition
		long sum = (x[len - 1] & LONG_MASK) + zlong;
		x[len - 1] = (int) sum;
		carry = sum >>> 32;
		for (int i = len - 2; i >= 0; i--) {
			sum = (x[i] & LONG_MASK) + carry;
			x[i] = (int) sum;
			carry = sum >>> 32;
		}
	}

	/**
	 * 又是进制的字符串表示得到
	 * 
	 * @param val
	 *            decimal String representation of BinaryInteger.
	 * @throws NumberFormatException
	 *             <tt>val</tt> is not a valid representation of a
	 *             BinaryInteger.
	 * @see Character#digit
	 */
	public BinaryInteger(String val) {
		this(val, 10);
	}

	/**
	 * 随机产生numbits位的代表二进制的
	 * 
	 * @param numBits
	 *            maximum bitLength of the new BinaryInteger.
	 * @param rnd
	 *            source of randomness to be used in computing the new
	 *            BinaryInteger.
	 * @throws IllegalArgumentException
	 *             <tt>numBits</tt> is negative.
	 * @see #bitLength
	 */
	public BinaryInteger(int numBits, Random rnd) {
		this(1, randomBits(numBits, rnd));
	}

	private static byte[] randomBits(int numBits, Random rnd) {
		if (numBits < 0)
			throw new IllegalArgumentException("numBits must be non-negative");
		int numBytes = (numBits + 7) / 8;
		byte[] randomBits = new byte[numBytes];

		// Generate random bytes and mask out any excess bits
		if (numBytes > 0) {
			rnd.nextBytes(randomBits);
			int excessBits = 8 * numBytes - numBits;
			randomBits[0] &= (1 << (8 - excessBits)) - 1;
		}
		return randomBits;
	}

	/**
	 * 有一定的确定性产生 bitlength长的二进制素数
	 * 
	 * @param bitLength
	 *            bitLength of the returned BinaryInteger.
	 * @param certainty
	 *            a measure of the uncertainty that the caller is willing to
	 *            tolerate. The probability that the new BinaryInteger
	 *            represents a prime number will exceed
	 *            <tt>(1 - 1/2<sup>certainty</sup></tt>). The execution
	 *            time of this constructor is proportional to the value of this
	 *            parameter.
	 * @param rnd
	 *            source of random bits used to select candidates to be tested
	 *            for primality.
	 * @throws ArithmeticException
	 *             <tt>bitLength &lt; 2</tt>.
	 * @see #bitLength
	 */
	public BinaryInteger(int bitLength, int certainty, Random rnd) {
		BinaryInteger prime;

		if (bitLength < 2)
			throw new ArithmeticException("bitLength < 2");
		// The cutoff of 95 was chosen empirically for best performance
		prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
				: largePrime(bitLength, certainty, rnd));
		signum = 1;
		mag = prime.mag;
	}

	// Minimum size in bits that the requested prime number has
	// before we use the large prime number generating algorithms
	private static final int SMALL_PRIME_THRESHOLD = 95;

	// Certainty required to meet the spec of probablePrime
	private static final int DEFAULT_PRIME_CERTAINTY = 100;

	/**
	 * 产生素数
	 * 
	 * @param bitLength
	 *            bitLength of the returned BinaryInteger.
	 * @param rnd
	 *            source of random bits used to select candidates to be tested
	 *            for primality.
	 * @return a BinaryInteger of <tt>bitLength</tt> bits that is probably
	 *         prime
	 * @throws ArithmeticException
	 *             <tt>bitLength &lt; 2</tt>.
	 * @see #bitLength
	 */
	public static BinaryInteger probablePrime(int bitLength, Random rnd) {
		if (bitLength < 2)
			throw new ArithmeticException("bitLength < 2");

		// The cutoff of 95 was chosen empirically for best performance
		return (bitLength < SMALL_PRIME_THRESHOLD ? smallPrime(bitLength,
				DEFAULT_PRIME_CERTAINTY, rnd) : largePrime(bitLength,
				DEFAULT_PRIME_CERTAINTY, rnd));
	}

	/**
	 * 小素数的产生法
	 * 
	 * This method assumes bitLength > 1.