EUCLID(3BM)

NAME
getInverse, extendedGcd, gcd

SYNOPSIS
#include <libcrypt.h>

void getInverse(p, q, result)
BigInt p, q, result;

void extendedGcd(u, v, $font B u'$, $font B v'$, gcd)
BigInt u, v, $font B u'$, $font B v'$, gcd;

BigInt gcd(u, v)
BigInt u, v;

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. $getInverse$ returns $p sup size +2 -1 mod~q$ in $result$. $extendedGcd$ is Euclid's extended Greatest Common Divisor algorithm. It is based on the equation:
$u*u' - v*v' ~=~ gcd(u,~v)$. $getInverse$ is just a call to $extendedGcd$ when it is known that $gcd(p, ~q) = 1$.

SEE ALSO
bigInit(3BM), bigTest(3BM), bigBits(3BM), bigToBuf(3BM), bufToBig(3BM), fBigPrint(3BM), atobig(3BM), bigMod(3BM), bigDivide(3BM), bigSubtract(3BM), bigMultiply(3BM)