The biguint library interface

• A biguint x is a pointer to an array u of uint32, together with an unsigned integer n called its length.
  x = (2^32)^0 * u[0] + (2^32)^1 * u[1] + ... + (2^32)^(n-1) * u[n-1].
  n must be lesser than BIGUINT_MAXLIMBS, which is currently 64.
• Every u[i] is called a limb.
• The greatest integer i lesser than n for which u[i] is non-zero is called the order of x. The order of zero is 0.

Creating a biguint

Just declare uint32 x[BIGUINT_MAXLIMBS] ; . In the following, we will refer to a biguint as a uint32 *; remember that it must be pre-allocated.

Setting it to zero

uint32 *x ;
unsigned int n ;

 bu_zero(x, n) ;

bu_zero() sets the first n limbs of x to zero.

Copying a biguint

uint32 const *x ;
uint32 *y ;
unsigned int n ;

 bu_copy(y, x, n) ;

bu_copy() will copy the first n limbs from x to y.

Calculating the order

uint32 const *x ;
unsigned int n ;
unsigned int r ;

 r = bu_len(x, n) ;

bu_len() outputs the order of x of length n. 0 <= r <= n.

Comparing two biguints

uint32 const *a ;
uint32 const *b ;
unsigned int n ;
int r ;

 r = bu_cmp(a, b, n) ;

bu_cmp() returns -1 if a < b, 1 if a > b, and 0 if a = b. a and b must have the same length n.

Writing a biguint as an array of bytes

char *s ;
uint32 const *x ;
unsigned int n ;

 bu_pack(s, x, n) ;
 bu_pack_big(s, x, n) ;

bu_pack() writes 4*n bytes to s. The bytes are a little-endian representation of x.
bu_pack_big() is the same, with a big-endian representation.

Reading a biguint from an array of bytes

char const *s ;
uint32 *x ;
unsigned int n ;

 bu_unpack(s, x, n) ;
 bu_unpack_big(s, x, n) ;

bu_unpack() reads 4*n little-endian bytes from s and builds the corresponding biguint x.
bu_unpack_big() is the same, but the bytes are interpreted as big-endian.

Formatting a biguint for readable output

char *s ;
uint32 const *x ;
unsigned int n ;

 bu_fmt(s, x, n) ;

bu_fmt() writes x in s as a standard big-endian hexadecimal number. x is considered of length n, so 8*n bytes will be written to s, even if it x starts with zeros.

Reading a biguint from readable format

char const *s ;
uint32 *x ;
unsigned int n ;
unsigned int r ;

 r = bu_scan(s, x, &n) ;

bu_scan() is the inverse of bu_fmt(): some bytes are read from s, and they build a biguint x of computed length n. The reading stops at the first byte encountered that is not in the 0-9, A-F or a-f range. bu_scan() returns the number of bytes read.

Addition

uint32 const *a ;
uint32 const *b ;
uint32 *c ;
unsigned int n ;
unsigned char carrybefore ;
unsigned char carryafter ;

 carryafter = bu_addc(c, a, b, n, carrybefore) ;
 carryafter = bu_subc(c, a, b, n, carrybefore) ;

bu_addc() adds a and b, and puts the result into c. a and b must have the same length, n; after the addition, c has length n. carrybefore must be 0 or 1; if it is 1, then b+1 is used instead of b. If c doesn't fit in n limbs, then the n least significant limbs are kept, and bu_addc() returns 1. Else it returns 0.
bu_subc() is the same, with substraction. If c should be negative, then c is really (2^32)^n - c and bu_subc() returns 1.
bu_add(c, a, b, n) is a macro for bu_addc(c, a, b, n, 0).
bu_sub(c, a, b, n) is a macro for bu_subc(c, a, b, n, 0).

Multiplication

uint32 const *a ;
uint32 const *b ;
uint32 *c ;
unsigned int an, bn ;

 bu_mul(c, a, an, b, bn) ;

bu_mul() computes c=a*b. a's length is an; b's length is bn; c's length will be an+bn.

Division

uint32 const *a ;
uint32 const *b ;
uint32 *q ;
uint32 *r ;
unsigned int n ;

 bu_div(a, b, q, r, n) ;
 bu_mod(a, b, n) ;

bu_div() computes q, the quotient, and r, the remainder, of a divided by b. If b is zero, a SIGFPE is raised: this is intentional.
bu_mod() computes only the remainder, and stores it into a.

Left-shifts and right-shifts

uint32 *x ;
unsigned int n ;
unsigned char carryafter ;
unsigned char carrybefore ;

 carryafter = bu_slbc(x, n, carrybefore) ;
 carryafter = bu_srbc(x, n, carrybefore) ;

bu_slbc() computes x <<= 1. The least significant bit of x is then set to carrybefore. bu_slbc() returns the previous value of x's most significant bit.
bu_srbc() computes x >>= 1. The most significant bit of x is then set to carrybefore. bu_slbc() returns the previous value of x's least significant bit.
bu_slb(x, n) and bu_srb(x, n) are macros for respectively bu_slbc(x, n, 0) and bu_srbc(x, n, 0).

Modular operations

uint32 const *a ;
uint32 const *b ;
uint32 *c ;
uint32 const *m ;
unsigned int n ;

 bu_addmod(c, a, b, m, n) ;
 bu_submod(c, a, b, m, n) ;
 bu_divmod(c, a, b, m, n) ;
 bu_invmod(c, m, n) ;

bu_addmod() computes c = (a+b) mod m.
bu_submod() computes c = (a-b) mod m.
a, b and m must have the same length n. a and b must already be numbers modulo m.