|
Number Theory Utils 0.2.0
|
This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
Functions for dealing with factorization and modular arithmetic on 64 bit integers (not suitable for large integers which may overflow, around 2^31. a bignum-enabled version may be created to handle this)
Definition in file factorization.h.
Go to the source code of this file.
Data Structures | |
| struct | nut_Factors |
| A prime factorization. More... | |
| struct | nut_FactorConf |
| Configuration/tuning for heuristic factorization. More... | |
Macros | |
| #define | NUT_MAX_PRIMES_32 9 |
| The most distinct prime divisors a uint32_t can have. | |
| #define | NUT_MAX_PRIMES_64 15 |
| The most distinct prime divisors a uint64_t can have. | |
| #define | NUT_MAX_PRIMES_128 25 |
| The most distinct prime divisors a uint128_t can have. | |
| #define | NUT_DIVS_BEFORE_PRIME_CHECK 9 |
| Currently unused. | |
Functions | |
| 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_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 possible. | |
| 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 its max capacity if higher. | |
| NUT_ATTR_PURE uint64_t | nut_Factors_prod (const nut_Factors *factors) |
| Multiply a factorization into a number. | |
| 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. | |
| 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_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_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, that is, the number of signed lattice solutions to a^2 + b^2 = k, given k's factorization. | |
| void | nut_Factor_ipow (nut_Factors *factors, uint64_t power) |
| Raise a factorization to a power, ie multiply all exponents by a constant. | |
| 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_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. | |
| 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. | |
| 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. | |
| 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. | |
| 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_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 given bound. | |
| int | nut_Factor_fprint (FILE *restrict file, const nut_Factors *restrict factors) |
| Print a factorization of a number. | |
| void | nut_Factor_append (nut_Factors *factors, uint64_t m, uint64_t k) |
| Add a power of some prime to an existing factorization struct. | |
| 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. | |
| 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_CONST bool | nut_u64_is_prime_dmr (uint64_t n) |
| Check if n is prime using a deterministic Miller-Rabin test. | |
| NUT_ATTR_CONST uint64_t | nut_u64_next_prime_ge (uint64_t n) |
| Find the next prime >= n. | |
| 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_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. | |
| NUT_ATTR_CONST uint64_t | nut_u64_nth_root (uint64_t a, uint64_t n) |
| Get the floor of the nth root of a. | |
| 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 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. | |
| 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 coalescing. | |
| 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. | |
| 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. | |
Variables | |
| const uint64_t | nut_small_primes [25] |
| An array containing the 25 primes up to 100. | |
| 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. | |
| #define NUT_MAX_PRIMES_32 9 |
The most distinct prime divisors a uint32_t can have.
Definition at line 21 of file factorization.h.
| #define NUT_MAX_PRIMES_64 15 |
The most distinct prime divisors a uint64_t can have.
Definition at line 23 of file factorization.h.
| #define NUT_MAX_PRIMES_128 25 |
The most distinct prime divisors a uint128_t can have.
Definition at line 25 of file factorization.h.
| #define NUT_DIVS_BEFORE_PRIME_CHECK 9 |
Currently unused.
How many trial divisions to do before performing randomized prime tests (Miller Rabin). For 64 bit numbers, we can easily make Miller Rabin deterministic in 7 tests, whereas up to 40 would be used to check a large number. BSW and ECPP are also important for checking large primes, because BSW and Miller Rabin together can provide a higher primality confidence faster, whereas ECPP is much slower but provides an easily verifiable proof.
Definition at line 33 of file factorization.h.
| 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.
| [in] | max_primes | the number of distinct primes that should be storable |
| 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 possible.
E.g. 210=2*3*5*7 and 2310=2*3*5*7*11 so 210-2309 can have up to 4 distinct prime factors.
| [in] | n | number up to which the distinct prime factors of any number should be storable |
| [in] | num_primes | number of primes in array |
| [in] | primes | array of primes |
| 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 its max capacity if higher.
| [in] | factors | the struct to copy |
| NUT_ATTR_PURE uint64_t nut_Factors_prod | ( | const nut_Factors * | factors | ) |
Multiply a factorization into a number.
| [in] | factors | pointer to factors struct, as obtained from nut_u64_factor_trial_div |
| 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.
Works by multiplying power + 1 for all prime factors
| [in] | factors | pointer to factors struct, as obtained from nut_u64_factor_trial_div |
| 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.
Works by multiplying (prime**(power+1)-1)/(prime-1) for all prime factors
| [in] | factors | pointer to factors struct, as obtained from nut_u64_factor_trial_div |
| 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.
Note this is NOT the same as the sum of divisors of a number. Works by multiplying (prime**((power+1)*e)-1)/(prime**e-1) for all prime factors, where power is the power of each prime and e is the power of divisors to sum
| [in] | factors | pointer to factors struct, as obtained from nut_u64_factor_trial_div |
| [in] | power | power of divisors to sum |
| 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.
given the factorization of n. Works by multiplying binom(power + k, k) for all prime factors, where power is the power of eaach prime
| [in] | factors | pointer to factors struct, as obtained from nut_u64_factor_trial_div |
| [in] | k | tuple length |
| [in] | modulus | modulus to reduce answer by |
| 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, that is, the number of signed lattice solutions to a^2 + b^2 = k, given k's factorization.
By symmetry, the number of nonnegative lattice solutions is pretty much 1/4th this, except that if k is a perfect square it will be that + 1, since both (sqrt(k), 0) and (0, sqrt(k)) are nonnegative Clasically, this is the number of divisors of k which are congruent to 1 mod 4, minus the number of divisors which are congruent to 3 mod 4.
| void nut_Factor_ipow | ( | nut_Factors * | factors, |
| uint64_t | power | ||
| ) |
Raise a factorization to a power, ie multiply all exponents by a constant.
| [in,out] | factors | factorization to raise to a power |
| [in] | power | power to raise the factorization to |
| 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.
| [in] | factors | the factorization of n for which to compute phi |
| 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.
Always divides phi(n).
| [in] | factors | the factorization of n for which to compute the carmichael function |
| 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.
Always divides carmichael(n). order(a mod xy) = lcm(order(a mod x), order(a mod y)) when x and y are coprime, so to find the order of a mod a range of numbers, it might be most efficient to find order(a mod p^k) for every prime power, and then use the lcm to find it for composite numbers.
| [in] | a | the element to find the order of |
| [in] | n | the modulus |
| [in] | cn | the carmichael function of n. Both this and its factorization are needed, which improves efficiency when calling it for many numbers in a range, but if only a single number is needed, you will need to call some other functions to get that data, see below |
| [in,out] | cn_factors | the factorization of the carmichael function of the modulus, lambda(n). THIS BUFFER IS MODIFIED, if you need to use the factorization for something else, make sure to copy it first (nut_Factors_copy). This can be computed either by factoring n (nut_u64_factor_heuristic) and using nut_Factor_carmichael, or by sieving the factorization for all n (nut_sieve_carmichael) |
| int nut_Factor_forall_divs | ( | const nut_Factors *restrict | factors, |
| int(*)(const nut_Factors *, uint64_t, void *) | f, | ||
| void * | data, | ||
| nut_Factors *restrict | dfactors, | ||
| nut_Factors *restrict | pfactors | ||
| ) |
Call a given function on each divisor of a number, given its factorization.
| [in] | factors | the factorization of n for which to compute all divisors |
| [in] | f | callback function. Arguments are factorization of divisor, divisor, user data (respectively). Should return 0 to continue, or 1 to break. |
| [in,out] | data | user data (allows arbitrary data to be passed in and out of the callback) |
| [in] | dfactors | buffer to store internal work. Should be allocated to hold at least factors->num_primes |
| [in] | pfactors | buffer to store internal work. Should be allocated to hlod at least factors->num_primes |
| int nut_Factor_forall_divs_le | ( | const nut_Factors *restrict | factors, |
| uint64_t | d_max, | ||
| int(*)(const nut_Factors *, uint64_t, void *) | f, | ||
| 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 given bound.
| [in] | factors | the factorization of n for which to compute all divisors |
| [in] | d_max | max divisor to visit. This should be less than the product of factors, otherwise just use forall_divisors |
| [in] | f | callback function. Arguments are factorization of divisor, divisor, user data (respectively). Should return 0 to continue, or 1 to break. |
| [in,out] | data | user data (allows arbitrary data to be passed in and out of the callback) |
| [in] | dfactors | buffer to store internal work. Should be allocated to hold at least factors->num_primes |
| [in] | pfactors | buffer to store internal work. Should be allocated to hlod at least factors->num_primes |
| int nut_Factor_fprint | ( | FILE *restrict | file, |
| const nut_Factors *restrict | factors | ||
| ) |
Print a factorization of a number.
| [in,out] | file | pointer to file to print to |
| [in] | factors | pointer to factorization struct |
| void nut_Factor_append | ( | nut_Factors * | factors, |
| uint64_t | m, | ||
| uint64_t | k | ||
| ) |
Add a power of some prime to an existing factorization struct.
If the input factorization is sorted before this function is called, it will still be sorted after, and if the factor to be added is already present its power will be increased rather than creating a separate entry. The factorization struct must have enough space if an additional entry is needed. Composite numbers or zero powers should not be supplied.
| [in,out] | factors | pointer to factorization struct |
| [in] | m | prime |
| [in] | k | power |
| 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.
If both inputs are sorted, the result will be sorted and no dupliate entries will be created. Acts as if factors_append were called repeatedly.
| [in,out] | factors | pointer to factorization struct which should be extended |
| [in] | factors2 | pointer to factorization struct whose entries will be added to the other struct |
| [in] | k | power to multiply entries of factors2 by, for if some composite number m was discovered where m^k divides n and we have factored m |
| 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.
Both inputs must be sorted, and dfactors must be the factorization of a divisor of factors.
| [out] | out | allocated factorization struct to store the result, must not alias. |
| [in] | factors,dfactors | factorization of the dividend and divisor. |
| NUT_ATTR_CONST bool nut_u64_is_prime_dmr | ( | uint64_t | n | ) |
Check if n is prime using a deterministic Miller-Rabin test.
7 partictular bases are used so that no composite number will falsely be reported as prime for the entire 64-bit range
| [in] | n | number to check for primality |
| NUT_ATTR_CONST uint64_t nut_u64_next_prime_ge | ( | uint64_t | n | ) |
Find the next prime >= n.
| [in] | n | inclusive lower bound for prime |
| 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.
Primesieve is a good general source for primes, but the api for this function is designed to allow giving a specialized list of primes like only primes equal to 1 mod 6 if it is known that all factors have some form, or to provide an empty list when this function is used in a more generic context like nut_u64_factor_heuristic.
| [in] | n | the number to factor |
| [in] | num_primes | the number of primes in the array |
| [in] | primes | the array of primes |
| [out] | factors | pointer to struct where factors will be stored |
| 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.
If conf->pollard_max is greater than 3, the primes array should include at least 2 and 5 to avoid an infinite loop since nut_u64_factor1_pollard_rho can't factor 4 or 25. Currently a configuration struct must be passed. Kraitcheck methods (quadratic sieve and number field sieve) are not implemented because they are useless on 64 bit integers. Parameters to Pollard-Rho-Brent with gcd aggregation and Lenstra ecf are not tuned by this function.
| [in] | n | the number to factor |
| [in] | num_primes | the number of primes in the array to try trial division on (use 25 if using nut_small_primes) |
| [in] | primes | array of primes (can use nut_small_primes) |
| [in] | conf | limits for different algorithms (can use nut_default_factor_conf) |
| [out] | factors | output |
| NUT_ATTR_CONST uint64_t nut_u64_nth_root | ( | uint64_t | a, |
| uint64_t | n | ||
| ) |
Get the floor of the nth root of a.
Uses bitscan to estimate the base 2 log and in turn nth root of a, then uses Newton's method
| [in] | a | the number to take the nth root of |
| [in] | n | root to take |
| 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.
Used in nut_u64_factor_heuristic. max is the max exponent a could possibly be, which is limited because it is a uint64_t. If nothing is known about a, then the max exponent it could be is 63, if it were 2**63. However, if we know that the base of a must be larger than some minimum, such as if we know a is not divisible by any primes up to some point, then we can set a lower limit on the max exponent. For example, if a is 2-rough (not divisible by any primes <= 2), then the minimum possible base is 3, so the maximal exponent is 40 instead. For all primes in the nut_small_primes array, the max exponents are as follows: 2-rough -> min base 3 -> max exponent 40 3 -> 5 -> 27 5 -> 7 -> 22 7 -> 11 -> 18 11 -> 13 -> 17 13 -> 17 -> 15 19 -> 23 -> 14 23 -> 29 -> 13 29 -> 31 -> 12 37 -> 41 -> 11 57 -> 59 -> 10 83 -> 89 -> 9 and going over 100: 137 -> 139 -> 8 251 -> 257 -> 7 563 -> 569 -> 6 1621 -> 1627 -> 5 7129 -> 7151 -> 4 65521 -> 65537 -> 3 2642239 -> 2642257 -> 2 4294967291 -> 4294967311 -> 1 The max exponent can also be brought down if a is known to be small, but depending on context it may or may not be worth computing log(a)/log(p) where p is the largest prime not known to not divide a.
| [in] | a | the number to check for being a perfect power |
| [in] | max | the max exponent a could possibly be. Use eg 63 if unknown, 11 if a has had all factors of primes up to 47 removed. |
| [out] | _base | if a is found to be a perfect power, store the base here |
| [out] | _exp | if a is found to be a perfect power, store the exponent here |
| 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.
Note that this will not find factors of 4 or 25 no matter what x is.
| [in] | n | number to find a factor of |
| [in] | x | random value mod n |
| 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 coalescing.
Note that his will not find factors of 4 or 25 no matter what x is. m does not affect whether x will lead to a factor of n, it just means each iteration will be cheaper but up to 2m extraneous iterations could be performed.
| [in] | n | number to find a factor of |
| [in] | x | random value mod n |
| [in] | m | number of iterations per gcd check |
| 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.
In particular, an affine wierstrass representation is used internally and scalar multiplication is done using a binary "double and add" algorithm.
| [in] | n | number to find a factor of |
| [in] | x,y,a | random values mod n |
| [in] | B | number of trials before giving up (we compute kP for k from 2 to B) |
| 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.
Instead of an affine Wierstrass curve and binary multiplication. This is supposed to be faster but seems to be about the same.
| [in] | n | number to find a factor of |
| [in] | x,y,a | random numbers mod n |
| [in] | B | number of trials before giving up (we compute kP for k from 2 to B) |
|
extern |
An array containing the 25 primes up to 100.
nut_u64_factor1_pollard_rho and nut_u64_factor1_pollard_rho_brent can't find factors of 4 or 25 using the default polynomial, so if using nut_u64_factor_heuristic at least these primes should be used for trial division if the configuration allows pollard rho to be called.