biginteger.java

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

            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(BigInteger.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 BigInteger lucasLehmerSequence(int z, BigInteger k, BigInteger n) {
        BigInteger d = BigInteger.valueOf(z);
        BigInteger u = ONE; BigInteger u2;
        BigInteger v = ONE; BigInteger 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;
    }

    /**
     * Returns true iff this BigInteger passes the specified number of
     * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
     * 186-2).
     *
     * The following assumptions are made:
     * This BigInteger 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
        BigInteger thisMinusOne = this.subtract(ONE);
	BigInteger 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)
	    BigInteger b;
	    do {
		b = new BigInteger(this.bitLength(), rnd);
	    } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);

	    int j = 0;
	    BigInteger 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;
    }

    /**
     * This private constructor differs from its public cousin
     * with the arguments reversed in two ways: it assumes that its
     * arguments are correct, and it doesn't copy the magnitude array.
     */
    private BigInteger(int[] magnitude, int signum) {
	this.signum = (magnitude.length==0 ? 0 : signum);
	this.mag = magnitude;
    }

    /**
     * This private constructor is for internal use and assumes that its
     * arguments are correct.
     */
    private BigInteger(byte[] magnitude, int signum) {
	this.signum = (magnitude.length==0 ? 0 : signum);
        this.mag = stripLeadingZeroBytes(magnitude);
    }

    /**
     * This private constructor is for internal use in converting
     * from a MutableBigInteger object into a BigInteger.
     */
    BigInteger(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

    /**
     * Returns a BigInteger whose value is equal to that of the
     * specified <code>long</code>.  This "static factory method" is
     * provided in preference to a (<code>long</code>) constructor
     * because it allows for reuse of frequently used BigIntegers.
     *
     * @param  val value of the BigInteger to return.
     * @return a BigInteger with the specified value.
     */
    public static BigInteger 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 BigInteger(val);
    }

    /**
     * Constructs a BigInteger with the specified value, which may not be zero.
     */
    private BigInteger(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;
        }
    }

    /**
     * Returns a BigInteger with the given two's complement representation.
     * Assumes that the input array will not be modified (the returned
     * BigInteger will reference the input array if feasible).
     */
    private static BigInteger valueOf(int val[]) {
        return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
    }

    // Constants

    /**
     * Initialize static constant array when class is loaded.
     */
    private final static int MAX_CONSTANT = 16;
    private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
    private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
    static {
	for (int i = 1; i <= MAX_CONSTANT; i++) {
	    int[] magnitude = new int[1];
	    magnitude[0] = (int) i;
	    posConst[i] = new BigInteger(magnitude,  1);
	    negConst[i] = new BigInteger(magnitude, -1);
	}
    }

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

    /**
     * The BigInteger constant one.
     *
     * @since   1.2
     */
    public static final BigInteger ONE = valueOf(1);

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

    /**
     * The BigInteger constant ten.
     *
     * @since   1.5
     */
    public static final BigInteger TEN = valueOf(10);

    // Arithmetic Operations

    /**
     * Returns a BigInteger whose value is <tt>(this + val)</tt>.
     *
     * @param  val value to be added to this BigInteger.
     * @return <tt>this + val</tt>
     */
    public BigInteger add(BigInteger val) {
        int[] resultMag;
	if (val.signum == 0)
            return this;
	if (signum == 0)
	    return val;
	if (val.signum == signum)
            return new BigInteger(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 BigInteger(resultMag, cmp*signum);
    }

    /**
     * Adds the contents of the int arrays x and y. This method allocates
     * a new int array to hold the answer and returns a reference to that
     * array.
     */
    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;
    }

    /**
     * Returns a BigInteger whose value is <tt>(this - val)</tt>.
     *
     * @param  val value to be subtracted from this BigInteger.
     * @return <tt>this - val</tt>
     */
    public BigInteger subtract(BigInteger val) {
        int[] resultMag;
	if (val.signum == 0)
            return this;
	if (signum == 0)
	    return val.negate();
	if (val.signum != signum)
            return new BigInteger(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 BigInteger(resultMag, cmp*signum);
    }

    /**
     * Subtracts the contents of the second int arrays (little) from the
     * first (big).  The first int array (big) must represent a larger number
     * than the second.  This method allocates the space necessary to hold the
     * answer.
     */
    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);