Searching...
No Matches
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
12namespace SymEngine
13{
14
15// Prime Functions
17int probab_prime_p(const Integer &a, unsigned reps = 25);
19RCP<const Integer> nextprime(const Integer &a);
20
21// Basic Number-theoretic functions
23RCP<const Integer> gcd(const Integer &a, const Integer &b);
25RCP<const Integer> lcm(const Integer &a, const Integer &b);
27void 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);
31RCP<const Integer> mod(const Integer &n, const Integer &d);
33RCP<const Integer> quotient(const Integer &n, const Integer &d);
35void quotient_mod(const Ptr<RCP<const Integer>> &q,
36 const Ptr<RCP<const Integer>> &r, const Integer &a,
37 const Integer &b);
39RCP<const Integer> mod_f(const Integer &n, const Integer &d);
41RCP<const Integer> quotient_f(const Integer &n, const Integer &d);
43void quotient_mod_f(const Ptr<RCP<const Integer>> &q,
44 const Ptr<RCP<const Integer>> &r, const Integer &a,
45 const Integer &b);
47int mod_inverse(const Ptr<RCP<const Integer>> &b, const Integer &a,
48 const Integer &m);
49
51bool crt(const Ptr<RCP<const Integer>> &R,
52 const std::vector<RCP<const Integer>> &rem,
53 const std::vector<RCP<const Integer>> &mod);
54
56RCP<const Integer> fibonacci(unsigned long n);
57
59void fibonacci2(const Ptr<RCP<const Integer>> &g,
60 const Ptr<RCP<const Integer>> &s, unsigned long n);
61
63RCP<const Integer> lucas(unsigned long n);
64
66void lucas2(const Ptr<RCP<const Integer>> &g, const Ptr<RCP<const Integer>> &s,
67 unsigned long n);
68
70RCP<const Integer> binomial(const Integer &n, unsigned long k);
71
73RCP<const Integer> factorial(unsigned long n);
74
76bool divides(const Integer &a, const Integer &b);
77
80int factor(const Ptr<RCP<const Integer>> &f, const Integer &n, double B1 = 1.0);
81
84int factor_trial_division(const Ptr<RCP<const Integer>> &f, const Integer &n);
85
87int factor_lehman_method(const Ptr<RCP<const Integer>> &f, const Integer &n);
88
90int factor_pollard_pm1_method(const Ptr<RCP<const Integer>> &f,
91 const Integer &n, unsigned B = 10,
92 unsigned retries = 5);
93
95int factor_pollard_rho_method(const Ptr<RCP<const Integer>> &f,
96 const Integer &n, unsigned retries = 5);
97
99void prime_factors(std::vector<RCP<const Integer>> &primes, const Integer &n);
101void prime_factor_multiplicities(map_integer_uint &primes, const Integer &n);
102
105RCP<const Number> bernoulli(unsigned long n);
107RCP<const Number> harmonic(unsigned long n, long m = 1);
109// Primitive root calculated is the smallest when n is prime.
110bool primitive_root(const Ptr<RCP<const Integer>> &g, const Integer &n);
113void primitive_root_list(std::vector<RCP<const Integer>> &roots,
114 const Integer &n);
116RCP<const Integer> totient(const RCP<const Integer> &n);
118RCP<const Integer> carmichael(const RCP<const Integer> &n);
120bool multiplicative_order(const Ptr<RCP<const Integer>> &o,
121 const RCP<const Integer> &a,
122 const RCP<const Integer> &n);
124int legendre(const Integer &a, const Integer &n);
126int jacobi(const Integer &a, const Integer &n);
128int kronecker(const Integer &a, const Integer &n);
130void 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);
134bool 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);
139bool powermod(const Ptr<RCP<const Integer>> &powm, const RCP<const Integer> &a,
140 const RCP<const Number> &b, const RCP<const Integer> &m);
143void 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
149
151bool is_quad_residue(const Integer &a, const Integer &p);
153bool 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
160int mobius(const Integer &a);
161// Mertens Function
162// mertens(n) -> Sum of mobius(i) for i from 1 to n
163long mertens(const unsigned long a);
164
165integer_class mp_polygonal_number(const integer_class &s,
166 const integer_class &n);
167integer_class mp_principal_polygonal_root(const integer_class &s,
168 const integer_class &x);
169
181mp_perfect_power_decomposition(const integer_class &n,
182 bool lowest_exponent = false);
183
184} // namespace SymEngine
185
186#endif
Main namespace for SymEngine package.
integer_class mp_polygonal_number(const integer_class &s, const integer_class &n)
Numeric calculation of the n:th s-gonal number.
Definition: ntheory.cpp:1648
bool divides(const Integer &a, const Integer &b)
Definition: ntheory.cpp:161
RCP< const Integer > nextprime(const Integer &a)
Definition: ntheory.cpp:172
int kronecker(const Integer &a, const Integer &n)
Kronecker Function.
Definition: ntheory.cpp:882
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:100
void prime_factor_multiplicities(map_integer_uint &primes_mul, const Integer &n)
Find multiplicities of prime factors of n
Definition: ntheory.cpp:461
RCP< const Integer > gcd(const Integer &a, const Integer &b)
Greatest Common Divisor.
Definition: ntheory.cpp:31
RCP< const Integer > mod(const Integer &n, const Integer &d)
modulo round toward zero
Definition: ntheory.cpp:66
int mobius(const Integer &a)
Mobius Function.
Definition: ntheory.cpp:1604
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:134
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:842
RCP< const Integer > lucas(unsigned long n)
Lucas number.
Definition: ntheory.cpp:127
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:1371
RCP< const Integer > quotient_f(const Integer &n, const Integer &d)
Definition: ntheory.cpp:93
void prime_factors(std::vector< RCP< const Integer > > &prime_list, const Integer &n)
Find prime factors of n
Definition: ntheory.cpp:431
RCP< const Integer > fibonacci(unsigned long n)
Fibonacci number.
Definition: ntheory.cpp:110
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:680
bool is_quad_residue(const Integer &a, const Integer &p)
Returns true if 'a' is a quadratic residue of 'p'.
Definition: ntheory.cpp:1528
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:38
RCP< const Integer > mod_f(const Integer &n, const Integer &d)
modulo round toward -inf
Definition: ntheory.cpp:86
RCP< const Integer > quotient(const Integer &n, const Integer &d)
Definition: ntheory.cpp:71
Finds all Quadratic Residues of a Positive Integer.
Definition: ntheory.cpp:1503
int jacobi(const Integer &a, const Integer &n)
Jacobi Function.
Definition: ntheory.cpp:877
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:1433
RCP< const Integer > lcm(const Integer &a, const Integer &b)
Least Common Multiple.
Definition: ntheory.cpp:49
RCP< const Integer > binomial(const Integer &n, unsigned long k)
Binomial Coefficient.
Definition: ntheory.cpp:145
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:1401
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:552
int factor_lehman_method(const Ptr< RCP< const Integer > > &f, const Integer &n)
Factor using lehman's methods.
Definition: ntheory.cpp:253
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:296
std::pair< integer_class, integer_class > mp_perfect_power_decomposition(const integer_class &n, bool lowest_exponent)
Decompose a positive integer into perfect powers.
Definition: ntheory.cpp:1676
int factor(const Ptr< RCP< const Integer > > &f, const Integer &n, double B1)
Definition: ntheory.cpp:370
int factor_trial_division(const Ptr< RCP< const Integer > > &f, const Integer &n)
Definition: ntheory.cpp:421
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:117
int probab_prime_p(const Integer &a, unsigned reps)
Probabilistic Prime.
Definition: ntheory.cpp:167
RCP< const Integer > totient(const RCP< const Integer > &n)
Euler's totient function.
Definition: ntheory.cpp:792
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:1572
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:348
RCP< const Integer > factorial(unsigned long n)
Factorial.
Definition: ntheory.cpp:153
RCP< const Integer > carmichael(const RCP< const Integer > &n)
Carmichael function.
Definition: ntheory.cpp:812
integer_class mp_principal_polygonal_root(const integer_class &s, const integer_class &x)
Numeric calculation of the principal s-gonal root of x.
Definition: ntheory.cpp:1665
void quotient_mod(const Ptr< RCP< const Integer > > &q, const Ptr< RCP< const Integer > > &r, const Integer &n, const Integer &d)
Definition: ntheory.cpp:76
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:1468
RCP< const Number > bernoulli(unsigned long n)
Definition: ntheory.cpp:495
int legendre(const Integer &a, const Integer &n)
Legendre Function.
Definition: ntheory.cpp:872
RCP< const Number > harmonic(unsigned long n, long m)
Computes the sum of the inverses of the first perfect mth powers.
Definition: ntheory.cpp:522
int mod_inverse(const Ptr< RCP< const Integer > > &b, const Integer &a, const Integer &m)
inverse modulo
Definition: ntheory.cpp:56
void primitive_root_list(std::vector< RCP< const Integer > > &roots, const Integer &n)
Definition: ntheory.cpp:764