Multiprecision Arithmetic
Modular Arithmetic and Montgomery Reduction
Modular reduction strategies, Montgomery representation, and how trading division for multiplication accelerates every exponentiation.
Engineering / MathematicsMultiprecision Arithmetic2 min readKV-MATH-0510
Modular arithmetic underlies primality testing, factoring and finite field computation. The addition and subtraction are trivial; the multiplication is where the cost lives, because the naive approach requires a division after every product.
The problem
Computing a product modulo N naively means multiplying, then dividing by N to obtain the remainder. Since division is the most expensive basic operation, and modular multiplication is performed millions of times inside an exponentiation, this is the bottleneck.
Montgomery representation
Montgomery's method removes the division entirely by working in a transformed representation. Choose R, a power of the base larger than N and coprime to it. Represent x by xR mod N.
Montgomery multiplication
- PrecomputeCompute the inverse of -N modulo R. This is one setup cost per modulus.
- MultiplyForm the ordinary product of the two representatives.
- ReduceAdd a multiple of N chosen so the low half becomes zero, then shift right by R. Division by R is free because R is a power of the base.
- CorrectSubtract N once if the result exceeds it.
When it pays
Conversion into and out of Montgomery form costs one Montgomery multiplication each. The method therefore pays off when many modular multiplications are performed with the same modulus, which is exactly the situation in exponentiation.
| Situation | Recommendation |
|---|---|
| Single modular product | Ordinary reduction; conversion overhead dominates |
| Modular exponentiation | Montgomery, decisively |
| Finite field arithmetic with fixed modulus | Montgomery |
| Modulus changes every operation | Barrett or ordinary reduction |
Constraint
Frequently Asked Questions
Does Montgomery form change the results?
Which is faster, Montgomery or Barrett?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.2.5. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.