Module ntheory

Expand description

Number theory: primality, factorization, divisors, modular arithmetic. Number theory: primality testing, integer factorization, divisors, modular arithmetic, quadratic residues, discrete logarithms, prime counting, continued fractions and classical integer sequences.

Unified API — every function accepts arbitrary-precision integers via impl Into<BigInt>. Small values that fit in i64/u64 automatically take an optimised machine-word fast path; larger values use BigInt arithmetic.

§Primality

isprime is deterministic for n < 3.3·10²⁴ (Miller–Rabin with the first 13 prime bases) and uses the Baillie–PSW test (strong Fermat base 2 + strong Lucas) beyond that. BPSW has no known counterexamples and none exist below 2⁶⁴ (exhaustively verified), but it is not proven deterministic for arbitrary n. is_probable_prime exposes a plain randomized Miller–Rabin test with a caller-chosen round count.

§Factorization

factorint combines trial division by all primes below 2¹⁶, a perfect-power check, Pollard–Brent rho (machine words for n < 2⁶⁴), and Lenstra’s elliptic-curve method (Montgomery curves, stage 1) for larger composites. Every factor returned is prime (verified with isprime); the algorithm never returns a composite as a “prime” — for pathological inputs it may simply take a long time.

§Examples

use symplex::ntheory::{factorint, isprime, gcd, nextprime};
use num_bigint::BigInt;

// Same function works for i64 …
assert!(isprime(104729));

// … and for BigInt
let m61 = BigInt::from(2u64.pow(61) - 1);
assert!(isprime(m61));

// 2^64 + 1 = 274177 × 67280421310721
let f = factorint(BigInt::from(2u128.pow(64) + 1));
assert_eq!(f[0].0, BigInt::from(274177u64));
assert_eq!(f[1].0, BigInt::from(67280421310721u64));

Structs§

PartitionIter: Lazy iterator over the integer partitions of n in reverse lexicographic order (each partition is a non-increasing Vec<u64>).

Functions§

