prime.hpp File Reference

#include "config.hpp"
#include "factory.hpp"
#include "cmp.hpp"
#include "vector.hpp"
#include "std_import.hpp"
#include "prime.cpp"

Go to the source code of this file.

Namespaces
namespace	Arageli
A test for primality.
template<typename T, typename T_factory>
bool	Arageli::is_prime_division (const T &x, const T_factory &tfctr)
	Determines if x is prime via consecutive division by sample divisors.
template<typename T>
bool	Arageli::is_prime_division (const T &x)
	Determines if x is prime via consecutive division by sample divisors.
template<typename T, typename N, typename T_factory>
bool	Arageli::is_pseudoprime_miller_rabin (const T &x, const N &n, const T_factory &tfctr)
	Determines if x is prime via Miller-Rabin algorithm.
template<typename T>
bool	Arageli::is_prime_AKS_classic (const T &n)
	Determines if x is prime.
template<typename T>
bool	Arageli::is_prime_AKS (const T &n)
	Determines if x is prime.
template<typename T, typename N>
bool	Arageli::is_pseudoprime_miller_rabin (const T &x, const N &n)
	Determines if x is prime via Miller-Rabin algorithm.
template<typename T, typename N, typename T_factory>
bool	Arageli::is_pseudoprime_solovay_strassen (const T &x, const N &n, const T_factory &tfctr)
	Determines if x is prime via Solovey-Strassen algorithm.
template<typename T, typename N>
bool	Arageli::is_prime_solovey_strassen (const T &x, const N &n)
	Determines if x is prime via Solovey-Strassen algorithm.
template<typename T, typename T_factory>
bool	Arageli::is_prime (const T &x, const T_factory &tfctr)
	Determines if x is prime via appropriate algorithm for T.
template<typename T>
bool	Arageli::is_prime (const T &x)
	Determines if x is prime via appropriate algorithm for T.
template<typename T, typename T_factory>
bool	Arageli::is_probably_prime (const T &x, const T_factory &tfctr)
	Determines if x is probably prime via appropriate algorithm for T.
template<typename T>
bool	Arageli::is_probably_prime (const T &x)
	Determines if x is probably prime via appropriate algorithm for T.
template<typename Out, typename T>
Out	Arageli::small_primes (Out primes, const T &N)
	Fills sequence with first N primes.
template<typename T, typename N>
int	Arageli::is_prime_small_primes_division (const T &n, const N &np)
template<typename T>
int	Arageli::is_prime_small_primes_division (const T &n)
template<typename T, typename T_factory>
bool	Arageli::is_composite (const T &x, const T_factory &tfctr)
	Determines if x is composite.
template<typename T>
bool	Arageli::is_composite (const T &x)
	Determines if x is composite.
Factorization.
template<typename T1, typename T2, bool REFCNT2, typename T_factory>
vector< T2, REFCNT2 > &	Arageli::factorize_division (T1 x, vector< T2, REFCNT2 > &res, const T_factory &tfctr)
	Factorizes x into a set of prime factors via consecutive division.
template<typename T1, typename T2, bool REFCNT2>
vector< T2, REFCNT2 > &	Arageli::factorize_division (const T1 &x, vector< T2, REFCNT2 > &res)
	Factorizes x into a set of prime factors via consecutive division.
template<typename T, typename T_factory>
vector< T, true >	Arageli::factorize_division (const T &x, const T_factory &tfctr)
	Factorizes x into a set of prime factors via consecutive division.
template<typename T>
vector< T, true >	Arageli::factorize_division (const T &x)
	Factorizes x into a set of prime factors via consecutive division.
template<typename T1, typename T2, bool REFCNT2, typename T_factory>
vector< T2, REFCNT2 > &	Arageli::factorize (const T1 &x, vector< T2, REFCNT2 > &res, const T_factory &tfctr)
	Factorizes x into a set of prime factors via appropriate algorithm for T.
template<typename T1, typename T2, bool REFCNT2>
vector< T2, REFCNT2 > &	Arageli::factorize (const T1 &x, vector< T2, REFCNT2 > &res)
	Factorizes x into a set of prime factors via appropriate algorithm for T.
template<typename T, typename T_factory>
vector< T, true >	Arageli::factorize (const T &x, const T_factory &tfctr)
	Factorizes x into a set of prime factors via appropriate algorithm for T.
template<typename T>
vector< T, true >	Arageli::factorize (const T &x)
	Factorizes x into a set of prime factors via appropriate algorithm for T.
Partial factorization.
template<typename T1, typename T2, bool REFCNT2, typename T3, typename T4>
vector< T2, REFCNT2 > &	Arageli::partial_factorize_division (T1 x, vector< T2, REFCNT2 > &res, const T3 &max, T4 &rest)
	Partialy factorizes x into a set of prime factors via test division.
