Engineering / Mathematics — Integer Algorithms
Computing in the Integers Modulo n
Implementing arithmetic in Z_n: representative choice, reduction after each operation, inversion, and the cost of each primitive.
Executive summary
Working in Z_n means keeping every intermediate reduced. The operations inherit their cost from integer arithmetic plus a reduction, and the discipline of reducing early is what keeps operand size bounded.
Inversion is the expensive primitive and the only one requiring a gcd computation.
Learning objectives
- Choose a canonical representative and maintain it.
- State the cost of each modular primitive.
- Recognise when inversion can be avoided.
01Representatives and reduction
Elements of Z_n are stored as integers in [0, n). Every operation is followed by a reduction restoring that range, which for addition is a conditional subtraction and for multiplication is a division with remainder.
- Addition
O(ℓ)Add, then subtract n once if the result reaches n - Subtraction
O(ℓ)Subtract, then add n once if negative - Multiplication
O(ℓ²)Multiply to 2ℓ bits, then reduce - Inversion
O(ℓ²)Extended Euclid; same order but a much larger constant - Exponentiation
O(k · ℓ²)k squarings and up to k multiplications
02Inversion and its avoidance
The inverse of a modulo n exists exactly when gcd(a, n) = 1 and is computed by extended Euclid, which returns s with as + nt = 1, so s mod n is the inverse.
For prime moduli Fermat's little theorem offers an alternative: a^{p−2} mod p. This is asymptotically worse — a full exponentiation rather than a gcd — but it is branch-free and constant-time, which matters when resisting timing attacks.
| Method | Cost | Constant time? |
|---|---|---|
| Extended Euclid | O(ℓ²), small constant | No, branches on operand values |
| Fermat exponentiation | O(ℓ³) | Yes, with a fixed exponentiation ladder |
| Batch inversion | One inversion + 3n multiplications | Inherits from the single inversion |
03Choosing the modulus representation
Cryptographic implementations rarely store residues in plain form. Montgomery representation multiplies every element by a fixed power of two modulo n, which makes reduction a shift-and-add rather than a division, at the cost of conversion on entry and exit.
Convert in
Multiply each operand by R mod n, once at the start of a computation.
Operate
Montgomery multiplication of the transformed values needs no division, only multiplications and shifts.
Convert out
A single Montgomery reduction at the end recovers the ordinary representative.
The transformation pays for itself whenever more than a handful of modular multiplications share a modulus, which is every exponentiation. For a single multiplication it is a loss.
04Frequently asked questions
Is reducing after every operation always necessary?
Not always, and lazy reduction is a real optimisation. Sums can be allowed to grow while headroom remains in the representation, reducing only before a multiplication. This requires careful bookkeeping of the maximum possible magnitude at each point.
Why is inversion so much more expensive in practice than multiplication?
Because extended Euclid is inherently sequential and data-dependent, with a loop count depending on the operands and poor instruction-level parallelism. Its asymptotic class matches multiplication but its constant is an order of magnitude larger.
Does Montgomery representation change any results?
No, it is a change of representative only. Every value in Montgomery form corresponds to exactly one residue class, and converting out recovers the ordinary answer.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 48-51.
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.