Python API · Submodule

alkahest.number_theory

alkahest.number_theory — integer number theory (V3-1, FLINT-backed).

Public API mirrors common SymPy ntheory entry points: arbitrary-precision arguments are accepted as Python int objects.

class

class number_theory.DirichletChi(conductor: int)

#source

Quadratic Dirichlet character modulo an odd square-free conductor (q \ge 3).

Matches the Jacobi symbol ((\cdot \mid q)) on residues coprime to (q) (otherwise 0).

Properties

conductor

#source

Methods

eval(n)

#source

function

number_theory.discrete_log(residue: int, base: int, modulus: int) → int

#source

Smallest e >= 0 with pow(base, e, modulus) == residue % modulus.

Pohlig–Hellman over the factorisation of the order of base, with baby-step giant-step (Pollard's rho for prime factors above 2**42) in each prime-order subgroup: the cost follows the largest prime factor of ord(base), so 2**127 - 1 (whose p - 1 is smooth) is fast, while a 64-bit prime factor is genuinely hard. A composite modulus is factored, each prime power solved on its own, and the exponent classes merged by the Chinese remainder theorem; base and residue need not be coprime to modulus (discrete_log(2, 2, 12) == 1). The result is verified by pow before it is returned. A composite modulus has to be factored first, so a large hard semiprime costs what factoring it costs (bound it with ak.context(budget=...)).

Raises

NumberTheoryError: E-NT-003 when residue is not a power of base.
BudgetExceededError: E-BUDGET-* when an active ak.context(budget=...) runs out — never a partial exponent.

Examples

Python

>>> discrete_log(13, 3, 17)
4
>>> discrete_log(17, 13, 100)
7

function

number_theory.factorint(n: int) → dict[int, int]

#source

Prime factorisation of n with SymPy-compatible sign handling.

Honours an active Budget: under one, the factorisation climbs a ladder of bounded-effort passes (trial division, then ECM tuned for ever larger factors) and checks the budget between them, handing only cofactors of at most 160 bits to FLINT's full (uninterruptible) factoriser. A composite still unsplit when the budget runs out raises BudgetExceededError (E-BUDGET-*); the overshoot is at most one pass. With no budget the call is unbounded — a product of large primes with no small factor can take arbitrarily long.

function

number_theory.isprime(n: int) → bool

#source

Return True if n is a (proved) prime (fmpz_is_prime).

function

number_theory.jacobi_symbol(a: int, n: int) → int

#source

Jacobi symbol (a | n) for odd integers n > 1.

function

number_theory.nextprime(n: int, proved: bool=True) → int

#source

Smallest prime strictly greater than n.

function

number_theory.nthroot_mod(a: int, k: int, m: int) → int

#source

Some integer x with pow(x, k, m) == a % m for prime modulus m.

function

number_theory.totient(n: int) → int

#source

Euler totient φ(n) for integers n ≥ 1.