Functions

Number Theory Routines

Routines for basic number theory used for NTTs. More...

Functions

NTTW_DLL_SYM void loadPrimes_Small (nttw_integer **data, size_t *size)
 Loads the first 100 primes in data. Memory is allocated and data is passed by reference.
NTTW_DLL_SYM size_t isPrimeHighlyComposite (const size_t p, size_t *power)
 Is the p-1 a dyadic number. So the Fermat prime 257 will return true.
NTTW_DLL_SYM size_t newHighlyCompositeSize (const size_t p)
 Return the closest dyadic number (16,32,etc.) greater than 2*p-4. Used for Rader's FFT algorithm.
NTTW_DLL_SYM nttw_integer findClosestPrime (const nttw_integer *primeList, const size_t size, const nttw_integer number, size_t *nthPrime, int *isPrime)
 Finds the closest prime which is larger than the number in the primes list provided.
NTTW_DLL_SYM nttw_integer findAlternatePrime (const nttw_integer *primeList, const size_t size, const nttw_integer number)
 Finds an alternate prime p' of the form p' = k*p+1, where p is prime.
NTTW_DLL_SYM void findFactors (const nttw_integer *primeList, const size_t size, const nttw_integer number, nttw_integer **factors, size_t *noOfFactors)
 Finds the unique prime factors of the number using the primes list provided.
NTTW_DLL_SYM nttw_integer findFirstPrimitiveRoot (const nttw_integer prime)
 Finds the smallest primitive root of the prime.
NTTW_DLL_SYM nttw_integer findFirstPrimitiveRoot_Full (const nttw_integer *primes, const size_t noOfPrimes, const nttw_integer modulus)
 Finds the smallest primitive root of the prime using the list of primes provided.
NTTW_DLL_SYM nttw_big_integer euclidean (nttw_big_integer a, nttw_big_integer b, nttw_big_integer *x, nttw_big_integer *y)
 The Extended Euclidean Algorithm for solving congruences. C Version. Returns d = gcd(a,b) and x, y so that ax + by = d. When a and b are coprime, then x is the modular multiplicative inverse of a modulo b.
NTTW_DLL_SYM long euclidean_long (long a, long b, long *x, long *y)
 The Extended Euclidean Algorithm for solving congruences signed version. C Version. Returns d = gcd(a,b) and x, y so that ax + by = d. When a and b are coprime, then x is the modular multiplicative inverse of a modulo b.
NTTW_DLL_SYM nttw_integer modpow (nttw_integer base, nttw_integer exponent, nttw_integer modulus)
 Computes the modular exponentiation of the base to the exponent modulo modulus. Code from Wikipedia.Org.
NTTW_DLL_SYM nttw_big_integer minverse (const nttw_integer num, const nttw_integer mod)
 Computes the Multiplicative inverse using the Extended Euclidean Algorithm.
NTTW_DLL_SYM nttw_big_integer minverse_big (const nttw_big_integer num, const nttw_big_integer mod)
 Computes the Multiplicative inverse using the Extended Euclidean Algorithm. Big Integer Version.
NTTW_DLL_SYM long minverse_signed (const long num, const long mod)
 Computes the Multiplicative inverse using the Extended Euclidean Algorithm. Signed Version.

Detailed Description

Routines for basic number theory used for NTTs.


Function Documentation

euclidean ( nttw_big_integer  a,
nttw_big_integer  b,
nttw_big_integer x,
nttw_big_integer y 
)

The Extended Euclidean Algorithm for solving congruences. C Version. Returns d = gcd(a,b) and x, y so that ax + by = d. When a and b are coprime, then x is the modular multiplicative inverse of a modulo b.

Definition at line 250 of file prime.c.

euclidean_long ( long  a,
long  b,
long *  x,
long *  y 
)

The Extended Euclidean Algorithm for solving congruences signed version. C Version. Returns d = gcd(a,b) and x, y so that ax + by = d. When a and b are coprime, then x is the modular multiplicative inverse of a modulo b.

Definition at line 275 of file prime.c.

findAlternatePrime ( const nttw_integer primeList,
const size_t  size,
const nttw_integer  number 
)

Finds an alternate prime p' of the form p' = k*p+1, where p is prime.

Definition at line 108 of file prime.c.

findClosestPrime ( const nttw_integer primeList,
const size_t  size,
const nttw_integer  number,
size_t *  nthPrime,
int *  isPrime 
)

Finds the closest prime which is larger than the number in the primes list provided.

Parameters:
nthPrime - Stores the nth prime (index) which is closest. e.g. it may be the 21st prime which is closest.
isPrime - Will be set to TRUE if number is a prime.

Definition at line 80 of file prime.c.

findFactors ( const nttw_integer primeList,
const size_t  size,
const nttw_integer  number,
nttw_integer **  factors,
size_t *  noOfFactors 
)

Finds the unique prime factors of the number using the primes list provided.

Parameters:
factors - Is a 1D array passed by reference which will contain the found factors.

Copy into proper sized factors array

Definition at line 135 of file prime.c.

findFirstPrimitiveRoot ( const nttw_integer  prime  ) 

Finds the smallest primitive root of the prime.

Definition at line 176 of file prime.c.

findFirstPrimitiveRoot_Full ( const nttw_integer primes,
const size_t  noOfPrimes,
const nttw_integer  modulus 
)

Finds the smallest primitive root of the prime using the list of primes provided.

Definition at line 213 of file prime.c.

isPrimeHighlyComposite ( const size_t  p,
size_t *  power 
)

Is the p-1 a dyadic number. So the Fermat prime 257 will return true.

Check is p-1 is dyadic. This is normally a Fermat prime.

Definition at line 52 of file prime.c.

loadPrimes_Small ( nttw_integer **  data,
size_t *  size 
)

Loads the first 100 primes in data. Memory is allocated and data is passed by reference.

Definition at line 30 of file prime.c.

minverse ( const nttw_integer  num,
const nttw_integer  mod 
)

Computes the Multiplicative inverse using the Extended Euclidean Algorithm.

Definition at line 319 of file prime.c.

minverse_big ( const nttw_big_integer  num,
const nttw_big_integer  mod 
)

Computes the Multiplicative inverse using the Extended Euclidean Algorithm. Big Integer Version.

Definition at line 329 of file prime.c.

minverse_signed ( const long  num,
const long  mod 
)

Computes the Multiplicative inverse using the Extended Euclidean Algorithm. Signed Version.

Definition at line 339 of file prime.c.

modpow ( nttw_integer  base,
nttw_integer  exponent,
nttw_integer  modulus 
)

Computes the modular exponentiation of the base to the exponent modulo modulus. Code from Wikipedia.Org.

This code is not as fast as the powmod() function in number32.h file. This function is provided to keep the Prime Module self contained.

Definition at line 300 of file prime.c.

newHighlyCompositeSize ( const size_t  p  ) 

Return the closest dyadic number (16,32,etc.) greater than 2*p-4. Used for Rader's FFT algorithm.

Definition at line 70 of file prime.c.