Programming Praxis

Home | Pages | Archives

Montgomery Multiplication

July 29, 2014 9:00 AM

[ 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 xy 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−1 and m′ such that r r−1 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−1 mod m.

Montgomery exponentiation is similar. To compute xy mod m, select r, compute r−1 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.

Share this:

Posted by programmingpraxis

Categories: Exercises

Tags:

2 Responses to “Montgomery Multiplication”

  1. Re bar: One theory seems to be to put a code called a combining
    diacritic in Unicode after the character. A bar above would be
    ̄. The following characters looked somewhat usable
    locally in w3m and firefox: ā, b̄, c̄,
    d̄, ē.

    (The above text is copied and pasted from my local test document source code. In the comment editor, at the moment of this writing, I see the hex codes as HTML character entities or whatever they are called.)

    By Jussi Piitulainen on July 29, 2014 at 2:17 PM

  2. Hm. The code entity above should have been ampersand hash x 0304 semicolon. The software interpreted it as the actual code. The sample characters look to me as they should.

    By Jussi Piitulainen on July 29, 2014 at 2:24 PM

Leave a Reply

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.