template<typename T, typename N, typename T_factory>
T	Arageli::pollard_pm1 (const T &n, const N &no_of_iter, const T_factory &tfctr)
	Pollard p-1 method (Simple variant).
template<typename T, typename N>
T	Arageli::pollard_pm1 (const T &n, const N &no_of_iter=10000)
	Pollard p-1 method (Simple variant).
template<typename T, typename T_factory>
T	Arageli::rho_pollard (const T &n, const T_factory &tfctr)
	Pollard's rho algorithm.
template<typename T>
T	Arageli::rho_pollard (const T &n)
	Pollard's rho algorithm.
template<typename T, typename N, typename T_factory>
T	Arageli::brent (const T &n, N no_of_iter, const T_factory &tfctr)
	Pollard's rho algorithm.
template<typename T, typename N>
T	Arageli::brent (const T &n, N no_of_iter)
	Pollard's rho algorithm.
template<typename T, typename T3, typename T4>
vector< T, true >	Arageli::partial_factorize_division (const T &x, const T3 &max, T4 &rest)
	Partialy factorizes x into a set of prime factors via test division.
template<typename T1, typename TT1, typename T2, bool REFCNT2, typename T3>
vector< T2, REFCNT2 > &	Arageli::partial_factorize_division (const T1 &x, vector< T2, REFCNT2 > &res, const T3 &max)
	Partialy factorizes x into a set of prime factors via test division.
template<typename T, typename T3>
vector< T, true >	Arageli::partial_factorize_division (const T &x, const T3 &max)
	Partialy factorizes x into a set of prime factors via test division.
template<typename T1, typename T2, bool REFCNT2, typename T3, typename T4>
vector< T2, REFCNT2 > &	Arageli::partial_factorize (const T1 &x, vector< T2, REFCNT2 > &res, const T3 &max, T4 &rest)
	Partialy factorizes x into a set of prime factors via appropriate algorithm for T.
template<typename T, typename T3, typename T4>
vector< T, true >	Arageli::partial_factorize (const T &x, const T3 &max, T4 &rest)
	Partialy factorizes x into a set of prime factors via appropriate algorithm for T.
template<typename T1, typename TT1, typename T2, bool REFCNT2, typename T3>
vector< T2, REFCNT2 > &	Arageli::partial_factorize (const T1 &x, vector< T2, REFCNT2 > &res, const T3 &max)
	Partialy factorizes x into a set of prime factors via appropriate algorithm for T.
template<typename T, typename T3>
vector< T, true >	Arageli::partial_factorize (const T &x, const T3 &max)
	Partialy factorizes x into a set of prime factors via appropriate algorithm for T.
template<typename T1, typename T2, typename T3, typename T4>
const T4 &	Arageli::factorize_multiplier (T1 x, const T2 &m, T3 &rest, T4 &nm)
	Finds rest and nm such that x = rest * m^nm and rest is not divisible by m; returns reference to nm.
template<typename T1, typename T2, typename T3>
T1	Arageli::factorize_multiplier (const T1 &x, const T2 &m, T3 &rest)
	Finds rest and nm such that x = rest * m^nm and rest is not divisible by m; returns nm.
template<typename T1, typename T2>
T1	Arageli::factorize_multiplier (const T1 &x, const T2 &m)
	Finds rest and nm such that x = rest * m^nm and rest is not divisible by m; returns nm.
Prime number generators.
template<typename T>
T	Arageli::next_prime_successive_checking (T x)
	Finds the next after x prime number via successive test for each number.
template<typename T>
T	Arageli::prev_prime_successive_checking (T x)
	Finds the previous before x prime number via successive test for each number.
template<typename T>
T	Arageli::next_prime (const T &x)
	Finds the next after x prime number via appropriate algorithm.
template<typename T>
T	Arageli::prev_prime (const T &x)
	Finds the previous before x prime number via appropriate algorithm.
template<typename T>
T	Arageli::next_probably_prime (T x)
	Finds the next after x probably prime number via appropriate algorithm.
template<typename T>
T	Arageli::prev_probably_prime (T x)
	Finds the previous before x probably prime number via appropriate algorithm.
template<typename T, typename N>
void	Arageli::rsa_generate_keys (N l, T &c, T &public_key, T &d)
	algorithms.
template<typename T>
T	Arageli::rsa_encyph (const T &x, const T &c, const T &key)
template<typename T>
T	Arageli::rsa_decyph (const T &y, const T &d, const T &key)
template<typename T>
bool	Arageli::is_mersen_prime_degree (const T &n)
	Determines if 2^n-1 is Mersenn prime number.
template<typename T>
T	Arageli::next_mersen_prime_degree (const T &n)
	Gives such k > n that 2^k-1 is Mersenn prime number, and for all k > m > n, 2^m-1 is not.
Defines
#define	ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_PRIME

---

Define Documentation

#define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_PRIME

Definition at line 488 of file prime.hpp.

---