Computational Number-Theory Engine

Intuition, Vocabulary and Foundations

A computational number-theory engine is a dispatcher surrounded by shared contracts. A request such as “factor 84,” “merge these congruences,” or “evaluate this recurrence” first passes validation and capability routing. The selected module returns a canonical result plus its method, verification status, and resource evidence.

For choose(100,40) mod 72, a small-instance policy may use exact arithmetic, while a scalable policy uses prime powers and CRT. Both must return the same residue in [0,72), but their supported scale differs. Think of the engine as a hospital: intake validates, triage selects a specialist, shared records preserve types, and an independent test checks the outcome.

The engine-wide invariant is contract preservation: each route validates preconditions, returns a canonical typed result, and records enough evidence to replay or verify it. Selection is correct only when the method's domain and resource requirements are satisfied.

Concept	Concrete example	Boundary or non-example	Contract question
Routing	Small `factor` request selects bounded trial division	Dispatch before validating sign and size	Which capability fits this request and budget?
Canonical congruence	$(x\equiv14\pmod{18})$, $(0\le14\lt18)$	Undocumented negative residue	What representation crosses module boundaries?
Factor type	`[(2,2),(3,1),(7,1)]` for $(84)$	Unsorted or unverified factors	Can downstream modules consume it safely?
Resource limit	Declared maximum trial count	Hidden unbounded fallback	How much work may one request consume?
Deterministic seed	`20260923` reproduces randomized tests	Irreproducible failure	Can another run reconstruct the evidence?
Audit event	Request id, method, status, verifier	Logging secrets	What provenance is useful and safe?
Correctness oracle	Substitute CRT output into every congruence	Two methods sharing one bug	What independent property checks the result?
Stable failure	`unsupported-scale`	Returning zero for failure and valid zero	Can callers distinguish failure classes?

Step-by-Step Derivations and Algorithms

The router resolves an operation descriptor containing validator, cost estimator, candidate methods, limits, and verifier. Validation precedes estimation. Selection chooses the simplest method whose assumptions and estimated resources fit policy.

Factorization routes bounded inputs to trial division or sieve metadata and larger supported inputs to primality testing plus Pollard's rho. Congruences use extended Euclid and generalized CRT. Combinatorics distinguishes primes, prime powers, and composites. Recurrences choose iteration, matrices, or Kitamasa; polynomials choose naive, FFT, NTT, or multi-prime reconstruction. Field construction validates characteristic and irreducibility. Query modules classify static, online, updated, or offline workloads before selecting their structures.

Every module supplies verification: factor products reconstruct the input, CRT results satisfy all congruences, recurrence results match iteration on bounded indices, and convolution coefficients match the definition on sampled positions. A verifier failure stops the response rather than silently changing semantics.

Computational Number-Theory Engine algorithm map

flowchart TD
    A[Receive versioned request] --> B[Validate and normalize]
    B --> C[Resolve capability]
    C --> D[Estimate scale and resources]
    D --> E{Supported route?}
    E -->|No| F[Structured unsupported result]
    E -->|Yes| G{Capability family}
    G -->|Integer arithmetic| H[Factor and congruence modules]
    G -->|Algebra| I[Combinatorics recurrence polynomial field]
    G -->|Queries| J[Range and offline modules]
    H --> K[Canonicalize and verify]
    I --> K
    J --> K
    K --> L[Audit and return certificate]

Correctness is compositional: validators establish preconditions, kernels preserve local invariants, canonicalizers establish output contracts, and independent verifiers check observable properties. Routing adds bounded overhead, so total complexity is the selected algorithm plus certificate generation and verification.

Implementation, Complexity and Engineering

The compact reference demonstrates stable request and result shapes, deterministic ids, explicit limits, audit events, method selection, and verification across factorization, CRT, combinations, convolution, and range gcd. Unsupported scale is a normal structured result. A larger engine should separate pure kernels from orchestration, version its serialization schema, support cancellation and memory accounting, and avoid placing secrets in logs.

from dataclasses import dataclass, asdict
from hashlib import sha256
from math import comb, gcd, isqrt
from random import Random


@dataclass(frozen=True)
class Limits:
    max_trials: int = 100000
    max_comb_n: int = 5000
    max_cells: int = 1000000
    max_range: int = 1000000


