biginteger.java

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

    public void multiplyMonty(int a[], int x[], int y[], int m[], long mQuote)
    {
        int n = m.length;
        int nMinus1 = n - 1;
        long y_0 = (long)y[n - 1] & 0xffffffffL;
        for(int i = 0; i <= n; i++)
            a[i] = 0;

        for(int i = n; i > 0; i--)
        {
            long x_i = (long)x[i - 1] & 0xffffffffL;
            long u = (((long)a[n] & 0xffffffffL) + (x_i * y_0 & 0xffffffffL) & 0xffffffffL) * mQuote & 0xffffffffL;
            long prod1 = x_i * y_0;
            long prod2 = u * ((long)m[n - 1] & 0xffffffffL);
            long tmp = ((long)a[n] & 0xffffffffL) + (prod1 & 0xffffffffL) + (prod2 & 0xffffffffL);
            long carry = (prod1 >>> 32) + (prod2 >>> 32) + (tmp >>> 32);
            for(int j = nMinus1; j > 0; j--)
            {
                prod1 = x_i * ((long)y[j - 1] & 0xffffffffL);
                prod2 = u * ((long)m[j - 1] & 0xffffffffL);
                tmp = ((long)a[j] & 0xffffffffL) + (prod1 & 0xffffffffL) + (prod2 & 0xffffffffL) + (carry & 0xffffffffL);
                carry = (carry >>> 32) + (prod1 >>> 32) + (prod2 >>> 32) + (tmp >>> 32);
                a[j + 1] = (int)tmp;
            }

            carry += (long)a[0] & 0xffffffffL;
            a[1] = (int)carry;
            a[0] = (int)(carry >>> 32);
        }

        if(compareTo(0, a, 0, m) >= 0)
            subtract(0, a, 0, m);
        for(int i = 0; i < n; i++)
            x[i] = a[i + 1];

    }

    public BigInteger multiply(BigInteger val)
    {
        if(sign == 0 || val.sign == 0)
        {
            return ZERO;
        } else
        {
            int res[] = new int[magnitude.length + val.magnitude.length];
            return new BigInteger(sign * val.sign, multiply(res, magnitude, val.magnitude));
        }
    }

    public BigInteger negate()
    {
        return new BigInteger(-sign, magnitude);
    }

    public BigInteger pow(int exp)
        throws ArithmeticException
    {
        if(exp < 0)
            throw new ArithmeticException("Negative exponent");
        if(sign == 0)
            return exp != 0 ? this : ONE;
        BigInteger y = ONE;
        BigInteger z = this;
        do
        {
            if(exp == 0)
                break;
            if((exp & 0x1) == 1)
                y = y.multiply(z);
            exp >>= 1;
            if(exp != 0)
                z = z.multiply(z);
        } while(true);
        return y;
    }

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

                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);
                else
                    c = shiftRight(cStart, c, shift);
                if(c[cStart] == 0)
                    cStart++;
            } while(true);
            if(xyCmp == 0)
            {
                for(int i = xStart; i != x.length; i++)
                    x[i] = 0;

            }
        } else
        if(xyCmp == 0)
        {
            for(int i = 0; i != x.length; i++)
                x[i] = 0;

        }
        return x;
    }

    public BigInteger remainder(BigInteger val)
        throws ArithmeticException
    {
        if(val.sign == 0)
            throw new ArithmeticException("BigInteger: Divide by zero");
        if(sign == 0)
        {
            return ZERO;
        } else
        {
            int res[] = new int[magnitude.length];
            System.arraycopy(magnitude, 0, res, 0, res.length);
            return new BigInteger(sign, remainder(res, val.magnitude));
        }
    }

    private int[] shiftLeft(int mag[], int n)
    {
        int nInts = n >>> 5;
        int nBits = n & 0x1f;
        int magLen = mag.length;
        int newMag[] = null;
        if(nBits == 0)
        {
            newMag = new int[magLen + nInts];
            for(int i = 0; i < magLen; i++)
                newMag[i] = mag[i];

        } else
        {
            int i = 0;
            int nBits2 = 32 - nBits;
            int highBits = mag[0] >>> nBits2;
            if(highBits != 0)
            {
                newMag = new int[magLen + nInts + 1];
                newMag[i++] = highBits;
            } else
            {
                newMag = new int[magLen + nInts];
            }
            int m = mag[0];
            for(int j = 0; j < magLen - 1; j++)
            {
                int next = mag[j + 1];
                newMag[i++] = m << nBits | next >>> nBits2;
                m = next;
            }

            newMag[i] = mag[magLen - 1] << nBits;
        }
        return newMag;
    }

    public BigInteger shiftLeft(int n)
    {
        if(sign == 0 || magnitude.length == 0)
            return ZERO;
        if(n == 0)
            return this;
        if(n < 0)
            return shiftRight(-n);
        else
            return new BigInteger(sign, shiftLeft(magnitude, n));
    }

    private int[] shiftRight(int start, int mag[], int n)
    {
        int nInts = (n >>> 5) + start;
        int nBits = n & 0x1f;
        int magLen = mag.length;
        if(nInts != start)
        {
            int delta = nInts - start;
            for(int i = magLen - 1; i >= nInts; i--)
                mag[i] = mag[i - delta];

            for(int i = nInts - 1; i >= start; i--)
                mag[i] = 0;

        }
        if(nBits != 0)
        {
            int nBits2 = 32 - nBits;
            int m = mag[magLen - 1];
            for(int i = magLen - 1; i >= nInts + 1; i--)
            {
                int next = mag[i - 1];
                mag[i] = m >>> nBits | next << nBits2;
                m = next;
            }

            mag[nInts] >>>= nBits;
        }
        return mag;
    }

    private int[] shiftRightOne(int start, int mag[])
    {
        int magLen = mag.length;
        int m = mag[magLen - 1];
        for(int i = magLen - 1; i >= start + 1; i--)
        {
            int next = mag[i - 1];
            mag[i] = m >>> 1 | next << 31;
            m = next;
        }

        mag[start] >>>= 1;
        return mag;
    }

    public BigInteger shiftRight(int n)
    {
        if(n == 0)
            return this;
        if(n < 0)
            return shiftLeft(-n);
        if(n >= bitLength())
        {
            return sign >= 0 ? ZERO : valueOf(-1L);
        } else
        {
            int res[] = new int[magnitude.length];
            System.arraycopy(magnitude, 0, res, 0, res.length);
            return new BigInteger(sign, shiftRight(0, res, n));
        }
    }

    public int signum()
    {
        return sign;
    }

    private int[] subtract(int xStart, int x[], int yStart, int y[])
    {
        int iT = x.length - 1;
        int iV = y.length - 1;
        int borrow = 0;
        do
        {
            long m = (((long)x[iT] & 0xffffffffL) - ((long)y[iV--] & 0xffffffffL)) + (long)borrow;
            x[iT--] = (int)m;
            if(m < (long)0)
                borrow = -1;
            else
                borrow = 0;
        } while(iV >= yStart);
        do
        {
            if(iT < xStart)
                break;
            long m = ((long)x[iT] & 0xffffffffL) + (long)borrow;
            x[iT--] = (int)m;
            if(m >= (long)0)
                break;
            borrow = -1;
        } while(true);
        return x;
    }

    public BigInteger subtract(BigInteger val)
    {
        if(val.sign == 0 || val.magnitude.length == 0)
            return this;
        if(sign == 0 || magnitude.length == 0)
            return val.negate();
        if(val.sign < 0)
        {
            if(sign > 0)
                return add(val.negate());
        } else
        if(sign < 0)
            return add(val.negate());
        int compare = compareTo(val);
        if(compare == 0)
            return ZERO;
        BigInteger bigun;
        BigInteger littlun;
        if(compare < 0)
        {
            bigun = val;
            littlun = this;
        } else
        {
            bigun = this;
            littlun = val;
        }
        int res[] = new int[bigun.magnitude.length];
        System.arraycopy(bigun.magnitude, 0, res, 0, res.length);
        return new BigInteger(sign * compare, subtract(0, res, 0, littlun.magnitude));
    }

    public byte[] toByteArray()
    {
        int bitLength = bitLength();
        byte bytes[] = new byte[bitLength / 8 + 1];
        int bytesCopied = 4;
        int mag = 0;
        int ofs = magnitude.length - 1;
        int carry = 1;
        for(int i = bytes.length - 1; i >= 0; i--)
        {
            if(bytesCopied == 4 && ofs >= 0)
            {
                if(sign < 0)
                {
                    long lMag = (long)(~magnitude[ofs--]) & 0xffffffffL;
                    lMag += carry;
                    if((lMag & 0xffffffff00000000L) != (long)0)
                        carry = 1;
                    else
                        carry = 0;
                    mag = (int)(lMag & 0xffffffffL);
                } else
                {
                    mag = magnitude[ofs--];
                }
                bytesCopied = 1;
            } else
            {
                mag >>>= 8;
                bytesCopied++;
            }
            bytes[i] = (byte)mag;
        }

        return bytes;
    }

    public String toString()
    {
        return toString(10);
    }

    public String toString(int rdx)
    {
        if(magnitude == null)
            return "null";
        if(sign == 0)
            return "0";
        String s = new String();
        if(rdx == 16)
        {
            for(int i = 0; i < magnitude.length; i++)
            {
                String h = "0000000".concat(String.valueOf(String.valueOf(Integer.toHexString(magnitude[i]))));
                h = h.substring(h.length() - 8);
                s = String.valueOf(s) + String.valueOf(h);
            }

        } else
        {
            Stack S = new Stack();
            BigInteger base = new BigInteger(Integer.toString(rdx, rdx), rdx);
            for(BigInteger u = new BigInteger(abs().toString(16), 16); !u.equals(ZERO); u = u.divide(base))
            {
                BigInteger b = u.mod(base);
                if(b.equals(ZERO))
                    S.push("0");
                else
                    S.push(Integer.toString(b.magnitude[0], rdx));
            }

            while(!S.empty()) 
                s = String.valueOf(s) + String.valueOf(S.pop());
        }
        for(; s.length() > 1 && s.charAt(0) == '0'; s = s.substring(1));
        if(s.length() == 0)
            s = "0";
        else
        if(sign == -1)
            s = "-".concat(String.valueOf(String.valueOf(s)));
        return s;
    }

    public static BigInteger valueOf(long val)
    {
        if(val == (long)0)
            return ZERO;
        byte b[] = new byte[8];
        for(int i = 0; i < 8; i++)
        {
            b[7 - i] = (byte)(int)val;
            val >>= 8;
        }

        return new BigInteger(b);
    }

    private int max(int a, int b)
    {
        if(a < b)
            return b;
        else
            return a;
    }

    public int getLowestSetBit()
    {
        if(equals(ZERO))
            return -1;
        int w;
        for(w = magnitude.length - 1; w >= 0 && magnitude[w] == 0; w--);
        int b;
        for(b = 31; b > 0 && magnitude[w] << b != 0x80000000; b--);
        return (magnitude.length - 1 - w) * 32 + (31 - b);
    }

    public boolean testBit(int n)
        throws ArithmeticException
    {
        if(n < 0)
            throw new ArithmeticException("Bit position must not be negative");
        if(n / 32 >= magnitude.length)
            return sign < 0;
        else
            return (magnitude[magnitude.length - 1 - n / 32] >> n % 32 & 0x1) > 0;
    }

    static 
    {
        IMASK = 0xffffffffL;
        BITS_PER_BYTE = 8;
        BYTES_PER_INT = 4;
    }
}