@enumeratio/residues

Modular arithmetic for @cortex-js/compute-engine, over bigints: residues, CRT, factoring, every r-th root of a residue, discrete logarithms and primitive roots, plus ResidueClass — an element of $\mathbb{Z}/m$ as a value, after Sage's Mod(a, m). Every head answers exactly or stays unevaluated — no such residue, an unfactorable modulus, more roots than it will list — never approximate.

Primality is Baillie–PSW; factoring is trial division then Pollard's rho, budgeted (RHO_BUDGET) so a hard semiprime declines rather than hangs. PrimePi sieves below PRIME_SIEVE_LIMIT, counts by Lucy_Hedgehog above it, and from a few billion on by the Deléglise–Rivat combinatorial count (primeCountDR), up to PRIME_COUNT_LIMIT. NthPrime counts exactly at an inverse-π estimate and sieves the short gap to p_n, up to PRIME_PI_LIMIT.

Usage

import { declareResidues } from "@enumeratio/residues";

declareResidues(ce);

./src is exported for workspace packages that need the plain TypeScript (test setups, sibling packages in this monorepo). The plain kernels (gcd, powMod, crt, factorInteger, isPrime, …) are also exported directly for use outside an engine.

PowerModList(3, 1/2, 11)   // [5, 6] — the square roots of 3 mod 11
FactorInteger(360)         // [[2, 3], [3, 2], [5, 1]]

Heads

Modular arithmetic

• ChineseRemainder — CRT, also over ResidueClass classes
• ResidueClass — compute-engine's element of $\mathbb{Z}/m$, after Sage's Mod(a, m): arithmetic stays inside one ring, and classes of different moduli never combine
• IntegerMod — the same class with Sage's coercion: classes of different moduli combine in $\mathbb{Z}/\gcd(m, n)$
• QuotientRing(Integers, m) — compute-engine's $\mathbb{Z}/m\mathbb{Z}$, made the collection of its ResidueClass classes (IntegerModRing(m) is its old spelling)
• PowerMod — modular exponentiation, widened to a rational exponent s/r (the least r-th root) and a rational base
• PowerModList — every r-th root of $a^s$ mod $m$
• MultiplicativeOrder — the order of $a$ mod $n$, widened to a discrete log against a target list
• PrimitiveRootList — the primitive roots of a cyclic $(\mathbb{Z}/n)^×$

Also declared without a reference page yet: discreteLog, primitiveRoots, primitiveRootCount, unitsMod, and rootsInCyclicGroup (baby-step giant-step over a generic cyclic group).

See also

@enumeratio/numerals (numerals) sits on top of this package for numeral systems, including a residue-numeral system built from ChineseRemainder. @enumeratio/number-theory (number-theory) extends PowerMod/PowerModList to the Gaussian integers.

---

• Source: packages/symbols/arithmetic/residues
• Depends on: boxes, ce-patches, engine, manifest, structures
• In development, also: config