Montgomery modular multiplication

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery.
Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of and to efficiently compute the Montgomery form of. The efficiency comes from avoiding expensive division operations. Classical modular multiplication reduces the double-width product using division by and keeping only the remainder. This division requires quotient digit estimation and correction. The Montgomery form, in contrast, depends on a constant which is coprime to, and the only division necessary in Montgomery multiplication is division by. The constant can be chosen so that division by is easy, significantly improving the speed of the algorithm. In binary computers, is always a power of two, since division by powers of two can be implemented by bit shifting.
The need to convert and into Montgomery form and their product out of Montgomery form means that computing a single product by Montgomery multiplication is slower than the conventional or Barrett reduction algorithms. However, when performing many multiplications in a row, as in modular exponentiation, intermediate results can be left in Montgomery form. Then the initial and final conversions become a negligible fraction of the overall computation. Many important cryptosystems such as RSA and Diffie–Hellman key exchange are based on arithmetic operations modulo a large odd number, and for these cryptosystems, computations using Montgomery multiplication with a power of two are faster than the available alternatives.

Modular arithmetic

Let denote a positive integer modulus. The quotient ring consists of residue classes modulo, that is, its elements are sets of the form
where ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by . The residue class corresponding to is denoted. Equality of residue classes is called congruence and is denoted
Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers for which. If is an integer, then the representative of is written. When writing congruences, it is common to identify an integer with the residue class it represents. With this convention, the above equality is written.
Arithmetic on residue classes is done by first performing integer arithmetic on their representatives. The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative. For example, if, then the sum of the residue classes and is computed by finding the integer sum, then determining, the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so.

Montgomery form

If and are integers in the range, then their sum is in the range and their difference is in the range, so determining the representative in requires at most one subtraction or addition of. However, the product is in the range. Storing the intermediate integer product requires twice as many bits as either or, and efficiently determining the representative in requires division. Mathematically, the integer between 0 and that is congruent to can be expressed by applying the Euclidean division theorem:
where is the quotient and, the remainder, is in the interval. The remainder is. Determining can be done by computing, then subtracting from. For example, again with, the product is determined by computing, dividing, and subtracting.
Because the computation of requires division, it is undesirably expensive on most computer hardware. Montgomery form is a different way of expressing the elements of the ring in which modular products can be computed without expensive divisions. While divisions are still necessary, they can be done with respect to a different divisor. This divisor can be chosen to be a power of two, for which division can be replaced by shifting, or a whole number of machine words, for which division can be replaced by omitting words. These divisions are fast, so most of the cost of computing modular products using Montgomery form is the cost of computing ordinary products.
The auxiliary modulus must be a positive integer such that. For computational purposes it is also necessary that division and reduction modulo are inexpensive, and the modulus is not useful for modular multiplication unless. The Montgomery form of the residue class with respect to is, that is, it is the representative of the residue class. For example, suppose that and that. The Montgomery forms of 3, 5, 7, and 15 are,,, and.
Addition and subtraction in Montgomery form are the same as ordinary modular addition and subtraction because of the distributive law:
Note that doing the operation in Montgomery form does not lose information compared to doing it in the quotient ring. This is a consequence of the fact that, because, multiplication by is an isomorphism on the additive group. For example,, which in Montgomery form becomes.
Multiplication in Montgomery form, however, is seemingly more complicated. The usual product of and does not represent the product of and because it has an extra factor of :
Computing products in Montgomery form requires removing the extra factor of. While division by is cheap, the intermediate product is not divisible by because the modulo operation has destroyed that property. So for instance, the product of the Montgomery forms of 7 and 15 modulo 17, with, is the product of 3 and 4, which is 12. Since 12 is not divisible by 100, additional effort is required to remove the extra factor of.
Removing the extra factor of can be done by multiplying by an integer such that, that is, by an whose residue class is the modular inverse of mod. Then, working modulo,
The integer exists because of the assumption that and are coprime. It can be constructed using the extended Euclidean algorithm. The extended Euclidean algorithm efficiently determines integers and that satisfy Bézout's identity:
,, and:
This shows that it is possible to do multiplication in Montgomery form. A straightforward algorithm to multiply numbers in Montgomery form is therefore to multiply,, and as integers and reduce modulo.
For example, to multiply 7 and 15 modulo 17 in Montgomery form, again with, compute the product of 3 and 4 to get 12 as above. The extended Euclidean algorithm implies that, so. Multiply 12 by 8 to get 96 and reduce modulo 17 to get 11. This is the Montgomery form of 3, as expected.

The REDC algorithm

While the above algorithm is correct, it is slower than multiplication in the standard representation because of the need to multiply by and divide by. Montgomery reduction, also known as REDC, is an algorithm that simultaneously computes the product by and reduces modulo more quickly than the naïve method. Unlike conventional modular reduction, which focuses on making the number smaller than, Montgomery reduction focuses on making the number more divisible by. It does this by adding a small multiple of which is sophisticatedly chosen to cancel the residue modulo. Dividing the result by yields a much smaller number. This number is so much smaller that it is nearly the reduction modulo, and computing the reduction modulo requires only a final conditional subtraction. Because all computations are done using only reduction and divisions with respect to, not, the algorithm runs faster than a straightforward modular reduction by division.
function REDC is
input: Integers R and N with,
Integer N′ in such that,
Integer T in the range.
output: Integer S in the range such that
m ← mod R
t ← / R
if t ≥ N then
return
else
return t
end if
end function
To see that this algorithm is correct, first observe that is chosen precisely so that is divisible by. A number is divisible by if and only if it is congruent to zero mod, and we have:
Therefore, is an integer. Second, the output is either or, both of which are congruent to, so to prove that the output is congruent to, it suffices to prove that is, satisfies:
Therefore, the output has the correct residue class. Third, is in, and therefore is between 0 and. Hence is less than, and because it's an integer, this puts in the range. Therefore, reducing into the desired range requires at most a single subtraction, so the algorithm's output lies in the correct range.
To use REDC to compute the product of 7 and 15 modulo 17, first convert to Montgomery form and multiply as integers to get 12 as above. Then apply REDC with,,, and. The first step sets to. The second step sets to. Notice that is 1100, a multiple of 100 as expected. is set to 11, which is less than 17, so the final result is 11, which agrees with the computation of the previous section.
As another example, consider the product but with. Using the extended Euclidean algorithm, compute, so will be. The Montgomery forms of 7 and 15 are and, respectively. Their product 28 is the input to REDC, and since, the assumptions of REDC are satisfied. To run REDC, set to. Then, so. Because, this is the Montgomery form of.

Interpretation via the Chinese Remainder Theorem

Source:
Given the modulus and the Montgomery radix used in a Montgomery reduction, consider the residue ring
an isomorphism that follows from the Chinese Remainder Theorem.