Montgomery Multiplication

[Nomen Nescio]

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

> 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.

Bear replied:

> 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.

That's not Montgomery multiplication; that's what Knuth called modular
arithmetic, described in section 4.3.2 of Seminumerical Methods.

Montgomery multiplication is well described at
http://www.ciphergoth.org/writing/postings/news-992.txt, as Paul Crowley
posted.

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