Montgomery Multiplication

[jamesd at echeque.com]

    --
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 majordomo at wasabisystems.com