Engineering / Mathematics — Integer Algorithms
Modular Inverses and Chinese Remaindering
Combining modular inversion with Chinese remaindering to move computations between a composite modulus and its coprime factors.
Executive summary
Modular inversion and Chinese remaindering are the two directions of a single technique: decomposing a computation modulo a composite into independent computations modulo its coprime parts, and reassembling the result.
The reassembly requires an inverse for each part, which is where the two topics meet.
Learning objectives
- Combine inversion and remaindering into a working reconstruction procedure.
- Compare the direct and incremental reconstruction methods.
- Bound the total cost of a modular decomposition.
01The two directions
Project
Reduce a value modulo each of the coprime factors. Cheap: one division per factor.
Compute
Perform the whole computation independently in each Z_{nᵢ}, with smaller operands throughout.
Reconstruct
Reassemble the results into a single value modulo the product, using precomputed inverses.
The saving comes from step two. Multiplication is superlinear, so several small multiplications cost less than one large one. With k factors of equal size and quadratic multiplication, the work drops by roughly a factor of k.
02Incremental reconstruction
The direct formula computes all the inverses up front. An incremental variant merges the residues two at a time and is often preferable, because it needs only one inverse per merge and adapts naturally when factors are discovered progressively.
Incremental Chinese remaindering
residues aᵢ modulo pairwise coprime nᵢx with x ≡ aᵢ (mod nᵢ) for all i- Start with x = a₁ and M = n₁.
- For each subsequent pair (aᵢ, nᵢ):
- Compute u = (aᵢ − x) mod nᵢ.
- Compute v = M⁻¹ mod nᵢ by extended Euclid.
- Set x = x + M · (u v mod nᵢ).
- Set M = M · nᵢ.
- Return x mod M.
O(k · len(M)²) for k factors03Cost accounting
| Step | Cost | Frequency |
|---|---|---|
| Reduce input mod each nᵢ | O(len(M) · len(nᵢ)) | Once per factor |
| Inverse of M mod nᵢ | O(len(nᵢ)²) | Once per merge; precomputable if factors are fixed |
| Multiply and accumulate | O(len(M) · len(nᵢ)) | Once per merge |
| Final reduction | O(len(M)²) | Once |
When the same factor set is reused — the usual case in modular algorithms, where a fixed list of primes is chosen in advance — every inverse is precomputed once and the per-reconstruction cost falls to multiplications and additions only.
04Frequently asked questions
Is the decomposition worthwhile for only two factors?
Yes, and RSA decryption is exactly that case. Two factors of half length each, with quadratic multiplication, gives roughly a fourfold speedup even after reconstruction overhead.
What if the factors are not coprime?
The reconstruction is not well defined. Consistency must be checked on the gcd of each pair, and the result is unique modulo the lcm rather than the product. Modular algorithms avoid the situation by choosing distinct primes.
How are the primes chosen in a modular algorithm?
Large enough that few are needed, small enough to fit a machine word so that arithmetic in each Z_p is single-precision. Primes just below 2^31 or 2^63 are the usual choice, with enough of them that their product exceeds a bound on the true result.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 62-63.
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.