ntheory.h

Go to the documentation of this file.

 
#ifndef SYMENGINE_NTHEORY_H
#define SYMENGINE_NTHEORY_H
 
#include <symengine/integer.h>
 
namespace SymEngine
{
 
// Prime Functions
SYMENGINE_EXPORT int probab_prime_p(const Integer &a, unsigned reps = 25);
SYMENGINE_EXPORT RCP<const Integer> nextprime(const Integer &a);
 
// Basic Number-theoretic functions
SYMENGINE_EXPORT RCP<const Integer> gcd(const Integer &a, const Integer &b);
SYMENGINE_EXPORT RCP<const Integer> lcm(const Integer &a, const Integer &b);
SYMENGINE_EXPORT
void gcd_ext(const Ptr<RCP<const Integer>> &g, const Ptr<RCP<const Integer>> &s,
             const Ptr<RCP<const Integer>> &t, const Integer &a,
             const Integer &b);
SYMENGINE_EXPORT RCP<const Integer> mod(const Integer &n, const Integer &d);
SYMENGINE_EXPORT RCP<const Integer> quotient(const Integer &n,
                                             const Integer &d);
SYMENGINE_EXPORT
void quotient_mod(const Ptr<RCP<const Integer>> &q,
                  const Ptr<RCP<const Integer>> &r, const Integer &a,
                  const Integer &b);
SYMENGINE_EXPORT RCP<const Integer> mod_f(const Integer &n, const Integer &d);
SYMENGINE_EXPORT RCP<const Integer> quotient_f(const Integer &n,
                                               const Integer &d);
SYMENGINE_EXPORT
void quotient_mod_f(const Ptr<RCP<const Integer>> &q,
                    const Ptr<RCP<const Integer>> &r, const Integer &a,
                    const Integer &b);
SYMENGINE_EXPORT
int mod_inverse(const Ptr<RCP<const Integer>> &b, const Integer &a,
                const Integer &m);
 
SYMENGINE_EXPORT
bool crt(const Ptr<RCP<const Integer>> &R,
         const std::vector<RCP<const Integer>> &rem,
         const std::vector<RCP<const Integer>> &mod);
 
SYMENGINE_EXPORT RCP<const Integer> fibonacci(unsigned long n);
 
SYMENGINE_EXPORT
void fibonacci2(const Ptr<RCP<const Integer>> &g,
                const Ptr<RCP<const Integer>> &s, unsigned long n);
 
SYMENGINE_EXPORT RCP<const Integer> lucas(unsigned long n);
 
SYMENGINE_EXPORT
void lucas2(const Ptr<RCP<const Integer>> &g, const Ptr<RCP<const Integer>> &s,
            unsigned long n);
 
SYMENGINE_EXPORT RCP<const Integer> binomial(const Integer &n, unsigned long k);
 
SYMENGINE_EXPORT RCP<const Integer> factorial(unsigned long n);
 
SYMENGINE_EXPORT bool divides(const Integer &a, const Integer &b);
 
SYMENGINE_EXPORT int factor(const Ptr<RCP<const Integer>> &f, const Integer &n,
                            double B1 = 1.0);
 
SYMENGINE_EXPORT int factor_trial_division(const Ptr<RCP<const Integer>> &f,
                                           const Integer &n);
 
SYMENGINE_EXPORT int factor_lehman_method(const Ptr<RCP<const Integer>> &f,
                                          const Integer &n);
 
SYMENGINE_EXPORT int factor_pollard_pm1_method(const Ptr<RCP<const Integer>> &f,
                                               const Integer &n,
                                               unsigned B = 10,
                                               unsigned retries = 5);
 
SYMENGINE_EXPORT int factor_pollard_rho_method(const Ptr<RCP<const Integer>> &f,
                                               const Integer &n,
                                               unsigned retries = 5);
 
SYMENGINE_EXPORT void prime_factors(std::vector<RCP<const Integer>> &primes,
                                    const Integer &n);
SYMENGINE_EXPORT void prime_factor_multiplicities(map_integer_uint &primes,
                                                  const Integer &n);
 
SYMENGINE_EXPORT RCP<const Number> bernoulli(unsigned long n);
SYMENGINE_EXPORT RCP<const Number> harmonic(unsigned long n, long m = 1);
// Primitive root calculated is the smallest when n is prime.
SYMENGINE_EXPORT bool primitive_root(const Ptr<RCP<const Integer>> &g,
                                     const Integer &n);
SYMENGINE_EXPORT void
primitive_root_list(std::vector<RCP<const Integer>> &roots, const Integer &n);
SYMENGINE_EXPORT RCP<const Integer> totient(const RCP<const Integer> &n);
SYMENGINE_EXPORT
RCP<const Integer> carmichael(const RCP<const Integer> &n);
SYMENGINE_EXPORT
bool multiplicative_order(const Ptr<RCP<const Integer>> &o,
                          const RCP<const Integer> &a,
                          const RCP<const Integer> &n);
SYMENGINE_EXPORT int legendre(const Integer &a, const Integer &n);
SYMENGINE_EXPORT int jacobi(const Integer &a, const Integer &n);
SYMENGINE_EXPORT int kronecker(const Integer &a, const Integer &n);
SYMENGINE_EXPORT
void nthroot_mod_list(std::vector<RCP<const Integer>> &roots,
                      const RCP<const Integer> &a, const RCP<const Integer> &n,
                      const RCP<const Integer> &m);
SYMENGINE_EXPORT
bool nthroot_mod(const Ptr<RCP<const Integer>> &root,
                 const RCP<const Integer> &a, const RCP<const Integer> &n,
                 const RCP<const Integer> &m);
SYMENGINE_EXPORT
bool powermod(const Ptr<RCP<const Integer>> &powm, const RCP<const Integer> &a,
              const RCP<const Number> &b, const RCP<const Integer> &m);
SYMENGINE_EXPORT
void powermod_list(std::vector<RCP<const Integer>> &pows,
                   const RCP<const Integer> &a, const RCP<const Number> &b,
                   const RCP<const Integer> &m);
 
SYMENGINE_EXPORT vec_integer_class quadratic_residues(const Integer &a);
 
SYMENGINE_EXPORT bool is_quad_residue(const Integer &a, const Integer &p);
SYMENGINE_EXPORT bool is_nth_residue(const Integer &a, const Integer &n,
                                     const Integer &mod);
// mu(n) = 1 if n is a square-free positive integer with an even number of prime
// factors
// mu(n) = −1 if n is a square-free positive integer with an odd number of prime
// factors
// mu(n) = 0 if n has a squared prime factor
SYMENGINE_EXPORT int mobius(const Integer &a);
// Mertens Function
// mertens(n) -> Sum of mobius(i) for i from 1 to n
SYMENGINE_EXPORT long mertens(const unsigned long a);
 
SYMENGINE_EXPORT
integer_class mp_polygonal_number(const integer_class &s,
                                  const integer_class &n);
SYMENGINE_EXPORT
integer_class mp_principal_polygonal_root(const integer_class &s,
                                          const integer_class &x);
 
SYMENGINE_EXPORT
std::pair<integer_class, integer_class>
mp_perfect_power_decomposition(const integer_class &n,
                               bool lowest_exponent = false);
 
} // namespace SymEngine
 
#endif