bignum.java

手机上进行RSA加密的算法

                                        r.negative = false;
                                        sub_unsigned(r, a);
                                        r.negative = true ^ r.negative;
                                }
                                else
                                {
                                        add_unsigned(r, a);
                                }
                        }

        }

        public static void
        sub(BigNum r, int a)
        {
                if (a == 0)
                        return;


//			//
//			// Test for zeroes
//			//
//			if (a == 0)
//				return;
//			if (isZero(r))
//			{
//				assign(r, a);
//				r.negative = (a < 0);
//				return;
//			}


                        if (a < 0)
                        {
                                if (r.negative)
                                {
                                        r.negative = false;
                                        sub_unsigned(r, -a);
                                        r.negative = true ^ r.negative;
                                }
                                else
                                {
                                        add_unsigned(r, -a);
                                }
                        }
                        else
                        {
                                if (r.negative)
                                {
                                        r.negative = false;
                                        add_unsigned(r, a);
                                        r.negative = true;
                                }
                                else
                                {
                                        sub_unsigned(r, a);
                                }
                        }

        }


        public static void
        add(BigNum r ,BigNum a, BigNum b)
        {

                        //
                        // Test for zeroes
                        //
                        if (a.len == 0)
                        {
                                copy(r, b);
                                return;
                        }
                        if (b.len == 0)
                        {
                                copy(r, a);
                                return;
                        }

                        if (a.negative)
                        {
                                if (b.negative)
                                {
                                        add_unsigned(r, a, b);
                                        r.negative = true;
                                }
                                else
                                {
                                        sub_unsigned(r, b, a);
                                }
                        }
                        else
                        {
                                if (b.negative)
                                {
                                        sub_unsigned(r, a, b);
                                }
                                else
                                {
                                        add_unsigned(r, a, b);
                                }
                        }

        }

        public static void
        add_unsigned(BigNum r, int a)
        {

                        if (a == 0)
                                return;

                        if (a < 0)
                                throw new MathError("unexpected negative");

                        if (r.len == 0)
                        {
                                r.n[0] = a;
                                r.len = 1;
                                r.negative = false;
                                return;
                        }

                        // Not tested till now, since len may have been zero
                        if (r.negative)
                                throw new MathError("unexpected negative");


                        grow(r, r.len+1);
                        boolean carry = false;

                        // If LONG
                        // long rn[] = r.n;
                        // long sum = rn[0] + a;
                        // If not LONG
                        int rn[] = r.n;
                        int sum = rn[0] + a;

                        rn[0] = sum & MASK;
                        carry = (sum >= RADIX);

                        int i = 1;
                        int rlen = r.len;
                        for (;carry && i < rlen; ++i)
                        {
                                sum = rn[i] + 1;
                                if (sum < RADIX)
                                {
                                        rn[i] = sum;
                                        carry = false;
                                }
                                else
                                {
                                        rn[i] = sum & MASK;
                                }
                        }
                        if (carry)
                        {
                                rn[i] = 1;
                                r.len++;
                        }

        }

        public static void
        add_unsigned(BigNum r ,BigNum a, BigNum b)
        {

                        // Ensure a is the longest
                        if (a.len < b.len)
                        {
                                BigNum t = a;
                                a = b;
                                b = t;
                        }

                        // Needed in case the result is same object as r
                        int alen = a.len;
                        int blen = b.len;

                        r.len = alen;
                        grow(r, r.len);
                        r.negative = false;

                        // If LONG
                        // long an[] = a.n;
                        // long bn[] = b.n;
                        // long rn[] = r.n;
                        // If not LONG
                        int an[] = a.n;
                        int bn[] = b.n;
                        int rn[] = r.n;

                        boolean carry = false;
                        int i;
                        for (i=0; i < blen; ++i)
                        {
                                // If LONG
                                // long sum = an[i] + bn[i] + (carry ? 1 : 0);
                                // If not LONG
                                int sum = an[i] + bn[i] + (carry ? 1 : 0);

                                rn[i] = sum & MASK;
                                carry = (sum >= RADIX);
                        }
                        for (;carry && i < alen; ++i)
                        {
                                // If LONG
                                // long sum = an[i] + 1;
                                // If not LONG
                                int sum = an[i] + 1;

                                if (sum < RADIX)
                                {
                                        rn[i] = sum;
                                        carry = false;
                                }
                                else
                                {
                                        rn[i] = sum & MASK;
                                }
                        }
                        if (a.len > i)
                                System.arraycopy(an, i, rn, i, alen-i);
                        if (carry)
                        {
                                r.len++;
                                grow(r, r.len);
                                r.n[i] = 1;	// Note - rn not valid after grow
                        }
// r.check_state();

        }


        public static void
        sub(BigNum r, BigNum a, BigNum b)
        {

                        //
                        // Test for zeroes
                        //
                        if (a.len == 0)
                        {
                                copy(r, b);
                                if (b.len > 0)
                                        r.negative = true ^ b.negative;
                                return;
                        }
                        if (b.len == 0)
                        {
                                copy(r, a);
                                return;
                        }

                        if (a.negative)
                        {
                                if (b.negative)
                                {
                                        sub_unsigned(r, b, a);
                                }
                                else
                                {
                                        add_unsigned(r, b, a);
                                        r.negative = true;
                                }
                        }
                        else
                        {
                                if (b.negative)
                                {
                                        add_unsigned(r, a, b);
                                }
                                else
                                {
                                        sub_unsigned(r, a, b);
                                }
                        }

        }


        public static void
        sub_unsigned(BigNum r, int a)
        {

                        if (a == 0)
                                return;

                        if (a < 0)
                                throw new MathError("unexpected negative");

                        if (r.len == 0)
                        {
                                r.n[0] = a;
                                r.len = 1;
                                r.negative = true;
                                return;
                        }

                        // Not tested till now, since len may have been zero
                        if (r.negative)
                                throw new MathError("unexpected negative");

                        // If LONG
                        // long rn[] = r.n;
                        // If not LONG
                        int rn[] = r.n;

                        int rlen = r.len;

                        if (rlen == 1)
                        {
                                if (a == rn[0])
                                {
                                        rn[0] = 0;
                                        r.len = 0;
                                        r.negative = false;
                                        return;
                                }
                                if (a < rn[0])
                                {
                                        rn[0] -= a;
                                        return;
                                }
                                r.negative = true;
                        }

                        // If LONG
                        // long diff = r.n[0] - a;
                        // If not LONG
                        int diff = rn[0] - a;

                        rn[0] = diff & MASK;
                        boolean borrow = (diff < 0);

                        for (int i = 0; borrow && i < rlen; ++i)
                        {
                                diff = rn[i] - 1;
                                if (diff >= 0)
                                {
                                        rn[i] = diff;
                                        borrow = false;
                                }
                                else
                                {
                                        rn[i] = diff & MASK;
                                }
                        }

                        while (rlen > 0 && rn[rlen-1] == 0)
                                rlen--;
                        r.len = rlen;

        }

        public static void
        sub_unsigned(BigNum r, BigNum a, BigNum b)
        {

                        switch (ucmp(a, b))
                        {
                        case 0:
                                zero(r);
                                return;
                        case -1:
                                BigNum t = a;
                                a = b;
                                b = t;
                                r.negative = true;
                                break;
                        case 1:
                                r.negative = false;
                        }

                        // Now a is the largest

                        grow(r, a.len);

                        // If LONG
                        // long an[] = a.n;
                        // long bn[] = b.n;
                        // long rn[] = r.n;
                        // If not LONG
                        int an[] = a.n;
                        int bn[] = b.n;
                        int rn[] = r.n;
                        int alen = a.len;
                        int blen = b.len;

                        boolean borrow = false;
                        int i;
                        for (i=0; i < blen; ++i)
                        {
                                // If LONG
                                // long diff = an[i] - bn[i] - (borrow ? 1 : 0);
                                // If not LONG
                                int diff = an[i] - bn[i] - (borrow ? 1 : 0);

                                rn[i] = diff & MASK;
                                borrow = (diff < 0);
                        }
                        for (;borrow && i < alen; ++i)
                        {
                                // If LONG
                                // long diff = an[i] - 1;
                                // If not LONG
                                int diff = an[i] - 1;

                                if (diff >= 0)
                                {
                                        rn[i] = diff;
                                        borrow = false;
                                }
                                else
                                {
                                        rn[i] = diff & MASK;
                                }
                        }
                        if (a.len > i)
                                System.arraycopy(an, i, rn, i, a.len-i);

                        int rlen = a.len;
                        while (rlen > 0 && rn[rlen-1] == 0)
                                rlen--;
                        r.len = rlen;

        }

        //
        // returns 0 if a==b
        // returns -1 if a<b
        // returns 1 if a>b
        //
        public static int
        cmp( BigNum a, BigNum b)
        {

                        // Not strictly necessary