Bigint Functions - C Source Code

Aaron Logue, Aug 2013

Here are some functions to perform various arithmetic operations on large positive integers with an emphasis on simplicity and readability. Along with all the usual functions, there is also a bigint random integer, square root, modulo division, base ^ exponent mod, Greatest Common Divisor, Rabin-Miller for probabilistic generation of large prime numbers, compare, shift, and bigint atoi() and itoa() with support for different number bases.

A test program is included. If it reports errors, be sure to set int_type and int2x_type in bigint.h to 32-bit and 64-bit types for your machine's architecture. If you have an older Pentium, for example, you may need to define this:

typedef unsigned long int_type;         /* 32 bits */
typedef unsigned long long int2x_type;  /* 64 bits */
rather than the default, which is this:
typedef unsigned int int_type;     /* 32 bits */
typedef unsigned long int2x_type;  /* 64 bits */
A successful test should look something like this:
$ ./bigint_test
1st product of two primes: 8563786966078250461288199321
2nd product of two primes: 3637937747419875503252803937
Common prime factor found: 38517449536877
bigint_random_n distribution: 3287 3339 3374
All tests passed. Yay!
 
Linux bigint.tar.gz or Windows bigint.zip (includes the skrand code)

Here are some of the more useful functions:

/****************************************************************************
 * bigint_init() : Allocate a new bigint and set it to a small integer value
 ***************************************************************************/
bigint_t * bigint_init(unsigned int bits, int_type val);

/****************************************************************************
 * bigint_set() : Set a bigint to a small integer value
 ***************************************************************************/
void bigint_set(bigint_t * var, int_type val);

/****************************************************************************
 * bigint_copy() : dest = source
 ***************************************************************************/
void bigint_copy(bigint_t * dest, bigint_t * source);

/****************************************************************************
 * bigint_random() : Set bigint to an arbitrarily-wide random value
 ***************************************************************************/
void bigint_random(bigint_t * var, unsigned int bits);

/****************************************************************************
 * bigint_random_n() : Set result to value from 0 to N-1 with uniform dist.
 ***************************************************************************/
void bigint_random_n(bigint_t * n, bigint_t * result);

/****************************************************************************
 * bigint_add() : result = parm1 + parm2
 ***************************************************************************/
void bigint_add(bigint_t * parm1, bigint_t * parm2, bigint_t * result);
 
/****************************************************************************
 * bigint_subtract() : parm1 = parm1 - parm2
 * Negative numbers are undefined; borrows from beyond MSB are dropped.
 ***************************************************************************/
void bigint_subtract(bigint_t * parm1, bigint_t * parm2);

/****************************************************************************
 * bigint_mult() : result = parm1 * parm2
 ***************************************************************************/
void bigint_mult(bigint_t * parm1, bigint_t * parm2, bigint_t * result);

/****************************************************************************
 * bigint_divide() : result = parm1 / parm2
 ***************************************************************************/
void bigint_divide(bigint_t * parm1, bigint_t * parm2, bigint_t * result);
	
/****************************************************************************
 * bigint_mod() : result = parm1 % parm2
 ***************************************************************************/
void bigint_mod(bigint_t * parm1, bigint_t * parm2, bigint_t * result);

/****************************************************************************
 * bigint_pow_mod() : result = base ^ exp % mod
 ***************************************************************************/
void bigint_pow_mod(bigint_t * base, bigint_t * exp, bigint_t * mod,
                    bigint_t * result);

/****************************************************************************
 * bigint_compare()
 * Return -1 if parm1 < parm2, 1 if parm1 > parm2, and 0 if parm1 == parm2
 ***************************************************************************/
int bigint_compare(bigint_t * parm1, bigint_t * parm2);

/****************************************************************************
 * bigint_shift() : parm1 = parm1 << -shift  or  parm1 = parm1 >> shift
 * Negative values shift parm1 left, positive values shift parm1 right
 * You can do big shifts; ie: -128
 ***************************************************************************/
void bigint_shift(bigint_t * parm1, int shift);

/****************************************************************************
 * bigint_rabin_miller() : Performs one Rabin-Miller / Miller-Rabin test
 ***************************************************************************/
int bigint_rabin_miller(bigint_t * a, bigint_t * n);

/****************************************************************************
 * bigint_is_prime() : Performs multiple Rabin-Miller / Miller-Rabin tests
 * See code for how to use the certainty parm to do more or less testing.
 * certainty=3 will produce proven 32-bit primes. certainty=7 will produce
 * proven 48-bit primes. certainty=57 will perform tests with the first
 * 7 primes then perform rabin-miller tests using 50 random numbers less
 * than n.  A 2Ghz laptop should be able to produce a 1024-bit prime in
 * a few minutes using bigint_random and this function.
 ***************************************************************************/
int bigint_is_prime(bigint_t * n, int certainty);

/****************************************************************************
 * bigint_atoi() : Convert strings to bigints using any base from 2 to 16
 ***************************************************************************/
void bigint_atoi(bigint_t * result, char * str, unsigned int base);

/****************************************************************************
 * bigint_itoa() : Convert bigints to strings using any base from 2 to 16
 * Example: str = bigint_itoa(n, 10);
 * NOTE: calls malloc. Caller is responsible for freeing returned string.
 ***************************************************************************/
char * bigint_itoa(bigint_t * n, unsigned int base);

/****************************************************************************
 * bigint_gcd() : Find greatest common divisor
 * Returns 0 if no GCD other than 1 found. Otherwise, 1 with result = GCD.
 ***************************************************************************/
int bigint_gcd(bigint_t * parm1, bigint_t * parm2, bigint_t *result);

/****************************************************************************
 * bigint_sqrt() : result = sqrt(parm1)
 ***************************************************************************/
void bigint_sqrt(bigint_t * parm1, bigint_t * result);

/****************************************************************************
 * bigint_free()
 ***************************************************************************/
void bigint_free(bigint_t * var);