The biguint library interface

• A biguint x is a pointer to an array u of uint32_t, 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].
• 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

Writing a biguint as an array of bytes

char *s ;
uint32_t 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_t *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 writes them into 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_t 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. bu_fmt returns the number of bytes written.

Reading a biguint from readable format

char const *s ;
uint32_t *x ;
unsigned int xn ;
unsigned int z ;
unsigned int len ;

  len = bu_scanlen(s, &z) ;
  bu_scan(s, len, x, xn, z) ;

bu_scanlen() scans s for a biguint written as a hexadecimal number and returns the number of bytes read. The reading stops at the first byte encountered that is not in the 0-9, A-F or a-f range. The z integer then contains the number of bytes excluding leading zeros.

If x has not been allocated yet, you can use xn = bitarray_div8(z) (if you have included the bitarray.h header) and allocate x with length xn.

bu_scan() then reads len bytes from s, assuming there are z significant bytes (i.e. not leading zeros); it writes the resulting biguint into x of length xn. It returns 1, except if xn is too small, in which case it returns 0 EOVERFLOW.

Addition

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;
unsigned char carrybefore ;
unsigned char carryafter ;

  bu_add(c, cn, a, an, b, bn) ;
  bu_sub(c, cn, a, an, b, bn) ;

bu_add() adds a and b, and puts the result into c. It returns 1 unless it has to truncate it.

bu_sub() substracts b from a, and puts the result into c. If the result should be negative, then it is written as (2^32)^cn - c and the function returns 0 EOVERFLOW.

Multiplication

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;

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

bu_mul() computes c=a*b. Make sure that cn ≥ bu_len(a, an) + bu_len(b, bn). If it is not the case, the result will be truncated and bu_mul will return 0 EOVERFLOW.

Division

uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *q ;
unsigned int qn ;
uint32_t *r ;
unsigned int rn ;

 bu_div(a, an, b, bn, q, qn, r, rn) ;
 bu_mod(r, rn, b, bn) ;

bu_div() computes q, the quotient, and r, the remainder, of a divided by b. If b is zero, it returns 0 EDOM. If qn or rn is to small to store the quotient or the remainder, it returns 0 EOVERFLOW. bu_mod() computes only the remainder, and stores it in-place.

GCD

uint32_t *r ;
unsigned int rn ;
uint32_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;

 bu_gcd(r, rn, a, an, b, bn) ;

Note that this function iterates on divisions, so it might use a non totally negligible amount of CPU time.

Left-shifts and right-shifts

uint32_t *x ;
unsigned int xn ;
unsigned char carryafter ;
unsigned char carrybefore ;

 carryafter = bu_slbc(x, xn, carrybefore) ;
 carryafter = bu_srbc(x, xn, 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_t const *a ;
unsigned int an ;
uint32_t const *b ;
unsigned int bn ;
uint32_t *c ;
unsigned int cn ;
uint32_t const *m ;
unsigned int mn ;

 bu_addmod(c, cn, a, an, b, bn, m, mn) ;
 bu_submod(c, cn, a, an, b, bn, m, mn) ;
 bu_mulmod(c, cn, a, an, b, bn, m, mn) ;
 bu_divmod(c, cn, a, an, b, bn, m, mn) ;
 bu_invmod(c, cn, m, mn) ;

bu_addmod() computes c = (a+b) mod m.
bu_submod() computes c = (a-b) mod m.
bu_mulmod() computes c = (a*b) mod m.
a and b must already be numbers modulo m.
The functions return 1 if all went well.