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>
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>
Arageli::pollard_pm1 (const T &n, const N &no_of_iter=10000)
 Pollard p-1 method (Simple variant).
template<typename T, typename T_factory>
Arageli::rho_pollard (const T &n, const T_factory &tfctr)
 Pollard's rho algorithm.
template<typename T>
Arageli::rho_pollard (const T &n)
 Pollard's rho algorithm.
template<typename T, typename N, typename T_factory>
Arageli::brent (const T &n, N no_of_iter, const T_factory &tfctr)
 Pollard's rho algorithm.
template<typename T, typename N>
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>
Arageli::next_prime_successive_checking (T x)
 Finds the next after x prime number via successive test for each number.
template<typename T>
Arageli::prev_prime_successive_checking (T x)
 Finds the previous before x prime number via successive test for each number.
template<typename T>
Arageli::next_prime (const T &x)
 Finds the next after x prime number via appropriate algorithm.
template<typename T>
Arageli::prev_prime (const T &x)
 Finds the previous before x prime number via appropriate algorithm.
template<typename T>
Arageli::next_probably_prime (T x)
 Finds the next after x probably prime number via appropriate algorithm.
template<typename 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>
Arageli::rsa_encyph (const T &x, const T &c, const T &key)
template<typename 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>
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.


Generated on Thu Aug 31 17:38:18 2006 for Arageli by  doxygen 1.4.7