prime.hpp

Go to the documentation of this file.

/*****************************************************************************

    prime.hpp -- tests for prime number and factorization foutine.

    This file is a part of Arageli library.

    Copyright (C) Nikolai Yu. Zolotykh, 1999--2006
    Copyright (C) Aleksey Bader, Russia, 2006

*****************************************************************************/

#ifndef _ARAGELI_prime_hpp_
#define _ARAGELI_prime_hpp_

#include "config.hpp"
#include "factory.hpp"
#include "cmp.hpp"
#include "vector.hpp"

#include "std_import.hpp"


namespace Arageli
{

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



template <typename T, typename T_factory>
bool is_prime_division (const T& x, const T_factory& tfctr);


template <typename T>
inline bool is_prime_division (const T& x)
{ return is_prime_division(x, factory<T>()); }


template <typename T, typename N, typename T_factory>
bool is_pseudoprime_miller_rabin (const T& x, const N& n, const T_factory& tfctr);


template <typename T>
bool is_prime_AKS_classic (const T& n);


template <typename T>
bool is_prime_AKS (const T& n);


template <typename T, typename N>
inline bool is_pseudoprime_miller_rabin (const T& x, const N& n)
{ return is_pseudoprime_miller_rabin(x, n, factory<T>()); }


template <typename T, typename N, typename T_factory>
bool is_pseudoprime_solovay_strassen (const T& x, const N& n, const T_factory& tfctr);


template <typename T, typename N>
inline bool is_prime_solovey_strassen (const T& x, const N& n)
{ return is_pseudoprime_solovay_strassen(x, n, factory<T>()); }



template <typename T, typename T_factory>
inline bool is_prime (const T& x, const T_factory& tfctr)
{ return is_prime_division(x, tfctr); }


template <typename T>
inline bool is_prime (const T& x)
{ return is_prime(x, factory<T>()); }


template <typename T, typename T_factory>
inline bool is_probably_prime (const T& x, const T_factory& tfctr)
{ return is_pseudoprime_solovay_strassen(x, 10, tfctr); }   // WARNING! 10


template <typename T>
inline bool is_probably_prime (const T& x)
{ return is_probably_prime(x, factory<T>()); }


template <typename Out, typename T>
Out small_primes (Out primes, const T& N);

template <typename T, typename N>
int is_prime_small_primes_division (const T& n, const N& np);

template <typename T>
int is_prime_small_primes_division(const T& n)
{ return is_prime_small_primes_division(n, ARAGELI_IS_PRIME_SMALL_PRIMES_DIVISION_NUMBER); }

template <typename T, typename T_factory>
inline bool is_composite (const T& x, const T_factory& tfctr)
{
    return
        !is_null(x) &&
        !is_unit(x) &&
        !is_opposite_unit(x) &&
        !is_prime(x, tfctr);
}


template <typename T>
inline bool is_composite (const T& x)
{ return is_composite(x, factory<T>()); }

// @}


// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



template <typename T1, typename T2, bool REFCNT2, typename T_factory>
vector<T2, REFCNT2>& factorize_division
(T1 x, vector<T2, REFCNT2>& res, const T_factory& tfctr);


template <typename T1, typename T2, bool REFCNT2>
inline vector<T2, REFCNT2>& factorize_division
(const T1& x, vector<T2, REFCNT2>& res)
{ return factorize_division(x, res, factory<T1>()); }


template <typename T, typename T_factory>
inline vector<T, true> factorize_division
(const T& x, const T_factory& tfctr)
{
    vector<T, true> res;
    return factorize_division(x, res, tfctr);
}


template <typename T>
inline vector<T, true> factorize_division (const T& x)
{ return factorize_division(x, factory<T>()); }



template <typename T1, typename T2, bool REFCNT2, typename T_factory>
inline vector<T2, REFCNT2>& factorize
(const T1& x, vector<T2, REFCNT2>& res, const T_factory& tfctr)
{ return factorize_division(x, res, tfctr); }


template <typename T1, typename T2, bool REFCNT2>
inline vector<T2, REFCNT2>& factorize
(const T1& x, vector<T2, REFCNT2>& res)
{ return factorize(x, res, factory<T1>()); }


template <typename T, typename T_factory>
inline vector<T, true> factorize
(const T& x, const T_factory& tfctr)
{
    vector<T, true> res;
    return factorize(x, res, tfctr);
}


template <typename T>
inline vector<T, true> factorize (const T& x)
{ return factorize(x, factory<T>()); }



// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


template
<
    typename T1,
    typename T2, bool REFCNT2,
    typename T3, typename T4
>
vector<T2, REFCNT2>& partial_factorize_division
(T1 x, vector<T2, REFCNT2>& res, const T3& max, T4& rest);


template<typename T, typename N, typename T_factory> 
T pollard_pm1(const T& n, const N& no_of_iter, const T_factory& tfctr);


template<typename T, typename N> 
T pollard_pm1(const T& n, const N& no_of_iter = 10000)
{return pollard_pm1(n, no_of_iter, factory<T>());}



template<typename T, typename T_factory> 
T rho_pollard(const T& n, const T_factory& tfctr);



template<typename T> 
T rho_pollard(const T& n)
{return rho_pollard(n, factory<T>());}


template<typename T, typename N, typename T_factory> 
T brent(const T& n, N no_of_iter, const T_factory& tfctr);


template<typename T, typename N> 
T brent(const T& n, N no_of_iter)
{return brent(n, no_of_iter, factory<T>());}

template <typename T, typename T3, typename T4>
inline vector<T, true> partial_factorize_division
(const T& x, const T3& max, T4& rest)
{
    vector<T, true> res;
    return partial_factorize_division(x, res, max, rest);
}


template
<
    typename T1,
    typename TT1, typename T2, bool REFCNT2,
    typename T3
>
inline vector<T2, REFCNT2>& partial_factorize_division
(const T1& x, vector<T2, REFCNT2>& res, const T3& max)
{
    T1 rest;    // not used
    return partial_factorize_division(x, res, max, rest);
}


template <typename T, typename T3>
inline vector<T, true> partial_factorize_division
(const T& x, const T3& max)
{
    T rest; // not used
    return partial_factorize_division(x, max, rest);
}


template
<
    typename T1,
    typename T2, bool REFCNT2,
    typename T3, typename T4
>
inline vector<T2, REFCNT2>& partial_factorize
(const T1& x, vector<T2, REFCNT2>& res, const T3& max, T4& rest)
{ return partial_factorize_division(x, res, max, rest); }


template <typename T, typename T3, typename T4>
inline vector<T, true> partial_factorize
(const T& x, const T3& max, T4& rest)
{
    vector<T, true> res;
    return partial_factorize(x, res, max, rest);
}


template
<
    typename T1,
    typename TT1, typename T2, bool REFCNT2,
    typename T3
>
inline vector<T2, REFCNT2>& partial_factorize
(const T1& x, vector<T2, REFCNT2>& res, const T3& max)
{
    T1 rest;    // not used
    return partial_factorize(x, res, max, rest);
}


template <typename T, typename T3>
inline vector<T, true> partial_factorize
(const T& x, const T3& max)
{
    T rest; // not used
    return partial_factorize(x, max, rest);
}


template <typename T1, typename T2, typename T3, typename T4>
const T4& factorize_multiplier (T1 x, const T2& m, T3& rest, T4& nm);


template <typename T1, typename T2, typename T3>
T1 factorize_multiplier (const T1& x, const T2& m, T3& rest)
{
    T1 nm;
    factorize_multiplier(x, m, rest, nm);
    return nm;
}


template <typename T1, typename T2>
T1 factorize_multiplier (const T1& x, const T2& m)
{
    T1 rest;
    return factorize_multiplier(x, m, rest);
}

// @}


// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



template <typename T>
T next_prime_successive_checking (T x);



template <typename T>
T prev_prime_successive_checking (T x);


template <typename T>
inline T next_prime (const T& x)
{ return next_prime_successive_checking(x); }


template <typename T>
inline T prev_prime (const T& x)
{ return prev_prime_successive_checking(x); }

template <typename T>
inline T next_probably_prime (T x);


template <typename T>
inline T prev_probably_prime (T x);



// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


template<typename T, typename N>
void rsa_generate_keys(N l, T& c, T& public_key, T& d);

template<typename T>
T rsa_encyph(const T& x,  const T& c, const T& key);

template<typename T>
T rsa_decyph(const T& y,  const T& d, const T& key);




// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++




template <typename T>
inline bool is_mersen_prime_degree (const T& n)
{ return n == next_mersen_prime_degree(n-1); /* WARNING! TEMPORARY! */ }



template <typename T>
T next_mersen_prime_degree (const T& n);




} // namespace Arageli


#ifdef ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE
    #define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_PRIME
    #include "prime.cpp"
    #undef  ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_PRIME
#endif


#endif  //  #ifndef _ARAGELI_prime_hpp_

---