bell: Bell number Bₙ: the number of set partitions of an n-element set (1, 1, 2, 5, 15, 52, 203, …).
bernoulli: Bernoulli number Bₙ as an exact rational, with the convention B₁ = −1/2. Returns None for negative n or n too large to fit in usize.
binomial: Binomial coefficient C(n, k) for integer n (any sign) and k ≥ 0.
binomial_coefficients: The binomial coefficients of (x + y)ⁿ keyed by exponent pair (SymPy binomial_coefficients, which returns the dictionary {(k₁, k₂): C(n, k₁)} with k₁ + k₂ = n). Returned as pairs sorted by k₁.
binomial_coefficients_list: Row n of Pascal’s triangle, [C(n,0), C(n,1), …, C(n,n)] (SymPy binomial_coefficients_list).
carmichael_lambda: Carmichael’s function λ(n): the exponent of the multiplicative group (ℤ/nℤ)×, i.e. the smallest m with aᵐ ≡ 1 (mod n) for all a coprime to n. Returns 0 for n ≤ 0.
catalan: Catalan number Cₙ = (2n)! / ((n+1)! n!) (1, 1, 2, 5, 14, 42, …).
continued_fraction: Simple continued fraction [a₀; a₁, a₂, …] of a rational number.
continued_fraction_convergents: Convergents hₙ/kₙ of a continued fraction [a₀; a₁, a₂, …].
continued_fraction_periodic: Periodic continued fraction of √d for a non-negative integer d: returns (non_periodic, periodic) so that √d = [a₀; (a₁, …, aₖ) repeating].
continued_fraction_reduce: The rational number with the finite simple continued fraction [a₀; a₁, …, aₙ] (SymPy continued_fraction_reduce on a plain list).
continued_fraction_reduce_periodic: The quadratic irrational with the periodic continued fraction [pre₀; pre₁, …, (period₀, …, periodₖ) repeating] (SymPy continued_fraction_reduce([a₀, …, [b₀, …]])), returned as the integer triple (p, q, d) meaning (p + √d) / q.
continued_fraction_reduce_periodic_ex: continued_fraction_reduce_periodic as a symbolic expression (p + √d)/q in ctx, which canonicalises it (√8/2 becomes √2).
crt: Chinese Remainder Theorem (BigInt version).
crt_i64: Chinese Remainder Theorem — convenience wrapper for i64 slices.
derangements: Number of derangements !n (permutations with no fixed point): 1, 0, 1, 2, 9, 44, 265, ….
digits: Digits of |n| in the given base, most significant first. digits(0, b) is [0].
discrete_log: Discrete logarithm: the smallest x ≥ 0 with aˣ ≡ b (mod n).
divisor_count: Returns the number of positive divisors of |n|.
divisor_sigma: Divisor function σₖ(n) = Σ_{d | n} dᵏ over the positive divisors of |n|. σ₀ counts divisors, σ₁ sums them. Returns 0 for n = 0.
divisor_sum: Returns the sum of all positive divisors of |n|.
divisors: Returns all positive divisors of |n| in ascending order.
egyptian_fraction: Greedy (Fibonacci–Sylvester) Egyptian fraction: denominators d₁ < d₂ < … of distinct unit fractions summing to r.
euler_number: Euler (secant) number Eₙ: E₀ = 1, E₂ = −1, E₄ = 5, E₆ = −61, …; odd indices are zero. Returns None for negative n.
factorint: Factorize an integer into prime factors.
factorint_bounded: Bounded partial factorisation for radical extraction.
fibonacci: Fibonacci number Fₙ (F₀ = 0, F₁ = 1), extended to negative indices by F₋ₙ = (−1)ⁿ⁺¹ Fₙ. Fast doubling, O(log n) big-integer multiplications.
gcd: Greatest common divisor of two integers.
gcd_many: Greatest common divisor of a list of integers (always ≥ 0).
gcdex: Extended GCD: (g, x, y) with a·x + b·y = g = gcd(a, b) ≥ 0.
harmonic: Harmonic number Hₙ = 1 + 1/2 + … + 1/n as an exact rational (H₀ = 0). Negative n returns None.
igcd: gcd_many for any integer type convertible to BigInt (i64, u64, i128, BigInt, …).
ilcm: lcm_many for any integer type convertible to BigInt.
iroot: Integer k-th root: the largest r with rᵏ ≤ n.
is_abundant: Is n abundant (σ(n) > 2n)? Requires n ≥ 1.
is_amicable: Are a and b an amicable pair (SymPy is_amicable)? That is, a ≠ b, both positive, and each is the sum of the proper divisors of the other: σ(a) − a = b and σ(b) − b = a.
is_carmichael: Is n a Carmichael number (SymPy is_carmichael)? Korselt’s criterion: n is composite, odd, square-free, and (p − 1) | (n − 1) for every prime p | n. The smallest is 561 = 3·11·17.
is_coprime: Returns true if a and b are coprime (gcd = 1).
is_deficient: Is n deficient (σ(n) < 2n)? Requires n ≥ 1.
is_mersenne_prime: Lucas–Lehmer test: is the Mersenne number 2ᵖ − 1 prime?
is_nthpow_residue: Does xⁿ ≡ a (mod m) have a solution? (SymPy is_nthpow_residue.)
is_palindromic: Is |n| a palindrome in the given base? Bases below 2 return false.
is_perfect: Is n perfect (σ(n) = 2n)? Requires n ≥ 1.
is_perfect_power: Is n a perfect power bᵏ with k ≥ 2?
is_primitive_root: Is g a primitive root modulo n (a generator of (ℤ/nℤ)×)?
is_probable_prime: Randomized Miller–Rabin probable-prime test with rounds random bases (plus base 2).
is_quad_residue: Is a a quadratic residue modulo n (i.e. does x² ≡ a (mod n) have a solution)? Works for any modulus n ≥ 1 by solving the congruence.
is_square: Returns true if n is a perfect square.
isprime: Primality test for any integer.
isqrt: Integer square root: the largest s such that s² ≤ n.
jacobi_symbol: Jacobi symbol (a/n) for odd positive n.
kronecker_symbol: Kronecker symbol (a/n), defined for all integers n.
lcm: Least common multiple of two integers.
lcm_many: Least common multiple of a list of integers (always ≥ 0).
legendre_symbol: Legendre symbol (a/p) for odd prime p.
lucas: Lucas number Lₙ (L₀ = 2, L₁ = 1), extended to negative indices by L₋ₙ = (−1)ⁿ Lₙ.
mobius: Möbius function μ(n).
mod_inverse: Modular inverse of a modulo n, if it exists.
mod_pow: Modular exponentiation: base^exp mod modulus.
multiplicative_order: Alias for n_order.
multiplicity: The multiplicity of p in n: the largest k with pᵏ | n (SymPy multiplicity). Works on absolute values; returns 0 when |p| ≤ 1 or n = 0 (SymPy raises there — the multiplicity of 0 is infinite and ±1 divides everything).
n_order: Multiplicative order of a modulo n: the smallest k ≥ 1 with aᵏ ≡ 1 (mod n). Returns None if n < 1 or gcd(a, n) ≠ 1.
nextprime: Returns the smallest prime strictly greater than n.
npartitions: Alias for partition_count: the number of integer partitions p(n).
nthroot_mod: Every solution x ∈ [0, m) of xⁿ ≡ a (mod m) (SymPy nthroot_mod).
partitions: All integer partitions of n, lazily, in reverse lexicographic order ([n] first, [1, 1, …, 1] last).
perfect_power: Perfect-power decomposition: Some((b, k)) with bᵏ = n, k ≥ 2 maximal and b not itself a perfect power. Negative n are handled with odd k. Returns None for |n| < 2 and for non-powers.
polynomial_congruence: Roots in [0, m) of an integer polynomial modulo m (SymPy polynomial_congruence).
prevprime: Returns the largest prime strictly less than n, or None if no such prime exists (i.e. n ≤ 2).
prime: The n-th prime (1-indexed: prime(1) = 2).
primenu: ν(n): the number of distinct prime factors of |n| (SymPy primenu). 0 for n ∈ {−1, 0, 1}.
primeomega: Ω(n): the number of prime factors of |n| counted with multiplicity (SymPy primeomega). 0 for n ∈ {−1, 0, 1}.
primepi: Prime-counting function π(n): the number of primes ≤ n.
primerange: All primes in the half-open range [a, b), in increasing order.
primes_up_to: Returns all primes up to (and including) limit using the Sieve of Eratosthenes.
primitive_root: Smallest primitive root modulo n, if the group (ℤ/nℤ)× is cyclic (n ∈ {1, 2, 4, pᵏ, 2pᵏ}); None otherwise.
primorial: The product of the first n primes, pₙ# (SymPy primorial(n), i.e. nth=True). primorial(0) = 1 (SymPy rejects n < 1).
primorial_up_to: The product of all primes ≤ n (SymPy primorial(n, nth=False)). 1 for n < 2.
quadratic_residues: The quadratic residues modulo n: the sorted distinct values of x² mod n for 0 ≤ x < n (SymPy quadratic_residues). Includes 0.
rational_lcm_of_denominators: Least common multiple of the denominators of a list of rationals — the factor that clears all denominators at once.
sqrt_mod: A square root of a modulo n, if one exists: the smallest non-negative solution of x² ≡ a (mod n).
sqrt_mod_all: All solutions x ∈ [0, n) of x² ≡ a (mod n), sorted.
totient: Euler’s totient function φ(n).

Module ntheory

Module ntheory Copy item path

§Primality

§Factorization

§Examples

Structs§

Functions§

Module ntheory