ntheory.h
Go to the documentation of this file.
1 
7 #ifndef SYMENGINE_NTHEORY_H
8 #define SYMENGINE_NTHEORY_H
9 
10 #include <symengine/integer.h>
11 
12 namespace SymEngine
13 {
14 
15 // Prime Functions
17 int probab_prime_p(const Integer &a, unsigned reps = 25);
19 RCP<const Integer> nextprime(const Integer &a);
20 
21 // Basic Number-theoretic functions
23 RCP<const Integer> gcd(const Integer &a, const Integer &b);
25 RCP<const Integer> lcm(const Integer &a, const Integer &b);
27 void gcd_ext(const Ptr<RCP<const Integer>> &g, const Ptr<RCP<const Integer>> &s,
28  const Ptr<RCP<const Integer>> &t, const Integer &a,
29  const Integer &b);
31 RCP<const Integer> mod(const Integer &n, const Integer &d);
33 RCP<const Integer> quotient(const Integer &n, const Integer &d);
35 void quotient_mod(const Ptr<RCP<const Integer>> &q,
36  const Ptr<RCP<const Integer>> &r, const Integer &a,
37  const Integer &b);
39 RCP<const Integer> mod_f(const Integer &n, const Integer &d);
41 RCP<const Integer> quotient_f(const Integer &n, const Integer &d);
43 void quotient_mod_f(const Ptr<RCP<const Integer>> &q,
44  const Ptr<RCP<const Integer>> &r, const Integer &a,
45  const Integer &b);
47 int mod_inverse(const Ptr<RCP<const Integer>> &b, const Integer &a,
48  const Integer &m);
49 
51 bool crt(const Ptr<RCP<const Integer>> &R,
52  const std::vector<RCP<const Integer>> &rem,
53  const std::vector<RCP<const Integer>> &mod);
54 
56 RCP<const Integer> fibonacci(unsigned long n);
57 
59 void fibonacci2(const Ptr<RCP<const Integer>> &g,
60  const Ptr<RCP<const Integer>> &s, unsigned long n);
61 
63 RCP<const Integer> lucas(unsigned long n);
64 
66 void lucas2(const Ptr<RCP<const Integer>> &g, const Ptr<RCP<const Integer>> &s,
67  unsigned long n);
68 
70 RCP<const Integer> binomial(const Integer &n, unsigned long k);
71 
73 RCP<const Integer> factorial(unsigned long n);
74 
76 bool divides(const Integer &a, const Integer &b);
77 
80 int factor(const Ptr<RCP<const Integer>> &f, const Integer &n, double B1 = 1.0);
81 
84 int factor_trial_division(const Ptr<RCP<const Integer>> &f, const Integer &n);
85 
87 int factor_lehman_method(const Ptr<RCP<const Integer>> &f, const Integer &n);
88 
90 int factor_pollard_pm1_method(const Ptr<RCP<const Integer>> &f,
91  const Integer &n, unsigned B = 10,
92  unsigned retries = 5);
93 
95 int factor_pollard_rho_method(const Ptr<RCP<const Integer>> &f,
96  const Integer &n, unsigned retries = 5);
97 
99 void prime_factors(std::vector<RCP<const Integer>> &primes, const Integer &n);
101 void prime_factor_multiplicities(map_integer_uint &primes, const Integer &n);
102 
105 RCP<const Number> bernoulli(unsigned long n);
107 RCP<const Number> harmonic(unsigned long n, long m = 1);
109 // Primitive root calculated is the smallest when n is prime.
110 bool primitive_root(const Ptr<RCP<const Integer>> &g, const Integer &n);
113 void primitive_root_list(std::vector<RCP<const Integer>> &roots,
114  const Integer &n);
116 RCP<const Integer> totient(const RCP<const Integer> &n);
118 RCP<const Integer> carmichael(const RCP<const Integer> &n);
120 bool multiplicative_order(const Ptr<RCP<const Integer>> &o,
121  const RCP<const Integer> &a,
122  const RCP<const Integer> &n);
124 int legendre(const Integer &a, const Integer &n);
126 int jacobi(const Integer &a, const Integer &n);
128 int kronecker(const Integer &a, const Integer &n);
130 void nthroot_mod_list(std::vector<RCP<const Integer>> &roots,
131  const RCP<const Integer> &a, const RCP<const Integer> &n,
132  const RCP<const Integer> &m);
134 bool nthroot_mod(const Ptr<RCP<const Integer>> &root,
135  const RCP<const Integer> &a, const RCP<const Integer> &n,
136  const RCP<const Integer> &m);
139 bool powermod(const Ptr<RCP<const Integer>> &powm, const RCP<const Integer> &a,
140  const RCP<const Number> &b, const RCP<const Integer> &m);
143 void powermod_list(std::vector<RCP<const Integer>> &pows,
144  const RCP<const Integer> &a, const RCP<const Number> &b,
145  const RCP<const Integer> &m);
146 
148 vec_integer_class quadratic_residues(const Integer &a);
149 
151 bool is_quad_residue(const Integer &a, const Integer &p);
153 bool is_nth_residue(const Integer &a, const Integer &n, const Integer &mod);
155 // mu(n) = 1 if n is a square-free positive integer with an even number of prime
156 // factors
157 // mu(n) = −1 if n is a square-free positive integer with an odd number of prime
158 // factors
159 // mu(n) = 0 if n has a squared prime factor
160 int mobius(const Integer &a);
161 // Mertens Function
162 // mertens(n) -> Sum of mobius(i) for i from 1 to n
163 long mertens(const unsigned long a);
164 } // namespace SymEngine
165 #endif
Main namespace for SymEngine package.
Definition: add.cpp:19
bool divides(const Integer &a, const Integer &b)
Definition: ntheory.cpp:159
bool powermod(const Ptr< RCP< const Integer >> &powm, const RCP< const Integer > &a, const RCP< const Number > &b, const RCP< const Integer > &m)
Definition: ntheory.cpp:1431
RCP< const Integer > nextprime(const Integer &a)
Definition: ntheory.cpp:170
int kronecker(const Integer &a, const Integer &n)
Kronecker Function.
Definition: ntheory.cpp:880
void fibonacci2(const Ptr< RCP< const Integer >> &g, const Ptr< RCP< const Integer >> &s, unsigned long n)
Fibonacci n and n-1.
Definition: ntheory.cpp:115
void prime_factor_multiplicities(map_integer_uint &primes_mul, const Integer &n)
Find multiplicities of prime factors of n
Definition: ntheory.cpp:459
RCP< const Integer > gcd(const Integer &a, const Integer &b)
Greatest Common Divisor.
Definition: ntheory.cpp:29
bool nthroot_mod(const Ptr< RCP< const Integer >> &root, const RCP< const Integer > &a, const RCP< const Integer > &n, const RCP< const Integer > &mod)
A solution to x**n == a mod m. Return false if none exists.
Definition: ntheory.cpp:1369
bool primitive_root(const Ptr< RCP< const Integer >> &g, const Integer &n)
Computes a primitive root. Returns false if no primitive root exists.
Definition: ntheory.cpp:678
RCP< const Integer > mod(const Integer &n, const Integer &d)
modulo round toward zero
Definition: ntheory.cpp:64
int mobius(const Integer &a)
Mobius Function.
Definition: ntheory.cpp:1602
RCP< const Integer > lucas(unsigned long n)
Lucas number.
Definition: ntheory.cpp:125
RCP< const Integer > quotient_f(const Integer &n, const Integer &d)
Definition: ntheory.cpp:91
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)
All Solutions to x**n == a mod m. Return false if none exists.
Definition: ntheory.cpp:1399
RCP< const Integer > fibonacci(unsigned long n)
Fibonacci number.
Definition: ntheory.cpp:108
bool is_quad_residue(const Integer &a, const Integer &p)
Returns true if 'a' is a quadratic residue of 'p'.
Definition: ntheory.cpp:1526
RCP< const Integer > mod_f(const Integer &n, const Integer &d)
modulo round toward -inf
Definition: ntheory.cpp:84
RCP< const Integer > quotient(const Integer &n, const Integer &d)
Definition: ntheory.cpp:69
void prime_factors(std::vector< RCP< const Integer >> &prime_list, const Integer &n)
Find prime factors of n
Definition: ntheory.cpp:429
int mod_inverse(const Ptr< RCP< const Integer >> &b, const Integer &a, const Integer &m)
inverse modulo
Definition: ntheory.cpp:54
vec_integer_class quadratic_residues(const Integer &a)
Finds all Quadratic Residues of a Positive Integer.
Definition: ntheory.cpp:1501
int jacobi(const Integer &a, const Integer &n)
Jacobi Function.
Definition: ntheory.cpp:875
RCP< const Integer > lcm(const Integer &a, const Integer &b)
Least Common Multiple.
Definition: ntheory.cpp:47
RCP< const Integer > binomial(const Integer &n, unsigned long k)
Binomial Coefficient.
Definition: ntheory.cpp:143
bool multiplicative_order(const Ptr< RCP< const Integer >> &o, const RCP< const Integer > &a, const RCP< const Integer > &n)
Multiplicative order. Return false if order does not exist.
Definition: ntheory.cpp:840
void quotient_mod_f(const Ptr< RCP< const Integer >> &q, const Ptr< RCP< const Integer >> &r, const Integer &n, const Integer &d)
Definition: ntheory.cpp:98
void primitive_root_list(std::vector< RCP< const Integer >> &roots, const Integer &n)
Definition: ntheory.cpp:762
int factor_trial_division(const Ptr< RCP< const Integer >> &f, const Integer &n)
Definition: ntheory.cpp:419
int factor_pollard_pm1_method(const Ptr< RCP< const Integer >> &f, const Integer &n, unsigned B, unsigned retries)
Factor using Pollard's p-1 method.
Definition: ntheory.cpp:294
int probab_prime_p(const Integer &a, unsigned reps)
Probabilistic Prime.
Definition: ntheory.cpp:165
RCP< const Integer > totient(const RCP< const Integer > &n)
Euler's totient function.
Definition: ntheory.cpp:790
bool is_nth_residue(const Integer &a, const Integer &n, const Integer &mod)
Returns true if 'a' is a nth power residue of 'mod'.
Definition: ntheory.cpp:1570
int factor_pollard_rho_method(const Ptr< RCP< const Integer >> &f, const Integer &n, unsigned retries)
Factor using Pollard's rho methods.
Definition: ntheory.cpp:346
bool crt(const Ptr< RCP< const Integer >> &R, const std::vector< RCP< const Integer >> &rem, const std::vector< RCP< const Integer >> &mod)
Chinese remainder function. Return true when a solution exists.
Definition: ntheory.cpp:550
int factor(const Ptr< RCP< const Integer >> &f, const Integer &n, double B1)
Definition: ntheory.cpp:368
RCP< const Integer > factorial(unsigned long n)
Factorial.
Definition: ntheory.cpp:151
RCP< const Integer > carmichael(const RCP< const Integer > &n)
Carmichael function.
Definition: ntheory.cpp:810
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)
Extended GCD.
Definition: ntheory.cpp:36
void powermod_list(std::vector< RCP< const Integer >> &pows, const RCP< const Integer > &a, const RCP< const Number > &b, const RCP< const Integer > &m)
Definition: ntheory.cpp:1466
RCP< const Number > bernoulli(unsigned long n)
Definition: ntheory.cpp:493
void quotient_mod(const Ptr< RCP< const Integer >> &q, const Ptr< RCP< const Integer >> &r, const Integer &n, const Integer &d)
Definition: ntheory.cpp:74
int legendre(const Integer &a, const Integer &n)
Legendre Function.
Definition: ntheory.cpp:870
RCP< const Number > harmonic(unsigned long n, long m)
Computes the sum of the inverses of the first perfect mth powers.
Definition: ntheory.cpp:520
int factor_lehman_method(const Ptr< RCP< const Integer >> &f, const Integer &n)
Factor using lehman's methods.
Definition: ntheory.cpp:251
void lucas2(const Ptr< RCP< const Integer >> &g, const Ptr< RCP< const Integer >> &s, unsigned long n)
Lucas number n and n-1.
Definition: ntheory.cpp:132