@dataclass(frozen=True)
class Result:
    ok: bool
    operation: str
    method: str
    value: object
    verified: bool
    error: str | None
    request_id: str


def identity(request):
    return sha256(repr(sorted(request.items())).encode()).hexdigest()[:16]


def egcd(a, b):
    old_r, r, old_s, s = abs(a), abs(b), 1, 0
    while r:
        q = old_r // r
        old_r, r, old_s, s = r, old_r - q*r, s, old_s - q*s
    return old_r, old_s * (-1 if a < 0 else 1)


def factor_small(value, limit):
    if value < 1:
        raise ValueError("positive input required")
    remaining, factors, candidate, trials = value, [], 2, 0
    while candidate*candidate <= remaining:
        trials += 1
        if trials > limit:
            raise OverflowError("trial budget exceeded")
        if remaining % candidate == 0:
            exponent = 0
            while remaining % candidate == 0:
                remaining //= candidate
                exponent += 1
            factors.append((candidate, exponent))
        candidate = 3 if candidate == 2 else candidate + 2
    if remaining > 1:
        factors.append((remaining, 1))
    return factors


def crt_merge(left, right):
    a, m = left
    b, n = right
    if m <= 0 or n <= 0:
        raise ValueError("positive moduli required")
    divisor, coefficient = egcd(m, n)
    difference = b - a
    if difference % divisor:
        return None
    reduced = n // divisor
    step = difference // divisor * coefficient % reduced
    modulus = m * reduced
    return (a + m*step) % modulus, modulus


def convolution(a, b, modulus):
    if modulus <= 0:
        raise ValueError("positive modulus required")
    if not a or not b:
        return []
    result = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            result[i+j] = (result[i+j] + x*y) % modulus
    return result


class Engine:
    def __init__(self, limits=Limits(), seed=20260923):
        self.limits, self.seed, self.audit = limits, seed, []

    def finish(self, request, method, value, verified, error=None):
        result = Result(error is None, request.get("operation", "unknown"),
                        method, value, verified, error, identity(request))
        self.audit.append({"id": result.request_id, "operation": result.operation,
                           "method": method, "ok": result.ok, "verified": verified})
        return result

    def execute(self, request):
        operation = request.get("operation")
        try:
            if operation == "factor":
                value = int(request["value"])
                factors = factor_small(value, self.limits.max_trials)
                product = 1
                for prime, exponent in factors:
                    product *= prime**exponent
                return self.finish(request, "bounded-trial", factors, product == value)

            if operation == "crt":
                answer = (0, 1)
                congruences = [(int(a), int(m)) for a, m in request["congruences"]]
                for congruence in congruences:
                    answer = crt_merge(answer, congruence)
                    if answer is None:
                        break
                verified = answer is None or all(answer[0] % m == a % m for a, m in congruences)
                return self.finish(request, "generalized-crt", answer, verified)

            if operation == "choose":
                n, k, modulus = int(request["n"]), int(request["k"]), int(request["modulus"])
                if n < 0 or modulus <= 0:
                    raise ValueError("invalid combination domain")
                if n > self.limits.max_comb_n:
                    return self.finish(request, "none", None, False, "unsupported-scale")
                value = (comb(n, k) if 0 <= k <= n else 0) % modulus
                return self.finish(request, "exact-then-reduce", value, True)

            if operation == "convolve":
                a, b = list(request["left"]), list(request["right"])
                if len(a)*len(b) > self.limits.max_cells:
                    return self.finish(request, "none", None, False, "unsupported-scale")
                modulus = int(request["modulus"])
                value = convolution(a, b, modulus)
                verified = not value or value[0] == a[0]*b[0] % modulus
                return self.finish(request, "naive-convolution", value, verified)

            if operation == "range_gcd":
                values = list(map(int, request["values"]))
                left, right = int(request["left"]), int(request["right"])
                if len(values) > self.limits.max_range:
                    return self.finish(request, "none", None, False, "unsupported-scale")
                if not 0 <= left < right <= len(values):
                    raise ValueError("invalid half-open range")
                value = 0
                for item in values[left:right]:
                    value = gcd(value, abs(item))
                verified = all(item % value == 0 for item in values[left:right]) if value else all(item == 0 for item in values[left:right])
                return self.finish(request, "range-scan", value, verified)

            return self.finish(request, "none", None, False, "unsupported-capability")
        except (KeyError, TypeError, ValueError, OverflowError) as error:
            return self.finish(request, "validation-or-budget", None, False, str(error))


