QUAD_RESIDUE(3BM)

NAME
quadResidue, compositeQuadResidue, squareRoot, compositeSquareRoot, bigIsQR, bigJacobi

SYNOPSIS
#include <libcrypt.h>

Boolean quadResidue (BigInt a, BigInt p);

Boolean compositeQuadResidue (BigInt a, BigInt p, BigInt q);

void squareRoot (BigInt a, BigInt p, BigInt root);

void compositeSquareRoot (BigInt a, BigInt p, BigInt q, BigInt root1, BIgInt root2);

Boolean bigIsQR(BigInt a, BigInt p, BigInt q)

int bigJacobi(BigInt a, BigInt b)

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. $a$ is a quadratic residue if $x sup size +2 2 mod~n ~=~ a$ has a solution $x$. If $n$ is prime, $a sup size +2 (n-1)/2 mod ~n ~=~ 1$. If $n$ is composite, $n ~=~ p*q$ for $p$ and $q$ prime, $a$ is a quadratic residue if it is a quadratic residue modulo each prime. In each square root function, it is assumed that the primes are of the form, $p mod 4 ~=~ 3$. For the composite modulus, the square roots are formed using the Chinese remainder theorem to combine the square roots modulo each prime. For the composite modulus, there are 4 roots. $compositeSquareRoot$ returns two of them, $root1$ and $root2$. The others are $n~-~root1$ and $n~-~root2$. $bigJacobi$ calculates the Jacobi symbol (a/b). $bigIsQR$ determines whether a is a quadratic residue mode p*q where p and q are prime. It does this by calculating the Jacobi symbols (a/p) and (a/q). If both are 1, then a is a quadratic residue modulo p*q.

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