Engineering / Mathematics — Integer Algorithms
Speeding Up Algorithms via Modular Computation
The modular method for exact computation: bounding the result, computing modulo several primes, and reconstructing.
Executive summary
Exact integer computations frequently produce intermediate values far larger than the final answer. Determinants of integer matrices are the standard example: entries stay small, intermediate minors do not.
The modular method bounds the answer in advance, computes modulo enough small primes to determine it, and reconstructs. Every intermediate stays within a machine word.
Learning objectives
- Recognise intermediate expression swell and its cost.
- Derive a bound on the result to fix the number of primes needed.
- Assemble the full modular pipeline.
01Intermediate expression swell
Gaussian elimination over the rationals on an integer matrix produces fractions whose numerators and denominators grow rapidly, even when the determinant itself is small. The growth is not an artefact of a poor implementation; it is inherent to the elimination order.
The modular method eliminates the swell by never leaving the range of a machine word.
02The pipeline
Bound the answer
Derive an a priori bound H on the absolute value of the result — for determinants, Hadamard's bound from the row norms.
Choose primes
Select distinct primes p₁, ..., p_k, each fitting a machine word, with product exceeding 2H.
Compute modulo each
Run the algorithm in Z_{pᵢ} for each i. All arithmetic is single-precision.
Reconstruct
Chinese remainder the residues to recover the value modulo the product.
Recentre
Map the result into the symmetric range (−H, H] to recover the signed answer.
Hadamard bound: |det A| ≤ ∏ᵢ ||rowᵢ||₂03Unlucky primes and how to handle them
A prime is unlucky if the algorithm behaves differently modulo that prime than over the integers — for elimination, if a pivot that is non-zero over the integers vanishes modulo p.
| Symptom | Cause | Remedy |
|---|---|---|
| Rank drops mod p | p divides a leading minor | Discard p, use another prime |
| Result inconsistent across primes | One or more unlucky primes | Majority agreement, or add primes and recheck |
| Reconstruction unstable as primes are added | Bound H was too small | Recompute the bound or add primes until stable |
Unlucky primes are rare — the bad primes divide a fixed non-zero integer, so only finitely many exist — and random selection from a large pool makes the probability of hitting one negligible. Robust implementations add primes until the reconstructed value stops changing.
04Frequently asked questions
Why not use rational arithmetic with gcd reduction instead?
Because reducing fractions at every step requires a gcd computation per operation, which is more expensive than the arithmetic itself, and the numerators still grow between reductions. The modular method avoids fractions entirely.
How many primes are typically needed?
Enough that their product exceeds twice the bound. For word-size primes near 2^62 and a determinant bound of a few thousand bits, that is a few dozen primes — each computation being fast enough that the total remains far below the direct approach.
Does this apply beyond linear algebra?
Widely. Polynomial gcds, resultants, factorisation over the integers and Groebner basis computation all use modular techniques for the same reason: the answer is small and the intermediates are not.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 63-66.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.