21#define NUT_MAX_PRIMES_32 9
23#define NUT_MAX_PRIMES_64 15
25#define NUT_MAX_PRIMES_128 25
33#define NUT_DIVS_BEFORE_PRIME_CHECK 9
NUT_ATTR_PURE uint64_t nut_Factor_carmichael(const nut_Factors *factors)
Find Carmichael's Lambda function, the smallest exponent m so a^m = 1 for all 0 < a < n.
int nut_Factor_forall_divs_tmptmp(const nut_Factors *restrict factors, int(*f)(const nut_Factors *, uint64_t, void *), void *restrict data)
Call forall_divisors with temporarily allocated dfactors and pfactors structs.
NUT_ATTR_NODISCARD uint64_t nut_u64_factor_heuristic(uint64_t n, uint64_t num_primes, const uint64_t primes[restrict static num_primes], const nut_FactorConf *restrict conf, nut_Factors *restrict factors)
Factor a number using a variety of approaches based on its size.
void nut_Factor_ipow(nut_Factors *factors, uint64_t power)
Raise a factorization to a power, ie multiply all exponents by a constant.
bool nut_u64_is_perfect_power(uint64_t a, uint64_t max, uint64_t *restrict _base, uint64_t *restrict _exp)
Check if a is a perfect power of some integer.
NUT_ATTR_CONST int64_t nut_u64_factor1_lenstra_montgomery(int64_t n, int64_t x, int64_t y, int64_t a, int64_t B)
Same as nut_u64_factor1_lenstra but using a projective Montgomery curve and Montgomery ladder.
const uint64_t nut_small_primes[25]
An array containing the 25 primes up to 100.
NUT_ATTR_PURE uint64_t nut_Factors_prod(const nut_Factors *factors)
Multiply a factorization into a number.
const nut_FactorConf nut_default_factor_conf
Default value for nut_u64_factor_heuristic Use if you don't want to tune the parameters or don't care...
NUT_ATTR_CONST bool nut_u64_is_prime_dmr(uint64_t n)
Check if n is prime using a deterministic Miller-Rabin test.
uint64_t nut_u64_order_mod(uint64_t a, uint64_t n, uint64_t cn, nut_Factors *cn_factors)
Find the multiplicative order of a mod n, the smallest exponent m so a^m = 1.
NUT_ATTR_CONST int64_t nut_u64_factor1_lenstra(int64_t n, int64_t x, int64_t y, int64_t a, int64_t B)
Try to find a factor of a number using Lenstra ecf.
int nut_Factor_forall_divs_le(const nut_Factors *restrict factors, uint64_t d_max, int(*f)(const nut_Factors *, uint64_t, void *), void *restrict data, nut_Factors *restrict dfactors, nut_Factors *restrict pfactors)
Call a given function on each divisor of a number, given its factorization, skipping divisors over a ...
void nut_Factor_divide(nut_Factors *restrict out, const nut_Factors *restrict factors, const nut_Factors *restrict dfactors)
Get the factorization of the quotient of two factorizations.
NUT_ATTR_PURE uint64_t nut_Factor_divcount(const nut_Factors *factors)
Find the number of divisors of a number given its prime factorization, including itself and 1.
int nut_Factor_fprint(FILE *restrict file, const nut_Factors *restrict factors)
Print a factorization of a number.
NUT_ATTR_PURE uint64_t nut_Factor_divtupcount(const nut_Factors *factors, uint64_t k, uint64_t modulus)
Find the number of k-tuples with product n.
uint64_t nut_Factor_circle_latte(const nut_Factors *factors)
Find the number of signed lattice points on a circle whose squared radius has a given factorization,...
void nut_Factor_append(nut_Factors *factors, uint64_t m, uint64_t k)
Add a power of some prime to an existing factorization struct.
NUT_ATTR_CONST uint64_t nut_u64_nth_root(uint64_t a, uint64_t n)
Get the floor of the nth root of a.
int nut_Factor_forall_divs_le_tmptmp(const nut_Factors *restrict factors, uint64_t d_max, int(*f)(const nut_Factors *, uint64_t, void *), void *restrict data)
Call forall_divisors_le with temporarily allocated dfactors and pfactors structs.
int nut_Factor_forall_divs(const nut_Factors *restrict factors, int(*f)(const nut_Factors *, uint64_t, void *), void *data, nut_Factors *restrict dfactors, nut_Factors *restrict pfactors)
Call a given function on each divisor of a number, given its factorization.
NUT_ATTR_MALLOC nut_Factors * nut_make_Factors_ub(uint64_t n, uint64_t num_primes, const uint64_t primes[static num_primes])
Allocate a factors structure that can hold all factors of n, even if it has as many prime factors as ...
NUT_ATTR_PURE uint64_t nut_Factor_phi(const nut_Factors *factors)
Find Euler's Phi function, the number of coprime numbers less than n.
NUT_ATTR_CONST uint64_t nut_u64_factor1_pollard_rho(uint64_t n, uint64_t x)
Try to find a factor of a number using Pollard's Rho algorithm with Floyd cycle finding.
void nut_Factor_combine(nut_Factors *restrict factors, const nut_Factors *restrict factors2, uint64_t k)
Add all prime/power pairs in one factorization to another.
NUT_ATTR_PURE uint64_t nut_Factor_divpowsum(const nut_Factors *factors, uint64_t power)
Find the sum of powers of divisors of a number given its prime factorization, including itself and 1.
NUT_ATTR_MALLOC nut_Factors * nut_make_Factors_w(uint64_t max_primes)
Allocate a factors structure that can hold a given number of distinct primes.
NUT_ATTR_NODISCARD uint64_t nut_u64_factor_trial_div(uint64_t n, uint64_t num_primes, const uint64_t primes[restrict static num_primes], nut_Factors *restrict factors)
Factor out all powers of a given array of primes.
NUT_ATTR_CONST uint64_t nut_u64_factor1_pollard_rho_brent(uint64_t n, uint64_t x, uint64_t m)
Try to find a factor of a number using Pollard's Rho algorithm with Brent cycle finding and gcd coale...
NUT_ATTR_PURE uint64_t nut_Factor_divsum(const nut_Factors *factors)
Find the sum of divisors of a number given its prime factorization, including itself and 1.
NUT_ATTR_CONST uint64_t nut_u64_next_prime_ge(uint64_t n)
Find the next prime >= n.
NUT_ATTR_MALLOC nut_Factors * nut_Factors_copy(const nut_Factors *factors)
Allocate a copy of a factors struct, but with only enough memory to store its current factors and not...
#define NUT_ATTR_ACCESS(...)
Wrapper for gcc's access function annotation - no clang equivalent, and currently disabled because it...
#define NUT_ATTR_NONNULL(...)
Wrapper for gnu::nonnull attr.
#define NUT_ATTR_NODISCARD
Wrapper for nodiscard attr - requires return value be used.
#define NUT_ATTR_PURE
Wrapper for gnu::pure attr - similar to const but the function can read non-volatile memory (includin...
#define NUT_ATTR_CONST
Wrapper for gnu::const attr - such a function has no side effects and cannot read memory.
#define NUT_ATTR_MALLOC
Wrapper for gnu::malloc attr - indicates the function returns a malloc'd pointer that must be free'd.
Configuration/tuning for heuristic factorization.
uint64_t lenstra_max
Use lenstra ecf when factoring numbers at most this large.
uint64_t pollard_stride
How many iterations of Pollard-Rho-Brent to do in between gcd tests.
uint64_t qsieve_max
Currently unused.
uint64_t pollard_max
Use Pollard-Rho-Brent when factoring numbers at most this large.
uint64_t lenstra_bfac
Factorial smoothness bound for Lenstra ecf.