# Montgomery modular multiplication

**Montgomery modular multiplication** is an algorithm for computing products modulo a fixed integer without performing the classical modular reduction step, which requires division. Instead of returning \( a \cdot b \bmod m \) directly, it returns \( a \cdot b \cdot R^{-1} \bmod m \), where \( R \) is a power of the word base chosen larger than the modulus and coprime to it. Operands are held in a shifted representation, the Montgomery form \( aR \bmod m \), in which ordinary multiplication followed by this reduction preserves the representation. The technique was introduced by Peter L. Montgomery, a researcher then known for work in computational number theory, in the paper *Modular Multiplication Without Trial Division* in *Mathematics of Computation* 44(170), pages 519–521, in April 1985<sup>[1](https://cseweb.ucsd.edu/classes/fa06/cse246/montgomery.pdf)</sup>. It has since become one of the most widely used methods for fast modular arithmetic in public-key cryptography, including RSA and elliptic curve systems<sup>[2](https://eprint.iacr.org/2013/882.pdf)</sup><sup> • </sup><sup>[3](https://eprint.iacr.org/2020/665.pdf)</sup>.

| Key fact | Detail |
|---|---|
| Definition | The Montgomery reduction of \( T \) modulo \( m \) with respect to \( R \) is \( TR^{-1} \bmod m \), for \( R > m \), \( \gcd(m, R) = 1 \), and \( 0 < T < mR \)<sup>[4](https://ebrary.net/134667/computer_science/montgomery_reduction)</sup> |
| Origin | Peter L. Montgomery, *Modular Multiplication Without Trial Division*, Mathematics of Computation 44(170): 519–521, April 1985<sup>[1](https://cseweb.ucsd.edu/classes/fa06/cse246/montgomery.pdf)</sup> |
| Core property | For \( \tilde{x} = xR \bmod m \) and \( \tilde{y} = yR \bmod m \), the Montgomery reduction of \( \tilde{x}\tilde{y} \) equals \( xyR \bmod m \), so products stay in Montgomery form<sup>[4](https://ebrary.net/134667/computer_science/montgomery_reduction)</sup> |
| Modulus restriction | The low word of the modulus must be invertible modulo the word base; with a power-of-two base this means the modulus must be odd<sup>[5](https://bearssl.org/bigint.html)</sup> |
| Multiplication cost | A Montgomery multiplication takes about \( 2n^2 + n \) integer multiplications for \( n \)-limb operands, against \( 2n^2 + 2n + 1 \) for multiplication with Barrett reduction<sup>[6](https://github.com/mitschabaude/montgomery/blob/main/doc/zprize22.md)</sup> |
| Software cost | In software, reducing a 2n-bit product modulo an n-bit modulus by Montgomery's method is only slightly more costly than multiplying two n-bit operands<sup>[2](https://eprint.iacr.org/2013/882.pdf)</sup> |
| Library support | OpenSSL exposes BN_mod_mul_montgomery, BN_to_montgomery, and BN_from_montgomery, and applies them automatically inside BN_mod_exp<sup>[7](https://docs.openssl.org/master/man3/BN_mod_mul_montgomery/)</sup> |

## The problem it solves

Computing \( a \cdot b \bmod m \) for the very large operands used in cryptography, several hundred to several thousand bits, involves two steps: a multiple-precision multiplication producing a product of roughly twice the operand length, and a reduction of that product modulo \( m \)<sup>[2](https://eprint.iacr.org/2013/882.pdf)</sup>. The straightforward reduction computes the remainder on division by \( m \) using a multiple-precision division algorithm, an approach called the classical algorithm for modular multiplication<sup>[4](https://ebrary.net/134667/computer_science/montgomery_reduction)</sup>. Integer division in software is extremely expensive for large operands, which makes this approach impractical for cryptographic applications<sup>[2](https://eprint.iacr.org/2013/882.pdf)</sup>.

Montgomery's idea is to replace the reduction \( P \bmod m \) by a computation of the form \( P \cdot 2^{-n} \bmod m \), where \( n \) is the bitlength of \( m \)<sup>[2](https://eprint.iacr.org/2013/882.pdf)</sup>. Divisions by the radix become exact right shifts, and the quotient digit needed at each step is obtained by a single small multiplication rather than by estimating and correcting a division guess. The Handbook of Applied Cryptography notes that the method generalizes a much older technique due to Hensel<sup>[8](https://gulf.edu.sa/assets/lib/cs/handbook-of-applied-cryptography.pdf)</sup>.

## How the algorithm works

Let \( m \) be the modulus and choose \( R \) as a power of the machine word base with \( R > m \) and \( \gcd(m, R) = 1 \)<sup>[4](https://ebrary.net/134667/computer_science/montgomery_reduction)</sup>. If \( m \) is written as a base-\( b \) integer of length \( n \), a typical choice is \( R = b^n \); this satisfies \( R > m \), and \( \gcd(R, m) = 1 \) holds whenever \( m \) is odd, which covers moduli of practical interest such as RSA moduli<sup>[4](https://ebrary.net/134667/computer_science/montgomery_reduction)</sup>.

The reduction of an input \( T \) with \( 0 < T < mR \) proceeds one limb at a time. At each step a value \( q \) is computed so that adding \( q \cdot m \) to the running sum makes its least significant limb zero; the sum is then divided by the radix, which is an exact shift. After all limbs are processed the result lies below \( 2m \), and a single conditional subtraction of \( m \) yields a value in \( [0, 2m) \) or fully reduced form<sup>[9](https://link.springer.com/article/10.1007/s13389-020-00254-3)</sup>. The quantity that makes this work is \( m' = -m^{-1} \bmod 2^{k} \) for a \( k \)-bit word, precomputed once per modulus<sup>[10](https://onlinelibrary.wiley.com/doi/10.1155/2011/127147)</sup>. Because the quotient is derived from the least significant limb, no carries propagate from lower positions and no [Euclidean division](https://www.edgepedia.org/euclidean-division) on words is needed; this is precisely where the method gains its speed over generic reduction<sup>[5](https://bearssl.org/bigint.html)</sup>.

The interleaved form, which computes the product and reduction together, processes the operands limb by limb and after \( m \) iterations returns \( A \cdot B \cdot R^{-1} \bmod N \)<sup>[10](https://onlinelibrary.wiley.com/doi/10.1155/2011/127147)</sup>. A separate reduction-only routine that takes an already-formed product as input allows a faster dedicated squaring algorithm to be used before the reduction step, an advantage the interleaved version cannot offer<sup>[8](https://gulf.edu.sa/assets/lib/cs/handbook-of-applied-cryptography.pdf)</sup>.

## Montgomery representation

The output of a Montgomery product is offset by the factor \( R^{-1} \), so the method is used through a consistent representation. The Montgomery representation of \( a \) modulo \( m \) is \( aR \bmod m \)<sup>[5](https://bearssl.org/bigint.html)</sup>. Within this representation, modular addition behaves normally, since \( aR + bR = (a+b)R \bmod m \), and the Montgomery product of two represented values returns the representation of their product, since \( (aR)(bR)/R = abR \bmod m \)<sup>[5](https://bearssl.org/bigint.html)</sup>.

Conversion in and out uses Montgomery multiplications with special operands. Multiplying \( aR \) by \( 1 \) returns \( a \bmod m \), converting out of the representation; multiplying \( a \) by \( R^2 \bmod m \) returns \( aR \bmod m \), converting in<sup>[5](https://bearssl.org/bigint.html)</sup>. The constant \( R^2 \bmod m \) can be precomputed when the same modulus is reused, which is the case for standard elliptic curves whose field constants are commonly hardcoded<sup>[5](https://bearssl.org/bigint.html)</sup>. An alternative conversion into Montgomery form is repeated doubling, \( kN \) doublings for a \( k \)-bit word base, which is slower but reuses existing code<sup>[5](https://bearssl.org/bigint.html)</sup>.

The offset is harmless in the dominant application. In modular exponentiation, the input is converted to Montgomery form once, all square-and-multiply steps run on Montgomery representations, and a single final multiplication by \( 1 \) converts the result back<sup>[4](https://ebrary.net/134667/computer_science/montgomery_reduction)</sup><sup> • </sup><sup>[11](https://www.intel.com/content/www/us/en/docs/crypto-primitives-library/developer-guide-reference/2025-1/montgomery-reduction-scheme-functions.html)</sup>. The Handbook notes that for a single isolated modular multiplication the classical algorithm can be superior, since it needs no precomputation, while Montgomery multiplication is very effective for modular exponentiation<sup>[8](https://gulf.edu.sa/assets/lib/cs/handbook-of-applied-cryptography.pdf)</sup>.

## Restrictions and variants

The method requires the low word of the modulus to be invertible modulo the word base, so with a power-of-two base the modulus must be odd<sup>[5](https://bearssl.org/bigint.html)</sup>. Even moduli can be handled by splitting \( m = 2^k m' \) with \( m' \) odd, computing modulo each factor separately, and recombining with the Chinese Remainder Theorem, though this is complex to implement in constant time<sup>[5](https://bearssl.org/bigint.html)</sup>.

A practical annoyance is the final conditional subtraction of \( m \), needed when the result is not fully reduced.

## Comparison with Barrett reduction

Barrett reduction is the main alternative general-purpose technique, introduced around the same time roughly 30 years before 2013<sup>[2](https://eprint.iacr.org/2013/882.pdf)</sup>. In multiplication-count terms, a Montgomery multiplication costs about \( 2n^2 + n \) integer multiplications while a multiplication with Barrett reduction costs \( 2n^2 + 2n + 1 \)<sup>[6](https://github.com/mitschabaude/montgomery/blob/main/doc/zprize22.md)</sup>. Barrett has one practical advantage: it computes the ordinary residue \( x \bmod p \) directly, so numbers are stored normally rather than in the shifted Montgomery form, which simplifies debugging and removes the per-element conversion cost, about one Montgomery product per field element in one implementation<sup>[6](https://github.com/mitschabaude/montgomery/blob/main/doc/zprize22.md)</sup>. In that author's measurements the fastest Barrett multiplication took 99 ns against 87 ns for Montgomery, a gap that justified staying with Montgomery<sup>[6](https://github.com/mitschabaude/montgomery/blob/main/doc/zprize22.md)</sup>. Benchmarks on other platforms show the trade can go either way: in a NEON radix-2 number-theoretic transform butterfly on Apple M1 Pro, the Montgomery path cost 0.74 cycles per butterfly against 0.95 for Barrett, a 23% advantage attributed to Montgomery's shorter five-instruction critical path and lower register pressure<sup>[12](https://www.mdpi.com/2079-9292/15/7/1456)</sup>, while on one GPU implementation a Barrett variant without Montgomery conversion was faster at the largest tested size<sup>[13](https://github.com/Artemarius/cuda-zkp-ntt)</sup>.

## Security considerations

The conditional subtraction at the end of a Montgomery multiplication, called the extra reduction, executes only when the intermediate result lies in \( [M, 2M) \), and this data-dependent branch creates timing differences that are the source of side-channel attacks on implementations<sup>[9](https://link.springer.com/article/10.1007/s13389-020-00254-3)</sup>. Countermeasures include performing the final subtraction in a regular fashion so that the same instruction sequence always executes regardless of the operand value<sup>[2](https://eprint.iacr.org/2013/882.pdf)</sup>. The same conditional-subtraction timing behavior exists in Barrett's algorithm, and known timing attacks on Montgomery-based RSA implementations transfer to Barrett implementations<sup>[9](https://link.springer.com/article/10.1007/s13389-020-00254-3)</sup>.

## Hardware and software use

Montgomery multiplication is a standard building block across cryptographic software and hardware. OpenSSL implements it through the BN_mod_mul_montgomery family, applying it automatically in modular exponentiation and exposing it for repeated operations under the same modulus<sup>[7](https://docs.openssl.org/master/man3/BN_mod_mul_montgomery/)</sup>. Intel's cryptography primitives library provides Montgomery reduction, multiplication, and exponentiation functions built around a context holding the modulus, its inverse word, and the Montgomery index<sup>[11](https://www.intel.com/content/www/us/en/docs/crypto-primitives-library/developer-guide-reference/2025-1/montgomery-reduction-scheme-functions.html)</sup>.

In hardware, the algorithm suits FPGA and ASIC implementations because it lets long integers be processed in a fixed radix, generally a power of two, without division<sup>[10](https://onlinelibrary.wiley.com/doi/10.1155/2011/127147)</sup>. Published designs span systolic arrays, high-radix multiplexed architectures, and scalable word-oriented multipliers in the tradition of Tenca and Koç<sup>[10](https://onlinelibrary.wiley.com/doi/10.1155/2011/127147)</sup>. Reported figures illustrate the scale: a constant-time CSIDH key-exchange design completes a 512-by-512-bit schoolbook multiplication in 22 clock cycles and a full Montgomery modular multiplication in 87 cycles<sup>[14](https://arxiv.org/abs/2508.11082)</sup>, and FPGA work on 1024-bit and 2048-bit operands reports throughput improvements of more than 27% and more than 70% respectively over prior state-of-the-art references on [Xilinx Virtex](https://www.edgepedia.org/xilinx-virtex)-7<sup>[15](https://www.sciencedirect.com/science/article/abs/pii/S1383762124000791)</sup>. Beyond RSA and elliptic curve cryptography, Montgomery arithmetic appears in lattice-based standards; NIST [FIPS 204](https://www.edgepedia.org/fips-204) notes that its purpose is to work efficiently with modular values that fit in a 32-bit register<sup>[16](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf)</sup>.

## References

1. [Peter L. Montgomery (1985). Modular Multiplication Without Trial Division. Mathematics of Computation 44(170), 519–521.](https://cseweb.ucsd.edu/classes/fa06/cse246/montgomery.pdf)
2. [Z. Liu and J. Großschädl (2013). New Speed Records for Montgomery Modular Multiplication on 8-bit AVR processors. IACR ePrint 2013/882.](https://eprint.iacr.org/2013/882.pdf)
3. [Montgomery-friendly primes and applications to cryptography. IACR ePrint 2020/665.](https://eprint.iacr.org/2020/665.pdf)
4. [Montgomery reduction. Handbook of Applied Cryptography, Chapter 14 (ebrary reproduction).](https://ebrary.net/134667/computer_science/montgomery_reduction)
5. [BearSSL, Big Integer Design: Montgomery Reduction And Multiplication.](https://bearssl.org/bigint.html)
6. [Mitschabaude (2022). Montgomery/Barrett comparison notes, ZPrize 2022 documentation.](https://github.com/mitschabaude/montgomery/blob/main/doc/zprize22.md)
7. [BN_mod_mul_montgomery, OpenSSL Documentation.](https://docs.openssl.org/master/man3/BN_mod_mul_montgomery/)
8. [A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography, Chapter 14.](https://gulf.edu.sa/assets/lib/cs/handbook-of-applied-cryptography.pdf)
9. [Timing attacks and local timing attacks against Barrett's modular multiplication algorithm. Journal of Cryptographic Engineering (2020).](https://link.springer.com/article/10.1007/s13389-020-00254-3)
10. [Perin et al. (2011). Montgomery Modular Multiplication on Reconfigurable Hardware: Systolic versus Multiplexed Implementation. International Journal of Reconfigurable Computing.](https://onlinelibrary.wiley.com/doi/10.1155/2011/127147)
11. [Montgomery Reduction Scheme Functions, Intel Cryptography Primitives Library Developer Guide.](https://www.intel.com/content/www/us/en/docs/crypto-primitives-library/developer-guide-reference/2025-1/montgomery-reduction-scheme-functions.html)
12. [ARMv8/NEON Optimization of NCC-Sign for Mixed-Radix NTT. Electronics (MDPI), 2025.](https://www.mdpi.com/2079-9292/15/7/1456)
13. [Artemarius, cuda-zkp-ntt: GPU-accelerated NTT for ZK-proof generation.](https://github.com/Artemarius/cuda-zkp-ntt)
14. [A Constant-Time Hardware Architecture for the CSIDH Key-Exchange Protocol. arXiv:2508.11082.](https://arxiv.org/abs/2508.11082)
15. [Resource-aware Montgomery modular multiplication optimization for digital signal processing. ScienceDirect (2024).](https://www.sciencedirect.com/science/article/abs/pii/S1383762124000791)
16. [Module-Lattice-Based Digital Signature Standard, NIST FIPS 204.](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Computational and symbolic algebra › Symbolic and algebraic algorithms › Exact and arbitrary-precision arithmetic*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license