Montgomery modular multiplication
Many operations of interest modulo N can be expressed equally well in Montgomery form. Addition, subtraction, negation, comparison for equality, multiplication by an integer not in Montgomery form, and greatest common divisors with N may all be done with the standard algorithms. The can be calculated as 
as long as is stored.
When , most other arithmetic operations can be expressed in terms of REDC. This assumption implies that the product of two representatives mod N is less than RN, the exact hypothesis necessary for REDC to generate correct output. In particular, the product of and is . The combined operation of multiplication and REDC is often called Montgomery multiplication.
Conversion into Montgomery form is done by computing . Conversion out of Montgomery form is done by computing . The modular inverse of is . Modular exponentiation can be done using by initializing the initial product to the Montgomery representation of 1, that is, to , and by replacing the multiply and square steps by Montgomery multiplies.
Performing these operations requires knowing at least and . When R is a power of a small positive integer b, can be computed by : The inverse of N modulo b is computed by a naive algorithm (for instance, if then the inverse is 1), and Hensel’s lemma is used repeatedly to find the inverse modulo higher and higher powers of b, stopping when the inverse modulo R is known; is the negation of this inverse. The constants and can be generated as and as . The fundamental operation is to compute REDC of a product. When standalone REDC is needed, it can be computed as REDC of a product with . The only place where a direct reduction modulo N is necessary is in the precomputation of .
Contents
Montgomery arithmetic on multiprecision integers
Most cryptographic applications require numbers that are hundreds or even thousands of bits long. Such numbers are too large to be stored in a single machine word. Typically, the hardware performs multiplication mod some base B, so performing larger multiplications requires combining several small multiplications. The base B is typically 2 for microelectronic applications, 28 for 8-bit firmware, The algorithm may use as little as words of storage (plus a carry bit).
As an example, let , , and . Suppose that and . The Montgomery representations of a and b are and . Compute . The initial input T to MultiPrecisionREDC will be [6, 4, 8, 5, 6, 7]. The number N will be represented as [7, 9, 9]. The extended Euclidean algorithm says that , so N′ will be 7.
i ← 0 m ← j T c - ------- - 0 0485670 2 (After first iteration of first loop) 1 0485670 2 2 0485670 2 3 0487670 0 (After first iteration of second loop) 4 0487670 0 5 0487670 0 6 0487670 0 i ← 1 m ← j T c - ------- - 0 0087670 6 (After first iteration of first loop) 1 0067670 8 2 0067670 8 3 0067470 1 (After first iteration of second loop) 4 0067480 0 5 0067480 0 i ← 2 m ← j T c - ------- - 0 0007480 2 (After first iteration of first loop) 1 0007480 2 2 0007480 2 3 0007400 1 (After first iteration of second loop) 4 0007401 0
Therefore, before the final comparison and subtraction, . The final subtraction yields the number 50. Since the Montgomery representation of is , this is the expected result.
When working in base 2, determining the correct m at each stage is particularly easy: If the current working bit is even, then m is zero and if it’s odd, then m is one. Furthermore, because each step of MultiPrecisionREDC requires knowing only the lowest bit, Montgomery multiplication can be easily combined with a .
Side channel attacks
When using it as a part of a cryptographically secure algorithm, unmodified Montgomery reduction is vulnerable to , where the attacker can learn about the inner workings of the algorithm by studying the differences in time, power-consumption or any other parameter affected by the fact that the algorithm performs very different actions depending on the input. However it is simple to modify the algorithm or the hardware to make it resistant to such attacks.