binaryinteger.java

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

	/**
	 * The BinaryInteger constant two. (Not exported.)
	 */
	private static final BinaryInteger TWO = valueOf(2);

	/**
	 * The BinaryInteger constant ten.
	 * 
	 * 
	 */
	public static final BinaryInteger TEN = valueOf(10);

	// Arithmetic Operations

	/**
	 * 加操作
	 * 
	 * @param val
	 *            value to be added to this BinaryInteger.
	 * @return <tt>this + val</tt>
	 */
	public BinaryInteger add(BinaryInteger val) {
		int[] resultMag;
		if (val.signum == 0)
			return this;
		if (signum == 0)
			return val;
		if (val.signum == signum)
			return new BinaryInteger(add(mag, val.mag), signum);

		int cmp = intArrayCmp(mag, val.mag);
		if (cmp == 0)
			return ZERO;
		resultMag = (cmp > 0 ? subtract(mag, val.mag) : subtract(val.mag, mag));
		resultMag = trustedStripLeadingZeroInts(resultMag);

		return new BinaryInteger(resultMag, cmp * signum);
	}

	/**
	 * 得到 x+y 的结果
	 */
	private static int[] add(int[] x, int[] y) {
		// If x is shorter, swap the two arrays
		if (x.length < y.length) {
			int[] tmp = x;
			x = y;
			y = tmp;
		}

		int xIndex = x.length;
		int yIndex = y.length;
		int result[] = new int[xIndex];
		long sum = 0;

		// Add common parts of both numbers
		while (yIndex > 0) {
			sum = (x[--xIndex] & LONG_MASK) + (y[--yIndex] & LONG_MASK)
					+ (sum >>> 32);
			result[xIndex] = (int) sum;
		}

		// Copy remainder of longer number while carry propagation is required
		boolean carry = (sum >>> 32 != 0);
		while (xIndex > 0 && carry)
			carry = ((result[--xIndex] = x[xIndex] + 1) == 0);

		// Copy remainder of longer number
		while (xIndex > 0)
			result[--xIndex] = x[xIndex];

		// Grow result if necessary
		if (carry) {
			int newLen = result.length + 1;
			int temp[] = new int[newLen];
			for (int i = 1; i < newLen; i++)
				temp[i] = result[i - 1];
			temp[0] = 0x01;
			result = temp;
		}
		return result;
	}

	/**
	 * 减操作
	 * 
	 * @param val
	 *            value to be subtracted from this BinaryInteger.
	 * @return <tt>this - val</tt>
	 */
	public BinaryInteger subtract(BinaryInteger val) {
		int[] resultMag;
		if (val.signum == 0)
			return this;
		if (signum == 0)
			return val.negate();
		if (val.signum != signum)
			return new BinaryInteger(add(mag, val.mag), signum);

		int cmp = intArrayCmp(mag, val.mag);
		if (cmp == 0)
			return ZERO;
		resultMag = (cmp > 0 ? subtract(mag, val.mag) : subtract(val.mag, mag));
		resultMag = trustedStripLeadingZeroInts(resultMag);
		return new BinaryInteger(resultMag, cmp * signum);
	}

	/**
	 * 得到 big-little的结果
	 */
	private static int[] subtract(int[] big, int[] little) {
		int bigIndex = big.length;
		int result[] = new int[bigIndex];
		int littleIndex = little.length;
		long difference = 0;

		// Subtract common parts of both numbers
		while (littleIndex > 0) {
			difference = (big[--bigIndex] & LONG_MASK)
					- (little[--littleIndex] & LONG_MASK) + (difference >> 32);
			result[bigIndex] = (int) difference;
		}

		// Subtract remainder of longer number while borrow propagates
		boolean borrow = (difference >> 32 != 0);
		while (bigIndex > 0 && borrow)
			borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);

		// Copy remainder of longer number
		while (bigIndex > 0)
			result[--bigIndex] = big[bigIndex];

		return result;
	}

	/**
	 * 乘操作
	 * 
	 * @param val
	 *            value to be multiplied by this BinaryInteger.
	 * @return <tt>this * val</tt>
	 */
	public BinaryInteger multiply(BinaryInteger val) {
		if (signum == 0 || val.signum == 0)
			return ZERO;

		int[] result = multiplyToLen(mag, mag.length, val.mag, val.mag.length,
				null);
		result = trustedStripLeadingZeroInts(result);
		return new BinaryInteger(result, signum * val.signum);
	}

	/**
	 * 得到 z=x*y
	 */
	private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
		int xstart = xlen - 1;
		int ystart = ylen - 1;

		if (z == null || z.length < (xlen + ylen))
			z = new int[xlen + ylen];

		long carry = 0;
		for (int j = ystart, k = ystart + 1 + xstart; j >= 0; j--, k--) {
			long product = (y[j] & LONG_MASK) * (x[xstart] & LONG_MASK) + carry;
			z[k] = (int) product;
			carry = product >>> 32;
		}
		z[xstart] = (int) carry;

		for (int i = xstart - 1; i >= 0; i--) {
			carry = 0;
			for (int j = ystart, k = ystart + 1 + i; j >= 0; j--, k--) {
				long product = (y[j] & LONG_MASK) * (x[i] & LONG_MASK)
						+ (z[k] & LONG_MASK) + carry;
				z[k] = (int) product;
				carry = product >>> 32;
			}
			z[i] = (int) carry;
		}
		return z;
	}

	/**
	 * 平方操作
	 * 
	 * @return <tt>this<sup>2</sup></tt>
	 */
	private BinaryInteger square() {
		if (signum == 0)
			return ZERO;
		int[] z = squareToLen(mag, mag.length, null);
		return new BinaryInteger(trustedStripLeadingZeroInts(z), 1);
	}

	/**
	 * Squares the contents of the int array x. The result is placed into the
	 * int array z. The contents of x are not changed.
	 */
	private static final int[] squareToLen(int[] x, int len, int[] z) {
		/*
		 * The algorithm used here is adapted from Colin Plumb's C library.
		 * Technique: Consider the partial products in the multiplication of
		 * "abcde" by itself:
		 * 
		 * a b c d e * a b c d e ================== ae be ce de ee ad bd cd dd
		 * de ac bc cc cd ce ab bb bc bd be aa ab ac ad ae
		 * 
		 * Note that everything above the main diagonal: ae be ce de = (abcd) *
		 * e ad bd cd = (abc) * d ac bc = (ab) * c ab = (a) * b
		 * 
		 * is a copy of everything below the main diagonal: de cd ce bc bd be ab
		 * ac ad ae
		 * 
		 * Thus, the sum is 2 * (off the diagonal) + diagonal.
		 * 
		 * This is accumulated beginning with the diagonal (which consist of the
		 * squares of the digits of the input), which is then divided by two,
		 * the off-diagonal added, and multiplied by two again. The low bit is
		 * simply a copy of the low bit of the input, so it doesn't need special
		 * care.
		 */
		int zlen = len << 1;
		if (z == null || z.length < zlen)
			z = new int[zlen];

		// Store the squares, right shifted one bit (i.e., divided by 2)
		int lastProductLowWord = 0;
		for (int j = 0, i = 0; j < len; j++) {
			long piece = (x[j] & LONG_MASK);
			long product = piece * piece;
			z[i++] = (lastProductLowWord << 31) | (int) (product >>> 33);
			z[i++] = (int) (product >>> 1);
			lastProductLowWord = (int) product;
		}

		// Add in off-diagonal sums
		for (int i = len, offset = 1; i > 0; i--, offset += 2) {
			int t = x[i - 1];
			t = mulAdd(z, x, offset, i - 1, t);
			addOne(z, offset - 1, i, t);
		}

		// Shift back up and set low bit
		primitiveLeftShift(z, zlen, 1);
		z[zlen - 1] |= x[len - 1] & 1;

		return z;
	}

	/**
	 * 除操作
	 * 
	 * @param val
	 *            value by which this BinaryInteger is to be divided.
	 * @return <tt>this / val</tt>
	 * @throws ArithmeticException
	 *             <tt>val==0</tt>
	 */
	public BinaryInteger divide(BinaryInteger val) {
		MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
				this.mag), b = new MutableBigInteger(val.mag);

		a.divide(b, q, r);
		return new BinaryInteger(q, this.signum * val.signum);
	}

	/**
	 * 除和取余操作合并
	 * 
	 * @param val
	 *            value by which this BinaryInteger is to be divided, and the
	 *            remainder computed.
	 * @return an array of two BigIntegers: the quotient <tt>(this / val)</tt>
	 *         is the initial element, and the remainder <tt>(this % val)</tt>
	 *         is the final element.
	 * @throws ArithmeticException
	 *             <tt>val==0</tt>
	 */
	public BinaryInteger[] divideAndRemainder(BinaryInteger val) {
		BinaryInteger[] result = new BinaryInteger[2];
		MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
				this.mag), b = new MutableBigInteger(val.mag);
		a.divide(b, q, r);
		result[0] = new BinaryInteger(q, this.signum * val.signum);
		result[1] = new BinaryInteger(r, this.signum);
		return result;
	}

	/**
	 * 取余操作
	 * 
	 * @param val
	 *            value by which this BinaryInteger is to be divided, and the
	 *            remainder computed.
	 * @return <tt>this % val</tt>
	 * @throws ArithmeticException
	 *             <tt>val==0</tt>
	 */
	public BinaryInteger remainder(BinaryInteger val) {
		MutableBigInteger q = new MutableBigInteger(), r = new MutableBigInteger(), a = new MutableBigInteger(
				this.mag), b = new MutableBigInteger(val.mag);

		a.divide(b, q, r);
		return new BinaryInteger(r, this.signum);
	}

	/**
	 * 指数操作
	 * 
	 * @param exponent
	 *            exponent to which this BinaryInteger is to be raised.
	 * @return <tt>this<sup>exponent</sup></tt>
	 * @throws ArithmeticException
	 *             <tt>exponent</tt> is negative. (This would cause the
	 *             operation to yield a non-integer value.)
	 */
	public BinaryInteger pow(int exponent) {
		if (exponent < 0)
			throw new ArithmeticException("Negative exponent");
		if (signum == 0)
			return (exponent == 0 ? ONE : this);

		// Perform exponentiation using repeated squaring trick
		int newSign = (signum < 0 && (exponent & 1) == 1 ? -1 : 1);
		int[] baseToPow2 = this.mag;
		int[] result = { 1 };

		while (exponent != 0) {
			if ((exponent & 1) == 1) {
				result = multiplyToLen(result, result.length, baseToPow2,
						baseToPow2.length, null);
				result = trustedStripLeadingZeroInts(result);
			}
			if ((exponent >>>= 1) != 0) {
				baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
				baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
			}
		}
		return new BinaryInteger(result, newSign);
	}

	/**
	 * 求最大公约数
	 * 
	 * @param val
	 *            value with which the GCD is to be computed.
	 * @return <tt>GCD(abs(this), abs(val))</tt>
	 */
	public BinaryInteger gcd(BinaryInteger val) {
		if (val.signum == 0)
			return this.abs();
		else if (this.signum == 0)
			return val.abs();

		MutableBigInteger a = new MutableBigInteger(this);
		MutableBigInteger b = new MutableBigInteger(val);

		MutableBigInteger result = a.hybridGCD(b);

		return new BinaryInteger(result, 1);
	}

	/**
	 * 左移运算
	 */
	private static int[] leftShift(int[] a, int len, int n) {
		int nInts = n >>> 5;
		int nBits = n & 0x1F;
		int bitsInHighWord = bitLen(a[0]);

		// If shift can be done without recopy, do so
		if (n <= (32 - bitsInHighWord)) {
			primitiveLeftShift(a, len, nBits);
			return a;
		} else { // Array must be resized
			if (nBits <= (32 - bitsInHighWord)) {
				int result[] = new int[nInts + len];
				for (int i = 0; i < len; i++)
					result[i] = a[i];
				primitiveLeftShift(result, result.length, nBits);
				return result;
			} else {
				int result[] = new int[nInts + len + 1];
				for (int i = 0; i < len; i++)
					result[i] = a[i];
				primitiveRightShift(result, result.length, 32 - nBits);
				return result;
			}
		}
	}

	// shifts a up to len right n bits assumes no leading zeros, 0<n<32
	static void primitiveRightShift(int[] a, int len, int n) {
		int n2 = 32 - n;
		for (int i = len - 1, c = a[i]; i > 0; i--) {
			int b = c;
			c = a[i - 1];
			a[i] = (c << n2) | (b >>> n);
		}
		a[0] >>>= n;
	}

	// shifts a up to len left n bits assumes no leading zeros, 0<=n<32
	static void primitiveLeftShift(int[] a, int len, int n) {
		if (len == 0 || n == 0)
			return;

		int n2 = 32 - n;
		for (int i = 0, c = a[i], m = i + len - 1; i < m; i++) {
			int b = c;
			c = a[i + 1];
			a[i] = (b << n) | (c >>> n2);
		}
		a[len - 1] <<= n;
	}

	/**
	 * Calculate bitlength of contents of the first len elements an int array,
	 * assuming there are no leading zero ints.
	 */
	private static int bitLength(int[] val, int len) {
		if (len == 0)
			return 0;
		return ((len - 1) << 5) + bitLen(val[0]);
	}

	/**
	 * 取绝对值
	 * 
	 * @return <tt>abs(this)</tt>
	 */
	public BinaryInteger abs() {
		return (signum >= 0 ? this : this.negate());
	}

	/**
	 * 取相反数
	 * 
	 * @return <tt>-this</tt>
	 */
	public BinaryInteger negate() {
		return new BinaryInteger(this.mag, -this.signum);
	}

	/**
	 * 得到符号位
	 * 
	 * @return -1, 0 or 1 as the value of this BinaryInteger is negative, zero
	 *         or positive.
	 */
	public int signum() {
		return this.signum;
	}

	// Modular Arithmetic Operations