Prime/Number Theory Header/Object for the NTTW C Library. More...
#include <stdlib.h>#include "global.h"
Go to the source code of this file.
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
Prime/Number Theory Header/Object for the NTTW C Library.
NTTW Prime/Number Theory Module
This file defines the functions for Prime numbers and other Number Theory related methods.
This file is part of NTTW Library.
NTTW is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
NTTW is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with NTTW. If not, see <http://www.gnu.org/licenses/>.
Definition in file prime.h.
