biginteger.java

进行与数字证书相关开发必须的java源码

        if(xyCmp > 0)
        {
            int shift = bitLength(0, x) - bitLength(0, y);
            int c[];
            if(shift > 1)
            {
                c = shiftLeft(y, shift - 1);
                count = shiftLeft(ONE.magnitude, shift - 1);
            } else
            {
                c = new int[x.length];
                count = new int[1];
                System.arraycopy(y, 0, c, c.length - y.length, y.length);
                count[0] = 1;
            }
            int iCount[] = new int[count.length];
            subtract(0, x, 0, c);
            System.arraycopy(count, 0, iCount, 0, count.length);
            int xStart = 0;
            int cStart = 0;
            int iCountStart = 0;
            do
            {
                for(int cmp = compareTo(xStart, x, cStart, c); cmp >= 0; cmp = compareTo(xStart, x, cStart, c))
                {
                    subtract(xStart, x, cStart, c);
                    add(count, iCount);
                }

                xyCmp = compareTo(xStart, x, 0, y);
                if(xyCmp <= 0)
                    break;
                if(x[xStart] == 0)
                    xStart++;
                shift = bitLength(cStart, c) - bitLength(xStart, x);
                if(shift == 0)
                {
                    c = shiftRightOne(cStart, c);
                    iCount = shiftRightOne(iCountStart, iCount);
                } else
                {
                    c = shiftRight(cStart, c, shift);
                    iCount = shiftRight(iCountStart, iCount, shift);
                }
                if(c[cStart] == 0)
                    cStart++;
                if(iCount[iCountStart] == 0)
                    iCountStart++;
            } while(true);
            if(xyCmp == 0)
            {
                add(count, ONE.magnitude);
                for(int i = xStart; i != x.length; i++)
                    x[i] = 0;

            }
        } else
        if(xyCmp == 0)
        {
            count = new int[1];
            count[0] = 1;
        } else
        {
            count = new int[1];
            count[0] = 0;
        }
        return count;
    }

    public BigInteger divide(BigInteger val)
        throws ArithmeticException
    {
        if(val.sign == 0)
            throw new ArithmeticException("Divide by zero");
        if(sign == 0)
            return ZERO;
        if(val.compareTo(ONE) == 0)
        {
            return this;
        } else
        {
            int mag[] = new int[magnitude.length];
            System.arraycopy(magnitude, 0, mag, 0, mag.length);
            return new BigInteger(sign * val.sign, divide(mag, val.magnitude));
        }
    }

    public BigInteger[] divideAndRemainder(BigInteger val)
        throws ArithmeticException
    {
        if(val.sign == 0)
            throw new ArithmeticException("Divide by zero");
        BigInteger biggies[] = new BigInteger[2];
        if(sign == 0)
        {
            biggies[0] = biggies[1] = ZERO;
            return biggies;
        }
        if(val.compareTo(ONE) == 0)
        {
            biggies[0] = this;
            biggies[1] = ZERO;
            return biggies;
        } else
        {
            int remainder[] = new int[magnitude.length];
            System.arraycopy(magnitude, 0, remainder, 0, remainder.length);
            int quotient[] = divide(remainder, val.magnitude);
            biggies[0] = new BigInteger(sign * val.sign, quotient);
            biggies[1] = new BigInteger(sign, remainder);
            return biggies;
        }
    }

    public boolean equals(Object val)
    {
        if(val == this)
            return true;
        if(!(val instanceof BigInteger))
            return false;
        BigInteger biggie = (BigInteger)val;
        if(biggie.sign != sign || biggie.magnitude.length != magnitude.length)
            return false;
        for(int i = 0; i < magnitude.length; i++)
            if(biggie.magnitude[i] != magnitude[i])
                return false;

        return true;
    }

    public BigInteger gcd(BigInteger val)
    {
        if(val.sign == 0)
            return abs();
        if(sign == 0)
            return val.abs();
        BigInteger u = this;
        BigInteger r;
        for(BigInteger v = val; v.sign != 0; v = r)
        {
            r = u.mod(v);
            u = v;
        }

        return u;
    }

    public int hashCode()
    {
        return 0;
    }

    public int intValue()
    {
        if(magnitude.length == 0)
            return 0;
        if(sign < 0)
            return -magnitude[magnitude.length - 1];
        else
            return magnitude[magnitude.length - 1];
    }

    public boolean isProbablePrime(int certainty)
    {
        if(certainty == 0)
            return true;
        BigInteger n = abs();
        if(n.equals(TWO))
            return true;
        if(n.equals(ONE) || !n.testBit(0))
            return false;
        if((certainty & 0x1) == 1)
            certainty = certainty / 2 + 1;
        else
            certainty /= 2;
        BigInteger q = n.subtract(ONE);
        int k = q.getLowestSetBit();
        q = q.shiftRight(k);
        Random rnd = new Random();
        for(int i = 0; i <= certainty; i++)
        {
            BigInteger x;
            do
                x = new BigInteger(n.bitLength(), rnd);
            while(x.compareTo(ONE) <= 0 || x.compareTo(n) >= 0);
            int j = 0;
            for(BigInteger y = x.modPow(q, n); (j != 0 || !y.equals(ONE)) && !y.equals(n.subtract(ONE)); y = y.modPow(TWO, n))
            {
                if(j > 0 && y.equals(ONE))
                    return false;
                if(++j == k)
                    return false;
            }

        }

        return true;
    }

    public long longValue()
    {
        long val = 0L;
        if(magnitude.length == 0)
            return 0L;
        if(magnitude.length > 1)
            val = (long)magnitude[magnitude.length - 2] << 32 | (long)magnitude[magnitude.length - 1] & 0xffffffffL;
        else
            val = (long)magnitude[magnitude.length - 1] & 0xffffffffL;
        if(sign < 0)
            return -val;
        else
            return val;
    }

    public BigInteger max(BigInteger val)
    {
        return compareTo(val) <= 0 ? val : this;
    }

    public BigInteger min(BigInteger val)
    {
        return compareTo(val) >= 0 ? val : this;
    }

    public BigInteger mod(BigInteger m)
        throws ArithmeticException
    {
        if(m.sign <= 0)
        {
            throw new ArithmeticException("BigInteger: modulus is not positive");
        } else
        {
            BigInteger biggie = remainder(m);
            return biggie.sign < 0 ? biggie.add(m) : biggie;
        }
    }

    public BigInteger modInverse(BigInteger m)
        throws ArithmeticException
    {
        if(m.sign != 1)
            throw new ArithmeticException("Modulus must be positive");
        BigInteger x = new BigInteger();
        BigInteger y = new BigInteger();
        BigInteger gcd = extEuclid(this, m, x, y);
        if(!gcd.equals(ONE))
            throw new ArithmeticException("Numbers not relatively prime.");
        if(x.compareTo(ZERO) < 0)
            x = x.add(m);
        return x;
    }

    private static BigInteger extEuclid(BigInteger a, BigInteger b, BigInteger u1Out, BigInteger u2Out)
    {
        BigInteger u1 = ONE;
        BigInteger u3 = a;
        BigInteger v1 = ZERO;
        BigInteger tn;
        for(BigInteger v3 = b; v3.compareTo(ZERO) > 0; v3 = tn)
        {
            BigInteger q = u3.divide(v3);
            tn = u1.subtract(v1.multiply(q));
            u1 = v1;
            v1 = tn;
            tn = u3.subtract(v3.multiply(q));
            u3 = v3;
        }

        u1Out.sign = u1.sign;
        u1Out.magnitude = u1.magnitude;
        BigInteger res = u3.subtract(u1.multiply(a)).divide(b);
        u2Out.sign = res.sign;
        u2Out.magnitude = res.magnitude;
        return u3;
    }

    private void zero(int x[])
    {
        for(int i = 0; i != x.length; i++)
            x[i] = 0;

    }

    public BigInteger modPow(BigInteger exponent, BigInteger m)
        throws ArithmeticException
    {
        int zVal[] = null;
        int yAccum[] = null;
        boolean useMonty = (m.magnitude[m.magnitude.length - 1] & 0x1) == 1;
        long mQ = 0L;
        if(useMonty)
        {
            mQ = m.getMQuote();
            BigInteger tmp = shiftLeft(32 * m.magnitude.length).mod(m);
            zVal = tmp.magnitude;
            useMonty = zVal.length == m.magnitude.length;
            if(useMonty)
                yAccum = new int[m.magnitude.length + 1];
        }
        if(!useMonty)
        {
            if(magnitude.length <= m.magnitude.length)
            {
                zVal = new int[m.magnitude.length];
                System.arraycopy(magnitude, 0, zVal, zVal.length - magnitude.length, magnitude.length);
            } else
            {
                BigInteger tmp = remainder(m);
                zVal = new int[m.magnitude.length];
                System.arraycopy(tmp.magnitude, 0, zVal, zVal.length - tmp.magnitude.length, tmp.magnitude.length);
            }
            yAccum = new int[m.magnitude.length * 2];
        }
        int yVal[] = new int[m.magnitude.length];
        for(int i = 0; i < exponent.magnitude.length; i++)
        {
            int v = exponent.magnitude[i];
            int bits = 0;
            if(i == 0)
            {
                while(v > 0) 
                {
                    v <<= 1;
                    bits++;
                }
                System.arraycopy(zVal, 0, yVal, 0, zVal.length);
                v <<= 1;
                bits++;
            }
            for(; v != 0; v <<= 1)
            {
                if(useMonty)
                {
                    multiplyMonty(yAccum, yVal, yVal, m.magnitude, mQ);
                } else
                {
                    square(yAccum, yVal);
                    remainder(yAccum, m.magnitude);
                    System.arraycopy(yAccum, yAccum.length - yVal.length, yVal, 0, yVal.length);
                    zero(yAccum);
                }
                bits++;
                if(v >= 0)
                    continue;
                if(useMonty)
                {
                    multiplyMonty(yAccum, yVal, zVal, m.magnitude, mQ);
                } else
                {
                    multiply(yAccum, yVal, zVal);
                    remainder(yAccum, m.magnitude);
                    System.arraycopy(yAccum, yAccum.length - yVal.length, yVal, 0, yVal.length);
                    zero(yAccum);
                }
            }

            for(; bits < 32; bits++)
                if(useMonty)
                {
                    multiplyMonty(yAccum, yVal, yVal, m.magnitude, mQ);
                } else
                {
                    square(yAccum, yVal);
                    remainder(yAccum, m.magnitude);
                    System.arraycopy(yAccum, yAccum.length - yVal.length, yVal, 0, yVal.length);
                    zero(yAccum);
                }

        }

        if(useMonty)
        {
            zero(zVal);
            zVal[zVal.length - 1] = 1;
            multiplyMonty(yAccum, yVal, zVal, m.magnitude, mQ);
        }
        return new BigInteger(1, yVal);
    }

    private int[] square(int w[], int x[])
    {
        if(w.length != 2 * x.length)
            throw new IllegalArgumentException("no I don't think so...");
        long u1;
        long u2;
        for(int i = x.length - 1; i != 0; i--)
        {
            long v = (long)x[i] & 0xffffffffL;
            u1 = v * v;
            u2 = u1 >>> 32;
            u1 &= 0xffffffffL;
            u1 += (long)w[2 * i + 1] & 0xffffffffL;
            w[2 * i + 1] = (int)u1;
            long c = u2 + (u1 >> 32);
            for(int j = i - 1; j >= 0; j--)
            {
                u1 = ((long)x[j] & 0xffffffffL) * v;
                u2 = u1 >>> 31;
                u1 = (u1 & (long)0x7fffffff) << 1;
                u1 += ((long)w[i + j + 1] & 0xffffffffL) + c;
                w[i + j + 1] = (int)u1;
                c = u2 + (u1 >>> 32);
            }

            c += (long)w[i] & 0xffffffffL;
            w[i] = (int)c;
            w[i - 1] = (int)(c >> 32);
        }

        u1 = (long)x[0] & 0xffffffffL;
        u1 *= u1;
        u2 = u1 >>> 32;
        u1 &= 0xffffffffL;
        u1 += (long)w[1] & 0xffffffffL;
        w[1] = (int)u1;
        w[0] = (int)(u2 + (u1 >> 32) + (long)w[0]);
        return w;
    }

    private int[] multiply(int x[], int y[], int z[])
    {
        for(int i = z.length - 1; i >= 0; i--)
        {
            long a = (long)z[i] & 0xffffffffL;
            long value = 0L;
            for(int j = y.length - 1; j >= 0; j--)
            {
                value += a * ((long)y[j] & 0xffffffffL) + ((long)x[i + j + 1] & 0xffffffffL);
                x[i + j + 1] = (int)value;
                value >>>= 32;
            }

            x[i] = (int)value;
        }

        return x;
    }

    private long getMQuote()
    {
        if(mQuote != -1L)
            return mQuote;
        if((magnitude[magnitude.length - 1] & 0x1) == 0)
        {
            return -1L;
        } else
        {
            byte bytes[] = {
                1, 0, 0, 0, 0
            };
            BigInteger b = new BigInteger(1, bytes);
            mQuote = negate().mod(b).modInverse(b).longValue();
            return mQuote;
        }
    }