cinteger-arithmeticmodular-arithmeticmultiprecision

multiprecision unsigned subtraction in C


I am trying to implement multi-precision unsigned subtraction over a finite field (p=2^191-19) in C, but I cannot figure out how to deal with borrow bit! My operands are represented in radix-2^16 as:

typedef unsigned long long T[12];

which means each element of the T-type array has exactly 16-bits data (radix-2^16 representation). Now I want to subtract two operands of T type, but I do not know which one is smaller! If the result is negative, I want to add the result to the prime value to have positive results in modular arithmetic. Here is my implementation based on this book page-30(Multiprecision subtraction algorithm):

void bigint192_sub(T r, const T a, const T b){
    int i;
    int borrow;
    r[0] = a[0] - b[0];
    borrow = r[0] >> 16;
    r[0] &= 0xFFFF;
    for(i=1;i<12;++i){
        r[i] = a[i] - b[i] - borrow;
        borrow = r[i] >> 16;
        r[i] &= 0xFFFF;
    }
}

but I got the wrong answer!

My inputs:
a =0x2d7e33e5bba0f6bb87ce04b28e940662db8f3f81aaf94576
b =0x28afc585dca4a8003b081f7289de11c2d229d5a967081f72
Myresult=0x4d16e62defd4ebc4cc8e54104b7f4a0096769d843f12604
Crresult=0x4ce6e5fdefc4ebb4cc5e54004b5f4a0096569d843f12604

Solution

  • You should fix borrow evaluation, since it may be only 0 or 1. So you should treat underflow as borrow equals to 1:

    borrow = (r[i] >> 16) != 0;
    

    Also I'd rewrite function in a bit more general form, since we may treat first pass as like we have no borrow:

    void bigint192_sub(T r, const T a, const T b){
        int i;
        int borrow;
        for (borrow = 0, i = 0; i < 12; ++i) {
            r[i] = a[i] - b[i] - borrow;
            borrow = (r[i] >> 16) != 0;
            r[i] &= 0xFFFF;
        }
    }