Montgomery Multiplication

[bear]

On Tue, 2 Jul 2002, Damien O'Rourke wrote:

>Hi,
>
>I was just wondering if anyone knew where to get a good explanation of
>Montgomery multiplication
>for the non-mathematician?  I have a fair bit of maths but not what is
>needed to understand his paper.

It's kind of an exotic technique, but it's one I happen to know...

Montgomery Multiplication is explained for the computer scientist
in Knuth, _Seminumerical Methods_.

Briefly: The chinese remainder theorem proves that for any set
A1...AN of integers with no common divisors, any integer X which is
less than their product can be represented as a series of remainders
X1...XN, where Xn is equal to X modulo An.

if you're using the same set of integers with no common divisors
A1...AN to represent two integers X and Y, you have a pair of series
of remainders X1...XN and Y1...YN.

Montgomery proved that Z, the product of X and Y, if it's in the
representable range, is Z1...ZN where Zn equals (Xn * Yn) mod An.

This means that, for integers A1..AN that are selected to be small
enough for your computer to multiply in a single instruction, you
can do multiplication of extended-precision integers less than their
product in linear time relative to the size of the set of integers
A; just multiply each pair of remainder terms modulo the modulus
for that term, and the result is the product.  As a technique,
it's a useful method when you know ahead of time what approximate
size your bigints are.

With positionally-notated integers, You need time N squared, or
at least N log N (I seem to remember that there was an N log N
technique, but I don't remember what it was and may be mistaken),
relative to the length of the integers themselve.

There are a few optimizations available so you can select a set A
that's just big enough to do the job, but they require some degree
of foreknowledge of the job that you often don't have when writing
libraries.

The major problem with Montgomery representation of integers is
that it makes division hard. If you can arrange your problem so
you don't need division, and you know the approximate size of
the bignums you'll be working with, it can speed things up
noticeably.

				Bear



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com