Team-Fly
Previous Section Next Section

A.5 Number-Theoretic Functions

unsigned
issqr_l (CLINT a_l, CLINT b_l)

test for square property of a_l, if so, output of square root in b_l 

unsigned
iroot_l (CLINT a_l, CLINT b_l)

integer part of square root of a_l, output in b_l 

void
gcd_l (CLINT a_l, CLINT b_l,
     CLINT g_l)

greatest common divisor of a_l and b_l, output in g_l 

void
xgcd_l (CLINT a_l, CLINT b_l,
     CLINT g_l,
     CLINT u_l, int *sign_u,
     CLINT v_l, int *sign_v)

greatest common divisor of a_l and b_l and representation of gcd in u_l and v_l with sign in sign_u and sign_v 

void
inv_l (CLINT a_l, CLINT n_l,
     CLINT g_l, CLINT i_l)

gcd of a_l mod n_l and inverse of a_l mod n_l 

void
lcm_l (CLINT a_l, CLINT b_l,
     CLINT v_l)

least common multiple of a_l and b_l, output in v_l 

int
chinrem_l (unsigned noofeq,
     clint** coeff_l,
     CLINT x_l)

solution of simultaneous linear congruences, output in x_l 

int
jacobi_l (CLINT a_l,
     CLINT b_l)

Legendre/Jacobi symbol, a_l over b_l 

int
proot_l (CLINT a_l, CLINT p_l,
     CLINT x_l)

square root of a_l mod p_l, output in x_l 

int
root_l (CLINT a_l, CLINT p_l,
     CLINT q_l, CLINT x_l)

square of a_l mod p_l*q_l, output in x_l 

int
primroot_l (CLINT x_l,
     unsigned noofprimes,
     clint** primes_l)

determine a primitive root modulo n, output in x_l 

USHORT
sieve_l (CLINT a_l,
     unsigned noofsmallprimes)

division sieve, division of a_l by small primes

 

int prime_l (CLINT n_l,
unsigned noofsmallprimes,
     unsigned iterations)

Miller-Rabin primality test of n_l with division sieve
Team-Fly Previous Section Next Section