Euclidean Algorithms and Congruences
Modular Inversion and Simultaneous Inversion
Computing modular inverses, and Montgomery's trick for inverting many elements at the cost of one inversion plus multiplications.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0522
Modular inversion is substantially more expensive than modular multiplication. When many inverses are needed, Montgomery's simultaneous inversion trick replaces all but one of them with multiplications — a decisive saving in elliptic curve work.
Single inversion
The inverse of a modulo N is obtained from the extended Euclidean algorithm. An alternative for prime moduli is exponentiation by p - 2, using Fermat's little theorem.
| Method | Cost | Applicability |
|---|---|---|
| Extended Euclidean | Roughly a GCD | Any modulus |
| Exponentiation | About log p multiplications | Prime modulus only |
| Binary extended | Shifts and subtractions | Any odd modulus; good without fast division |
Simultaneous inversion
Montgomery's trick inverts k elements using one inversion and about 3k multiplications.
Montgomery's simultaneous inversion
- Accumulate prefixesCompute running products of the inputs, storing each partial product.
- Invert onceInvert the final total product — the only inversion performed.
- UnwindWalk backwards, recovering each individual inverse by multiplying the running inverse by the stored prefix, then removing that element from the running inverse.
The failure mode is the point
Avoiding inversion entirely
Projective coordinates on elliptic curves defer inversion by carrying a denominator through the group law, requiring only one inversion at the very end. This is the standard approach where inversion is expensive — see elliptic curve arithmetic modulo N.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.3.3. 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.