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.
|
Routines for basic number theory used for NTTs.
