binaryinteger.java

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

	 */
	private static BinaryInteger smallPrime(int bitLength, int certainty,
			Random rnd) {
		int magLen = (bitLength + 31) >>> 5;
		int temp[] = new int[magLen];
		int highBit = 1 << ((bitLength + 31) & 0x1f); // High bit of high int
		int highMask = (highBit << 1) - 1; // Bits to keep in high int

		while (true) {
			// Construct a candidate
			for (int i = 0; i < magLen; i++)
				temp[i] = rnd.nextInt();
			temp[0] = (temp[0] & highMask) | highBit; // Ensure exact length
			if (bitLength > 2)
				temp[magLen - 1] |= 1; // Make odd if bitlen > 2

			BinaryInteger p = new BinaryInteger(temp, 1);

			// Do cheap "pre-test" if applicable
			if (bitLength > 6) {
				long r = p.remainder(SMALL_PRIME_PRODUCT).longValue();
				if ((r % 3 == 0) || (r % 5 == 0) || (r % 7 == 0)
						|| (r % 11 == 0) || (r % 13 == 0) || (r % 17 == 0)
						|| (r % 19 == 0) || (r % 23 == 0) || (r % 29 == 0)
						|| (r % 31 == 0) || (r % 37 == 0) || (r % 41 == 0))
					continue; // Candidate is composite; try another
			}

			// All candidates of bitLength 2 and 3 are prime by this point
			if (bitLength < 4)
				return p;

			// Do expensive test if we survive pre-test (or it's inapplicable)
			if (p.primeToCertainty(certainty))
				return p;
		}
	}

	private static final BinaryInteger SMALL_PRIME_PRODUCT = valueOf(3L * 5 * 7
			* 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41);

	/**
	 * 大素数的产生法
	 */
	private static BinaryInteger largePrime(int bitLength, int certainty,
			Random rnd) {
		BinaryInteger p;
		p = new BinaryInteger(bitLength, rnd).setBit(bitLength - 1);
		p.mag[p.mag.length - 1] &= 0xfffffffe;

		// Use a sieve length likely to contain the next prime number
		int searchLen = (bitLength / 20) * 64;
		BitSieve searchSieve = new BitSieve(p, searchLen);
		BinaryInteger candidate = searchSieve.retrieve(p, certainty);

		while ((candidate == null) || (candidate.bitLength() != bitLength)) {
			p = p.add(BinaryInteger.valueOf(2 * searchLen));
			if (p.bitLength() != bitLength)
				p = new BinaryInteger(bitLength, rnd).setBit(bitLength - 1);
			p.mag[p.mag.length - 1] &= 0xfffffffe;
			searchSieve = new BitSieve(p, searchLen);
			candidate = searchSieve.retrieve(p, certainty);
		}
		return candidate;
	}

	/**
	 * Returns the first integer greater than this <code>BinaryInteger</code>
	 * that is probably prime. The probability that the number returned by this
	 * method is composite does not exceed 2<sup>-100</sup>. This method will
	 * never skip over a prime when searching: if it returns <tt>p</tt>,
	 * there is no prime <tt>q</tt> such that <tt>this &lt; q &lt; p</tt>.
	 * 
	 * @return the first integer greater than this <code>BinaryInteger</code>
	 *         that is probably prime.
	 * @throws ArithmeticException
	 *             <tt>this &lt; 0</tt>.
	 * @since 1.5
	 */
	public BinaryInteger nextProbablePrime() {
		if (this.signum < 0)
			throw new ArithmeticException("start < 0: " + this);

		// Handle trivial cases
		if ((this.signum == 0) || this.equals(ONE))
			return TWO;

		BinaryInteger result = this.add(ONE);

		// Fastpath for small numbers
		if (result.bitLength() < SMALL_PRIME_THRESHOLD) {

			// Ensure an odd number
			if (!result.testBit(0))
				result = result.add(ONE);

			while (true) {
				// Do cheap "pre-test" if applicable
				if (result.bitLength() > 6) {
					long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
					if ((r % 3 == 0) || (r % 5 == 0) || (r % 7 == 0)
							|| (r % 11 == 0) || (r % 13 == 0) || (r % 17 == 0)
							|| (r % 19 == 0) || (r % 23 == 0) || (r % 29 == 0)
							|| (r % 31 == 0) || (r % 37 == 0) || (r % 41 == 0)) {
						result = result.add(TWO);
						continue; // Candidate is composite; try another
					}
				}

				// All candidates of bitLength 2 and 3 are prime by this point
				if (result.bitLength() < 4)
					return result;

				// The expensive test
				if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY))
					return result;

				result = result.add(TWO);
			}
		}

		// Start at previous even number
		if (result.testBit(0))
			result = result.subtract(ONE);

		// Looking for the next large prime
		int searchLen = (result.bitLength() / 20) * 64;

		while (true) {
			BitSieve searchSieve = new BitSieve(result, searchLen);
			BinaryInteger candidate = searchSieve.retrieve(result,
					DEFAULT_PRIME_CERTAINTY);
			if (candidate != null)
				return candidate;
			result = result.add(BinaryInteger.valueOf(2 * searchLen));
		}
	}

	/**
	 * Returns <tt>true</tt> if this BinaryInteger is probably prime,
	 * <tt>false</tt> if it's definitely composite.
	 * 
	 * This method assumes bitLength > 2.
	 * 
	 * @param certainty
	 *            a measure of the uncertainty that the caller is willing to
	 *            tolerate: if the call returns <tt>true</tt> the probability
	 *            that this BinaryInteger is prime exceeds
	 *            <tt>(1 - 1/2<sup>certainty</sup>)</tt>. The execution
	 *            time of this method is proportional to the value of this
	 *            parameter.
	 * @return <tt>true</tt> if this BinaryInteger is probably prime,
	 *         <tt>false</tt> if it's definitely composite.
	 */
	boolean primeToCertainty(int certainty) {
		int rounds = 0;
		int n = (Math.min(certainty, Integer.MAX_VALUE - 1) + 1) / 2;

		// The relationship between the certainty and the number of rounds
		// we perform is given in the draft standard ANSI X9.80, "PRIME
		// NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
		int sizeInBits = this.bitLength();
		if (sizeInBits < 100) {
			rounds = 50;
			rounds = n < rounds ? n : rounds;
			return passesMillerRabin(rounds);
		}

		if (sizeInBits < 256) {
			rounds = 27;
		} else if (sizeInBits < 512) {
			rounds = 15;
		} else if (sizeInBits < 768) {
			rounds = 8;
		} else if (sizeInBits < 1024) {
			rounds = 4;
		} else {
			rounds = 2;
		}
		rounds = n < rounds ? n : rounds;

		return passesMillerRabin(rounds) && passesLucasLehmer();
	}

	/**
	 * Returns true iff this BinaryInteger is a Lucas-Lehmer probable prime.
	 * 
	 * The following assumptions are made: This BinaryInteger is a positive, odd
	 * number.
	 */
	private boolean passesLucasLehmer() {
		BinaryInteger thisPlusOne = this.add(ONE);

		// Step 1
		int d = 5;
		while (jacobiSymbol(d, this) != -1) {
			// 5, -7, 9, -11, ...
			d = (d < 0) ? Math.abs(d) + 2 : -(d + 2);
		}

		// Step 2
		BinaryInteger u = lucasLehmerSequence(d, thisPlusOne, this);

		// Step 3
		return u.mod(this).equals(ZERO);
	}

	/**
	 * Computes Jacobi(p,n). Assumes n positive, odd, n>=3.
	 */
	private static int jacobiSymbol(int p, BinaryInteger n) {
		if (p == 0)
			return 0;

		// Algorithm and comments adapted from Colin Plumb's C library.
		int j = 1;
		int u = n.mag[n.mag.length - 1];

		// Make p positive
		if (p < 0) {
			p = -p;
			int n8 = u & 7;
			if ((n8 == 3) || (n8 == 7))
				j = -j; // 3 (011) or 7 (111) mod 8
		}

		// Get rid of factors of 2 in p
		while ((p & 3) == 0)
			p >>= 2;
		if ((p & 1) == 0) {
			p >>= 1;
			if (((u ^ (u >> 1)) & 2) != 0)
				j = -j; // 3 (011) or 5 (101) mod 8
		}
		if (p == 1)
			return j;
		// Then, apply quadratic reciprocity
		if ((p & u & 2) != 0) // p = u = 3 (mod 4)?
			j = -j;
		// And reduce u mod p
		u = n.mod(BinaryInteger.valueOf(p)).intValue();

		// Now compute Jacobi(u,p), u < p
		while (u != 0) {
			while ((u & 3) == 0)
				u >>= 2;
			if ((u & 1) == 0) {
				u >>= 1;
				if (((p ^ (p >> 1)) & 2) != 0)
					j = -j; // 3 (011) or 5 (101) mod 8
			}
			if (u == 1)
				return j;
			// Now both u and p are odd, so use quadratic reciprocity
			assert (u < p);
			int t = u;
			u = p;
			p = t;
			if ((u & p & 2) != 0) // u = p = 3 (mod 4)?
				j = -j;
			// Now u >= p, so it can be reduced
			u %= p;
		}
		return 0;
	}

	private static BinaryInteger lucasLehmerSequence(int z, BinaryInteger k,
			BinaryInteger n) {
		BinaryInteger d = BinaryInteger.valueOf(z);
		BinaryInteger u = ONE;
		BinaryInteger u2;
		BinaryInteger v = ONE;
		BinaryInteger v2;

		for (int i = k.bitLength() - 2; i >= 0; i--) {
			u2 = u.multiply(v).mod(n);

			v2 = v.square().add(d.multiply(u.square())).mod(n);
			if (v2.testBit(0)) {
				v2 = n.subtract(v2);
				v2.signum = -v2.signum;
			}
			v2 = v2.shiftRight(1);

			u = u2;
			v = v2;
			if (k.testBit(i)) {
				u2 = u.add(v).mod(n);
				if (u2.testBit(0)) {
					u2 = n.subtract(u2);
					u2.signum = -u2.signum;
				}
				u2 = u2.shiftRight(1);

				v2 = v.add(d.multiply(u)).mod(n);
				if (v2.testBit(0)) {
					v2 = n.subtract(v2);
					v2.signum = -v2.signum;
				}
				v2 = v2.shiftRight(1);

				u = u2;
				v = v2;
			}
		}
		return u;
	}

	/**
	 * miller -rabin 检测素数法
	 * 
	 * The following assumptions are made: This BinaryInteger is a positive, odd
	 * number greater than 2. iterations<=50.
	 */
	private boolean passesMillerRabin(int iterations) {
		// Find a and m such that m is odd and this == 1 + 2**a * m
		BinaryInteger thisMinusOne = this.subtract(ONE);
		BinaryInteger m = thisMinusOne;
		int a = m.getLowestSetBit();
		m = m.shiftRight(a);

		// Do the tests
		Random rnd = new Random();
		for (int i = 0; i < iterations; i++) {
			// Generate a uniform random on (1, this)
			BinaryInteger b;
			do {
				b = new BinaryInteger(this.bitLength(), rnd);
			} while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);

			int j = 0;
			BinaryInteger z = b.modPow(m, this);
			while (!((j == 0 && z.equals(ONE)) || z.equals(thisMinusOne))) {
				if (j > 0 && z.equals(ONE) || ++j == a)
					return false;
				z = z.modPow(TWO, this);
			}
		}
		return true;
	}

	/**
	 * 由正数的整数数组表示和符号位来组建
	 */
	private BinaryInteger(int[] magnitude, int signum) {
		this.signum = (magnitude.length == 0 ? 0 : signum);
		this.mag = magnitude;
	}

	/**
	 * 由正数的字节数组表示和符号位来组建
	 */
	private BinaryInteger(byte[] magnitude, int signum) {
		this.signum = (magnitude.length == 0 ? 0 : signum);
		this.mag = stripLeadingZeroBytes(magnitude);
	}

	/**
	 * 引用java类库
	 */
	BinaryInteger(MutableBigInteger val, int sign) {
		if (val.offset > 0 || val.value.length != val.intLen) {
			mag = new int[val.intLen];
			for (int i = 0; i < val.intLen; i++)
				mag[i] = val.value[val.offset + i];
		} else {
			mag = val.value;
		}

		this.signum = (val.intLen == 0) ? 0 : sign;
	}

	// Static Factory Methods

	/**
	 * 由长整形得到
	 * 
	 * @param val
	 *            value of the BinaryInteger to return.
	 * @return a BinaryInteger with the specified value.
	 */
	public static BinaryInteger valueOf(long val) {
		// If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
		if (val == 0)
			return ZERO;
		if (val > 0 && val <= MAX_CONSTANT)
			return posConst[(int) val];
		else if (val < 0 && val >= -MAX_CONSTANT)
			return negConst[(int) -val];

		return new BinaryInteger(val);
	}

	/**
	 * Constructs a BinaryInteger with the specified value, which may not be
	 * zero.
	 */
	private BinaryInteger(long val) {
		if (val < 0) {
			signum = -1;
			val = -val;
		} else {
			signum = 1;
		}

		int highWord = (int) (val >>> 32);
		if (highWord == 0) {
			mag = new int[1];
			mag[0] = (int) val;
		} else {
			mag = new int[2];
			mag[0] = highWord;
			mag[1] = (int) val;
		}
	}

	/**
	 * 由整数数组得到
	 */
	private static BinaryInteger valueOf(int val[]) {
		return (val[0] > 0 ? new BinaryInteger(val, 1) : new BinaryInteger(val));
	}

	// Constants

	/**
	 * Initialize static constant array when class is loaded.
	 */
	private final static int MAX_CONSTANT = 16;

	private static BinaryInteger posConst[] = new BinaryInteger[MAX_CONSTANT + 1];

	private static BinaryInteger negConst[] = new BinaryInteger[MAX_CONSTANT + 1];
	static {
		for (int i = 1; i <= MAX_CONSTANT; i++) {
			int[] magnitude = new int[1];
			magnitude[0] = (int) i;
			posConst[i] = new BinaryInteger(magnitude, 1);
			negConst[i] = new BinaryInteger(magnitude, -1);
		}
	}

	/**
	 * The BinaryInteger constant zero.
	 * 
	 * 
	 */
	public static final BinaryInteger ZERO = new BinaryInteger(new int[0], 0);

	/**
	 * The BinaryInteger constant one.
	 * 
	 * 
	 */
	public static final BinaryInteger ONE = valueOf(1);