engine = Engine()
requests = [
    {"operation": "factor", "value": 84},
    {"operation": "crt", "congruences": [(2, 6), (5, 9)]},
    {"operation": "choose", "n": 100, "k": 40, "modulus": 72},
    {"operation": "convolve", "left": [1,2,3], "right": [4,5], "modulus": 998244353},
    {"operation": "range_gcd", "values": [12,18,30,25], "left": 0, "right": 3},
]
results = [engine.execute(request) for request in requests]
assert results[0].value == [(2,2),(3,1),(7,1)]
assert results[1].value == (14,18)
assert results[2].value == comb(100,40) % 72
assert results[3].value == [4,13,22,15]
assert results[4].value == 6
assert all(result.verified for result in results)

rng = Random(engine.seed)
for _ in range(200):
    values = [rng.randint(-100,100) for _ in range(20)]
    left = rng.randrange(20)
    right = rng.randrange(left+1,21)
    result = engine.execute({"operation":"range_gcd","values":values,"left":left,"right":right})
    expected = 0
    for item in values[left:right]:
        expected = gcd(expected, abs(item))
    assert result.value == expected and result.verified

unsupported = engine.execute({"operation":"choose","n":5001,"k":2,"modulus":7})
assert not unsupported.ok and unsupported.error == "unsupported-scale"
print("trace:", [asdict(result) for result in results])
print("audit events:", len(engine.audit))
print("all tests passed")

Choice	Benefit	Failure mode	Mitigation
Capability registry	Central supported-domain map	Router and implementation drift	Generate docs and tests from one registry
Shared result type	Predictable status and evidence	Payload misinterpretation	Version and validate schemas
Deterministic seeds	Reproducible failures	Narrow repeated coverage	Add scheduled varied campaigns
Explicit limits	Bounded latency and memory	Large valid request rejected	Return `unsupported-scale` with roadmap
Independent verifier	Detects integration errors	Shares implementation bug	Prefer substitution or reconstruction
Automatic fallback	Availability	Hidden work or changed semantics	Declare order and charge one budget
Audit trail	Replay and method analysis	Sensitive logging	Record metadata, not secrets
Benchmark threshold	Captures constants	Becomes stale	Version and rerun qualification

Applications, Case Studies and Exercises

An approachable engine reads JSON-lines requests for factorization, CRT, combinations, convolution, and range gcd. Every response carries a request id, method, canonical value, verification status, and explicit failure. A production-shaped engine separates the gateway, estimator, pure workers, caches, benchmark store, and audit sink; new algorithms run in shadow mode before becoming defaults.

Exercises progress from canonical types and route preconditions to certificate proofs and new optimized backends. Debugging targets ambiguous zero, nondeterministic failures, stale caches, coupled verifiers, silent fallbacks, and audit leakage.

Deliverable

Apply Computational Number-Theory Engine

Case study 1 — mixed batch. Submit factorization of $(84)$, CRT for $(2\bmod6)$ and $(5\bmod9)$, $(\binom{100}{40}\bmod72)$, convolution [1,2,3] with [4,5], and gcd of [12,18,30]. Require canonical values, successful verification, unique ids, and one audit event per request.

Case study 2 — qualification. Generate 50,000 requests with seed 20260923. Record latency percentiles, peak memory, method counts, fallbacks, rejections, and verifier failures. Replay failures by id and compare bounded samples with independent oracles. Success means zero unexplained mismatches and no limit violation.

Deliverable. Ship a versioned CLI and module, benchmark report, correctness dossier, and extension roadmap. Map each operation to domain, invariant, complexity, verifier, limits, and failures. Add one optimized backend behind the same API and demonstrate reproducible compatibility tests.

Select algorithms through validated domains and measured budgets, not names or asymptotics alone. Preserve canonical types, deterministic evidence, independent verification, bounded fallbacks, and privacy-aware audit trails at every integration boundary.

Cookie Consent