BIGMATH(3BM)

NAME
bigAdd, bigSubtract, bigDivide, bigLeftShift, bigRightShift, bigCompare, bigCopy, bigMultiply, bigMod, bigPow, negate, crtCombine

SYNOPSIS
#include <libcrypt.h>

typedef struct Bignum {
Sign sign;
size_t length; /* length of number (in Ulong units)	*/
size_t space; /* storage space (in Ulong units)	*/
Ulong *num;
} Bignum;
typedef Bignum * BigInt;

void bigAdd(BigInt a, BigInt b, BigInt result)

void bigSubtract(BigInt a, BigInt b, BigInt result)

void bigDivide(BigInt a, BigInt divisor, BigInt quotient, BigInt remainder)

void bigLeftShift(BigInt a, int numbits, BigInt result)

void bigRightShift(BigInt a, int numbits, BigInt result)

void bigAnd(BigInt a, BigInt b, BigInt result)

void bigOr(BigInt a, BigInt b, BigInt result)

void bigXor(BigInt a, BigInt b, BigInt result)

int bigCompare(BigInt a, BigInt b)

void bigCopy(BigInt a, BigInt result)

void bigMultiply(BigInt a, BigInt b, BigInt result)

void bigMod(BigInt a, BigInt modulus, BigInt result)

void bigPow(BigInt a, BigInt exponent, BigInt modulus, BigInt result)

void double_bigPow(BigInt a1, BigInt a2, BigInt exp1, BigInt exp2, BigInt modulus, BigInt result)

Table *g16_bigpow(BigInt a, BigInt modulus, int len_of_exp_in_4bit_nibs)

void brickell_bigpow(Table *table, BigInt exponent, BigInt modulus, BigInt result)

void void negate (BigInt a, BigInt modulus, BigInt result)

void void crtCombine (BigInt a, BigInt b, BigInt p, BigInt q, BigInt c12, BigInt result)

DESCRIPTION

For all of these functions $BigInt$ arguments are assumed to be initialized $BigInts$. $bigInit(0)$ should be used for initialization of empty $BigInts$. If more space is needed than is provided the functions themselves take care of the space allocation. For example:
result = bigInit(0);
bigAdd(a, b, result);

$bigAdd$ adds two $BigInts$ together and stores the result in $result$. $bigSubtract$ subtracts $BigInt ~b$ from $BigInt ~a$ and stores the result in $result$. If the second argument is larger than the first, the sign of the result is negative. $bigTest(b)$ is used to check the sign of a $BigInt$. $bigDivide$ divides $a$ by $divisor$ and stores the quotient in $quotient$ and the remainder in $remainder$.
quotient = bigInit(0);
remainder = bigInit(0);
bigDivide(a, divisor, quotient, remainder);

$bigLeftShift$ and $bigRightShift$ shift their first argument by $numbits$ to the left and right respectively, and place the result in $result$. $bigAnd$, $bigOr$ and $bigXor$ do the obvious. $bigCompare$ compares two $BigInts$. The result of the comparison is an integer which is positive if $a ~>~ b$, negative if $a ~<~ b$ or zero if $a ~=~ b$. $bigCopy$ copies a $BigInt$ into another. $bigMultiply$ multiplies two $BigInts$ using a combination of $O(n sup size +2 log3 )$ and $O(n sup size +2 2 )$ algorithms and places the result in $result$. $bigMod$ returns $a ~mod~ modulus$ in $result$. $bigPow$ computes $result ~=~ a sup size +2 b mod~ n$ using addition chaining tables and Montgomery reduction. $double_bigPow$ computes $result ~=~ {a sup size +2 b} {c sup size +2 d} mod ~p$ If one expects to use modular exponentiation using the same base and modulus (as in El Gamal or Diffie-Hellman systems) one can precompute a table to be used in Brickell's speedup for exponentiation. If the calculation is $r ~=~ {alpha} sup size +2 e mod ~p$, we calculate $table ~=~ g16_bigpow({alpha}, p, length_of_e)$ and $brickell_bigpow(table, e, p, r)$. Here, length_of_e is the number of 4 bit nibbles in the exponent. $negate$ returns $-a~mod ~p$ by calculating $a*(p - 1) ~ mod p$. $crtCombine$ does a Chinese Remainder combination of a and b with respect to primes p and q with coefficient, $c12 ~=~ p ~mod ~q$.

SEE ALSO
bigInit(3BM), bigTest(3BM), bigBits(3BM), bigToBuf(3BM), bufToBig(3BM), fBigPrint(3BM), atobig(3BM)