RSA, ECC, and Diffie-Hellman all boil down to computing A × B mod N, where N is a 2048-bit or 4096-bit prime. The multiplication is expensive but tractable. The mod is the killer — it requires a division, and division circuits are enormous, slow, and don't pipeline well. Montgomery multiplication is the trick that lets hardware do modular reduction using only shifts and adds.

The insight is to represent numbers in a transformed domain. Instead of storing A, you store A' = A × R mod N, where R is a power of 2 larger than N (say R = 2^2048 for a 2048-bit modulus). Now the Montgomery product of A' and B' is:

MonMul(A', B') = A' × B' × R⁻¹ mod N

which happens to equal (A × B)' — the transformed product. So arithmetic stays in the transformed domain.

Why does this help? Because the reduction step uses R = 2^k, and dividing by 2^k is a right shift. The algorithm iterates through bits of B:

• Start with T = 0.
• For each bit b_i of B: T = T + b_i × A. If T is odd, T = T + N (making it even without changing T mod N). Then T = T >> 1.
• After k iterations, T ≈ A × B × R⁻¹ mod N. If T ≥ N, subtract N once.

Every step is an add and a shift. No division, no compare-and-subtract loop, no variable-length reduction. The critical path is one full-width adder plus a mux — perfectly pipelineable.

Real-world example: The RSA engine in a modern secure enclave (Apple's SEP, Intel's PTT, ARM TrustZone crypto blocks) uses Montgomery multiplication almost universally. A 2048-bit RSA signature requires about 2048 modular multiplications (via square-and-multiply). Each Montgomery multiplication takes ~2048 cycles in a bit-serial implementation, or ~64 cycles in a word-serial one with 32-bit chunks. The whole signature completes in a few milliseconds on a dedicated block that would take hundreds of milliseconds on a general-purpose CPU doing schoolbook division.

Rule of thumb: Montgomery multiplication adds a fixed overhead of two conversions (into and out of the transformed domain), each costing one Montgomery multiplication. So it only pays off if you do at least ~3 modular multiplications in a row — which every crypto primitive does, because modular exponentiation chains thousands of them.

The one gotcha: N must be odd (so gcd(N, R) = 1). Every RSA/ECC modulus is either prime or a product of primes, so it's always odd — the algorithm assumes a property that the application always satisfies.