Functions

K:/Projects/scplusplus/gpl_releases/nttw/include/prime.h File Reference

Prime/Number Theory Header/Object for the NTTW C Library. More...

#include <stdlib.h>
#include "global.h"
Include dependency graph for prime.h:
This graph shows which files directly or indirectly include this file:

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/>.

Author:
Shekhar S. Chandra, 2008-9

Definition in file prime.h.