boofun.utils.number_theory

Number theory helpers with optional SymPy support.

This module provides essential number theory utilities for Boolean function analysis, including: - Prime factorization and testing - Euler’s totient function - Binomial coefficients - Modular arithmetic (GCD, CRT, modular inverse) - Prime sieving

Many algorithms in Boolean function analysis require these primitives, particularly for analyzing function structure and cryptographic properties.

Functions

binomial(n, k)	Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!).
binomial_sum(n, k)	Compute sum of binomial coefficients: Σ_{i=0}^{k} C(n, i).
crt(moduli, residues)	Chinese Remainder Theorem solution (value, modulus).
euler_phi(n)	Compute Euler's totient function φ(n).
factor(n)	Return prime factorization of n as a list of prime factors (with multiplicity).
gcd(a, b)	Greatest common divisor via math.gcd.
invmod(a, m)	Modular inverse of a modulo m (raises ValueError if none).
is_prime(n)	Deterministic primality for 64-bit n (SymPy-backed if available).
lcm(a, b)	Compute least common multiple of a and b.
mobius(n)	Compute the Möbius function μ(n).
prime_factorization(n)	Return prime factorization as a dictionary {prime: exponent}.
prime_sieve(upto)	Return primes <= upto via a simple Sieve of Eratosthenes.
totient(n)	Compute Euler's totient function φ(n).

boofun.utils.number_theory.gcd(a: int, b: int) → int

Greatest common divisor via math.gcd.

boofun.utils.number_theory.invmod(a: int, m: int) → int

Modular inverse of a modulo m (raises ValueError if none).

boofun.utils.number_theory.crt(moduli: Sequence[int], residues: Sequence[int]) → Tuple[int, int]

Chinese Remainder Theorem solution (value, modulus).

Raises:

ValueError – If no solution exists (e.g., incompatible moduli).

boofun.utils.number_theory.is_prime(n: int) → bool

Deterministic primality for 64-bit n (SymPy-backed if available).

boofun.utils.number_theory.prime_sieve(upto: int) → List[int]

Return primes <= upto via a simple Sieve of Eratosthenes.

boofun.utils.number_theory.factor(n: int) → List[int]

Return prime factorization of n as a list of prime factors (with multiplicity).

Parameters:

n – Positive integer to factor

Returns:

List of prime factors in ascending order

Example

>>> factor(60)
[2, 2, 3, 5]
>>> factor(17)
[17]

boofun.utils.number_theory.prime_factorization(n: int) → Dict[int, int]

Return prime factorization as a dictionary {prime: exponent}.

Parameters:

n – Positive integer to factor

Returns:

Dictionary mapping primes to their exponents

Example

>>> prime_factorization(60)
{2: 2, 3: 1, 5: 1}

boofun.utils.number_theory.euler_phi(n: int) → int

Compute Euler’s totient function φ(n).

φ(n) = count of integers in [1, n] that are coprime to n.

Uses the formula: φ(n) = n * ∏_{p|n} (1 - 1/p)

Parameters:

n – Positive integer

Returns:

Euler’s totient of n

Example

>>> euler_phi(12)  # 1, 5, 7, 11 are coprime to 12
4

boofun.utils.number_theory.totient(n: int) → int

Compute Euler’s totient function φ(n).

φ(n) = count of integers in [1, n] that are coprime to n.

Uses the formula: φ(n) = n * ∏_{p|n} (1 - 1/p)

Parameters:

n – Positive integer

Returns:

Euler’s totient of n

Example

>>> euler_phi(12)  # 1, 5, 7, 11 are coprime to 12
4

boofun.utils.number_theory.binomial(n: int, k: int) → int

Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!).

Uses iterative computation to avoid large intermediate values.

Parameters:

• n – Total items

• k – Items to choose

Returns:

Number of ways to choose k items from n

Example

>>> binomial(5, 2)
10

boofun.utils.number_theory.binomial_sum(n: int, k: int) → int

Compute sum of binomial coefficients: Σ_{i=0}^{k} C(n, i).

This is useful for counting functions of low degree.

Parameters:

• n – Total items

• k – Maximum selection size

Returns:

Sum of C(n,0) + C(n,1) + … + C(n,k)

Example

>>> binomial_sum(5, 2)  # C(5,0) + C(5,1) + C(5,2) = 1 + 5 + 10
16

boofun.utils.number_theory.lcm(a: int, b: int) → int

Compute least common multiple of a and b.

Parameters:

• a – Integers

• b – Integers

Returns:

LCM(a, b)

boofun.utils.number_theory.mobius(n: int) → int

Compute the Möbius function μ(n).

μ(n) = 0 if n has a squared prime factor μ(n) = (-1)^k if n is a product of k distinct primes μ(1) = 1

The Möbius function is important in combinatorics and number theory, particularly for Möbius inversion.

Parameters:

n – Positive integer

Returns:

μ(n) ∈ {-1, 0, 1}

Example

>>> mobius(1)
1
>>> mobius(6)  # 6 = 2 * 3, two distinct primes
1
>>> mobius(12)  # 12 = 2^2 * 3, has squared factor
0