Re: Montgomery Multiplication
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]
Montgomery Multiplication
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. Thanks for your help, Damien. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Montgomery Multiplication
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 [EMAIL PROTECTED]
Re: Montgomery Multiplication
I was just wondering if anyone knew where to get a good explanation of Montgomery multiplication for the non-mathematician? here's an explanation i wrote a couple of years ago: - don davis, boston what's going on with montgomery reduction: do you remember in your first digital-hardware class, how they taught you that you don't need AND, OR, and NOT gates, to build full-function logic circuits, because you can do everything with just NAND gates? montgomery's algorithm is kind of like that; it shows that you don't need the multiply, divide, and remainder operations to do bignum modular exponentiations, because you can use this montgomery-multiplication operation over-and-over, instead. the advantage of montgomery-mult'n is that it avoids the remaindering operation, and so avoids expensive divisions, but nevertheless manages to keep an exponentiation's intermediate products small, in a very cheap easy way. it works rather like logarithms, and the performance trade-offs are similar: to multiply two numbers, you have to transform them to the montgomery representation, montgomery-multiply the transformed numbers, then transform the product's montgomery-representation back to the normal representation. for two factors, this takes longer than a normal multiply-and-take-remainder step would, even though montgomery- multiplication is just as cheap as normal multiplication, because the final transformation takes longer than doing a remainder in the usual way. but, for exponentiation, where we would montgomery-multiply many times, we only have to do the representation-change twice, at the beginning and end. to do a modular exponentiation in the normal way, we'd have to take the remainder after every multiplication. so, that's how montgomery saves time: convert the operand to a representation in which the remaindering operation disappears, multiply that representation by itself as much as the exponent indicates, then change the repre- sentation back. this is like the advantage of logarithms: if you're multiplying many numbers together, then you convert all the operands once to their logs, and you convert the final result back, but you don't have to convert any of the intermediate results, so the cost of converting to from logarithm format is more than offset by the cheapness of adding instead of multiplying. now, how does montgomery representation make remaindering go away? the basic idea is that when we're doing a long chain of modular multiplications, we need to keep the intermediate products from getting too big, but taking their remainders mod N isn't the only way to keep them small. montgomery's conversion just multiplies each operand by the maximum operand-size, say 2^1024, modulo the crypto-system's modulus N. now, when we multiply two such trans- formed operands, the product gets bigger than we want to keep around, just as in normal modular arithmetic, but it's much easier to make the montgomery representation's excess go away at each step. the heart of montgomery's theorem is the trick of adding a certain simple multiple of the modulus N to this intermediate product, making a modulus-N equivalent that happens to be a multiple of 2^1024 . now, recall that this intermediate product is not a good montgomery representation; it's too big by just this factor of 2^1024. so, by throwing away the least-significant 1024 bits, we kill two birds with one stone: we keep the intermediate product's size manageable, and we keep the intermediate product in montgomery representation, so it's ready for another round of montgomery-multiplication. it's very slick, but none of the explanations i've read, treat this intermediate-size issue at all. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Montgomery Multiplication
-- On 2 Jul 2002 at 11:04, bear wrote: 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. Methods are available that are very close to being N log N (See Knuth) but I am not aware of anyone using them for practical purposes. The most common method for multiplying large integers has time N^1.6 Suppose we want to multiply two 2n bit numbers, to get a 4n bit product. We break them up into n bit numbers, so now we want to multiply (A * 2^n + B) * (U * 2^n + V) The long multiplication way of doing this would involve four multiplications of one n bit number by another n bit numbers. We could find the 2n+1 bit number A*U+B*V, special casing the carry bit, since it usually does not quite fit, and the two 2n bit numbers A*U and B*V We could then construct the 4n bit number A*U * 2^(2n) + (A*U+B*V) * 2^n + B*V However, to do this with three multiplications instead of four, we instead find the number x = (A+B) * (U+V) (A*U+B*V) = x - A*U - B*V One can perform analogous tricks for even greater savings by breaking it up into three instead of two, or four, or five, but after five it starts to get intolerably cumbersome. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG GKNOQNqkn5lYpFU6SPQseRS0yFwiX0ccDgB3zWAv 2xPio6LEvIRR+GZo5JDHl5ctEbbqxoyebosdh+9ba - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Montgomery Multiplication
Damien O'Rourke [EMAIL PROTECTED] writes: 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. I wrote a guide to the explanation in Handbook of Applied Cryptography which you can find here: http://www.ciphergoth.org/writing/postings/news-992.txt -- __ Paul Crowley \/ o\ [EMAIL PROTECTED] http://www.ciphergoth.org/ /\__/ BiCon 2002 UK bisexual gathering: http://www.2002.bicon.org.uk/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
