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 [EMAIL PROTECTED]