biginteger.java

J2ME加密算法的代码!里面包括常用的算法

            return ZERO;
        }
        if (n == 0)
        {
            return this;
        }

        if (n < 0)
        {
            return shiftRight( -n);
        }

        return new BigInteger(sign, shiftLeft(magnitude, n));
    }

    /**
     * do a right shift - this does it in place.
     */
    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;
    }

    /**
     * do a right shift by one - this does it in place.
     */
    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 (this.sign < 0 ? valueOf( -1) : BigInteger.ZERO);
        }

        int[] res = new int[this.magnitude.length];

        System.arraycopy(this.magnitude, 0, res, 0, res.length);

        return new BigInteger(this.sign, shiftRight(0, res, n));
    }

    public int signum()
    {
        return sign;
    }

    /**
     * returns x = x - y - we assume x is >= y
     */
    private int[] subtract(int xStart, int[] x, int yStart, int[] y)
    {
        int iT = x.length - 1;
        int iV = y.length - 1;
        long m;
        int borrow = 0;

        do
        {
            m = (((long)x[iT]) & IMASK) - (((long)y[iV--]) & IMASK) + borrow;

            x[iT--] = (int)m;

            if (m < 0)
            {
                borrow = -1;
            }
            else
            {
                borrow = 0;
            }
        } while (iV >= yStart);

        while (iT >= xStart)
        {
            m = (((long)x[iT]) & IMASK) + borrow;
            x[iT--] = (int)m;

            if (m < 0)
            {
                borrow = -1;
            }
            else
            {
                break;
            }
        }

        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 (this.sign != val.sign)
        {
            return this.add(val.negate());
        }

        int compare = compareTo(0, magnitude, 0, val.magnitude);
        if (compare == 0)
        {
            return ZERO;
        }

        BigInteger bigun, 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(this.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;
        long lMag;
        for (int i = bytes.length - 1; i >= 0; i--)
        {
            if (bytesCopied == 4 && ofs >= 0)
            {
                if (sign < 0)
                {
                    // we are dealing with a +ve number and we want a -ve one, so
                    // invert the magnitude ints and add 1 (propagating the carry)
                    // to make a 2's complement -ve number
                    lMag = ~magnitude[ofs--] & IMASK;
                    lMag += carry;
                    if ((lMag & ~IMASK) != 0)
                        carry = 1;
                    else
                        carry = 0;
                    mag = (int)(lMag & IMASK);
                }
                else
                {
                    mag = magnitude[ofs--];
                }
                bytesCopied = 1;
            }
            else
            {
                mag >>>= 8;
                bytesCopied++;
            }

            bytes[i] = (byte)mag;
        }

        return bytes;
    }

    public BigInteger xor(BigInteger val) 
    {
        if (this.sign == 0)
        {
            return val;
        }

        if (val.sign == 0)
        {
            return this;
        }

        int[] aMag = this.sign > 0
            ? this.magnitude
            : this.add(ONE).magnitude;

        int[] bMag = val.sign > 0
            ? val.magnitude
            : val.add(ONE).magnitude;

        boolean resultNeg = (sign < 0 && val.sign >= 0) || (sign >= 0 && val.sign < 0);
        int resultLength = Math.max(aMag.length, bMag.length);
        int[] resultMag = new int[resultLength];

        int aStart = resultMag.length - aMag.length;
        int bStart = resultMag.length - bMag.length;

        for (int i = 0; i < resultMag.length; ++i)
        {
            int aWord = i >= aStart ? aMag[i - aStart] : 0;
            int bWord = i >= bStart ? bMag[i - bStart] : 0;

            if (this.sign < 0)
            {
                aWord = ~aWord;
            }

            if (val.sign < 0)
            {
                bWord = ~bWord;
            }

            resultMag[i] = aWord ^ bWord;

            if (resultNeg)
            {
                resultMag[i] = ~resultMag[i];
            }
        }

        BigInteger result = new BigInteger(1, resultMag);

        if (resultNeg)
        {
            result = result.not();
        }

        return result;
    }

    public BigInteger or(
        BigInteger value)
    {
        if (this.sign == 0)
        {
            return value;
        }

        if (value.sign == 0)
        {
            return this;
        }

        int[] aMag = this.sign > 0
                        ? this.magnitude
                        : this.add(ONE).magnitude;

        int[] bMag = value.sign > 0
                        ? value.magnitude
                        : value.add(ONE).magnitude;

        boolean resultNeg = sign < 0 || value.sign < 0;
        int resultLength = Math.max(aMag.length, bMag.length);
        int[] resultMag = new int[resultLength];

        int aStart = resultMag.length - aMag.length;
        int bStart = resultMag.length - bMag.length;

        for (int i = 0; i < resultMag.length; ++i)
        {
            int aWord = i >= aStart ? aMag[i - aStart] : 0;
            int bWord = i >= bStart ? bMag[i - bStart] : 0;

            if (this.sign < 0)
            {
                aWord = ~aWord;
            }

            if (value.sign < 0)
            {
                bWord = ~bWord;
            }

            resultMag[i] = aWord | bWord;

            if (resultNeg)
            {
                resultMag[i] = ~resultMag[i];
            }
        }

        BigInteger result = new BigInteger(1, resultMag);

        if (resultNeg)
        {
            result = result.not();
        }

        return result;
    }
    
    public BigInteger setBit(int n) 
        throws ArithmeticException 
    {
        if (n<0)
        {
             throw new ArithmeticException("Bit address less than zero");
        }
         
        int wordNum = n/32;
        int result[];
        
        result = createResult(wordNum);
        
        result[result.length - wordNum - 1] |= 1 << (n % 32);
    
        return new BigInteger(sign, result);
    }
    
    public BigInteger clearBit(int n) 
        throws ArithmeticException 
    {
        if (n<0)
        {
             throw new ArithmeticException("Bit address less than zero");
        }
         
        int wordNum = n/32;
        int result[];
        
        result = createResult(wordNum);
        
        result[result.length - wordNum - 1] &= ~(1 << (n % 32));
    
        return new BigInteger(sign, result);
    }

    public BigInteger flipBit(int n) 
        throws ArithmeticException 
    {
        if (n<0)
        {
             throw new ArithmeticException("Bit address less than zero");
        }
         
        int wordNum = n/32;
        int[] result = createResult(wordNum);
        
        result[result.length - wordNum - 1] ^= (1 << (n % 32));
    
        return new BigInteger(sign, result);
    }

    private int[] createResult(int wordNum)
    {
        int[] result;
        if (magnitude.length < wordNum + 1)
        {
            result = new int[wordNum + 1];
        }
        else
        {
            result = new int[magnitude.length];
        }
        
        System.arraycopy(magnitude, 0, result, result.length - magnitude.length, magnitude.length);
        return result;
    }
        
    public String toString()
    {
        return toString(10);
    }

    public String toString(int rdx)
    {
        if (magnitude == null)
        {
            return "null";
        }
        else if (sign == 0)
        {
            return "0";
        }

        String s = "";
        String h;

        if (rdx == 16)
        {
            for (int i = 0; i < magnitude.length; i++)
            {
                h = "0000000" + Integer.toHexString(magnitude[i]);
                h = h.substring(h.length() - 8);
                s = s + h;
            }
        }
        else
        {
            // This is algorithm 1a from chapter 4.4 in Seminumerical Algorithms, slow but it works
            Stack S = new Stack();
            BigInteger base = new BigInteger(Integer.toString(rdx, rdx), rdx);
            // The sign is handled separatly.
            // Notice however that for this to work, radix 16 _MUST_ be a special case,
            // unless we want to enter a recursion well. In their infinite wisdom, why did not 
            // the Sun engineers made a c'tor for BigIntegers taking a BigInteger as parameter?
            // (Answer: Becuase Sun's BigIntger is clonable, something bouncycastle's isn't.)
            BigInteger u = new BigInteger(this.abs().toString(16), 16);
            BigInteger b;

            // For speed, maye these test should look directly a u.magnitude.length?
            while (!u.equals(BigInteger.ZERO))
            {
                b = u.mod(base);
                if (b.equals(BigInteger.ZERO))
                    S.push("0");
                else
                    S.push(Integer.toString(b.magnitude[0], rdx));
                u = u.divide(base);
            }
            // Then pop the stack
            while (!S.empty())
                s = s + S.pop();
        }
        // Strip leading zeros.
        while (s.length() > 1 && s.charAt(0) == '0')
            s = s.substring(1);

        if (s.length() == 0)
            s = "0";
        else if (sign == -1)
            s = "-" + s;

        return s;
    }

    public static final BigInteger ZERO = new BigInteger(0, new byte[0]);
    public static final BigInteger ONE = valueOf(1);
    private static final BigInteger TWO = valueOf(2);

    private static final int[] smallPrimes = new int[]{ 3, 5, 7, 11, 13, 17, 19, 23 };
    private static final int smallPrimesProduct = 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;

    public static BigInteger valueOf(long val)
    {
        if (val == 0)
        {
            return BigInteger.ZERO;
        }

        if (val < 0)
        {
            if (val == Long.MIN_VALUE)
            {
                return valueOf(~val).not();
            }

            return valueOf(-val).negate();
        }

        // store val into a byte array
        byte[] b = new byte[8];
        for (int i = 0; i < 8; i++)
        {
            b[7 - i] = (byte)val;
            val >>= 8;
        }

        return new BigInteger(b);
    }

    public int getLowestSetBit()
    {
        if (this.equals(ZERO))
        {
            return -1;
        }

        int w = magnitude.length - 1;

        while (w >= 0)
        {
            if (magnitude[w] != 0)
            {
                break;
            }

            w--;
        }

        int b = 31;

        while (b > 0)
        {
            if ((magnitude[w] << b) == 0x80000000)
            {
                break;
            }

            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;
        }

        return ((magnitude[(magnitude.length - 1) - n / 32] >> (n % 32)) & 1) > 0;
    }
}