Programming Praxis

[ Does anybody know the proper method for writing a-bar and b-bar in plain HTML? The LaTeX symbols are \={a} and \={b}, but WordPress renders LaTeX poorly, and I prefer plain HTML. FIXED! Thanks to Jussi, who suggests writing a amp hash x304 semicolon and b amp hash x304 semicolon. ]

Montgomery multiplication is a method of computing ab mod m for positive integers a, b and m, designed for situations where there are many multiplications to be performed mod m with a small number of multipliers; in particular, it is valuable for computing x^y mod m for large y. Montgomery multiplication was invented by Peter Montgomery in a 1985 article. Our exercise today will implement modular multiplication and exponentiation using Montgomery’s method.

The basic idea of Montgomery multiplication is to eliminate the division inherent in the modulo operation by translating the modulus m to a larger modulus r, with gcd(r, m) = 1, where r is a power of 2; thus, the division is rendered as a bit mask. Since r is a power of 2, the modulus m must be odd to satisfy the gcd requirement; we also require the two multipliers a and b be less than m. Then the Montgomery algorithm is as follows:

1. Find two integers r⁻¹ and m′ such that r r⁻¹ m m′ = 1 by the extended Euclidean algorithm. In particular, the algorithm used is a binary version of the algorithm that performs no divisions.
2. Translate the multipliers to “Montgomery space” by multiplying them by r (using left shifts) and reducing the product modulo m. Thus, ā = a r mod m and b̄ = b r mod m. These operations are expensive, but they are performed only once for each multiplier in a chain of multiplications.
3. Perform the Montgomery multiplication: calculate u = a b r mod m by the sequence of operations
   

   t = ā * b̄
   u = (t + (t * m′ mod r) * m) / r
   if (u ≥ m) then subtract m from u

   The only division is a right-shift; the final result uses subtraction instead of division because it is known that the product is less than 2m.

4. Translate the result back from Montgomery space to an ordinary integer by ab = u r⁻¹ mod m.

Montgomery exponentiation is similar. To compute x^y mod m, select r, compute r⁻¹ and m′, translate x to Montgomery space, use the square-and-multiply method with Montgomery multiplications to perform the exponentiation starting from 1 in Montgomery space, then translate the result back from Montgomery space. This is much faster than the calculation without Montgomery multiplication, because the cost of initializing the Montgomery space is amortized over several multiplications, each of which avoids the inherent division of the modulo operator.

Your task is to write functions that perform Montgomery multiplication and exponentiation. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2