[11041] in cryptography@c2.net mail archive
Re: Montgomery Multiplication
daemon@ATHENA.MIT.EDU (Nomen Nescio)
Thu Jul 4 12:22:38 2002
From: Nomen Nescio <nobody@dizum.com>
To: cryptography@wasabisystems.com
Date: Thu, 4 Jul 2002 17:50:33 +0200 (CEST)
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@wasabisystems.com
