04-10-2010, 03:42 PM
.
[attachment=4969]
Montgomery Multiplication
Duncan A. Buell
abstract
Montgomery Multiplication Peter Montgomery has devised a way to speed up arithmetic in a context in which a single modulus is used for a long-running computation [Mon85]. This method has also been explored as a hardware operation [BD97, EW93]. The basic idea goes back to a standard trick that has been used for arithmetic modulo Mersenne numbers.
Let Mn = 2n
−1 be the n-th Mersenne number. Assume that we are doing
arithmetic modulo Mn. The crucial operation is multiplication: if A and B
are integers modulo Mn, that is to say, n-bit numbers, then the product
C = A · B can be written as C = C1 · 2n + C0; C1 and C0 are the digits of
the product C written with radix 2n.
The trick is to observe the following.
C = C1 · 2n + C0
= C1 · 2n
− C1 + C1 + C0
= C1 · (2n
− 1) + C1 + C0
= C1 ·Mn + C1 + C0
C1 + C0 (mod Mn)
So instead of having to divide by Mn in order to produce the remainder,
we only need to add the left half of a product to the right half of the product.
[attachment=4969]
Montgomery Multiplication
Duncan A. Buell
abstract
Montgomery Multiplication Peter Montgomery has devised a way to speed up arithmetic in a context in which a single modulus is used for a long-running computation [Mon85]. This method has also been explored as a hardware operation [BD97, EW93]. The basic idea goes back to a standard trick that has been used for arithmetic modulo Mersenne numbers.
Let Mn = 2n
−1 be the n-th Mersenne number. Assume that we are doing
arithmetic modulo Mn. The crucial operation is multiplication: if A and B
are integers modulo Mn, that is to say, n-bit numbers, then the product
C = A · B can be written as C = C1 · 2n + C0; C1 and C0 are the digits of
the product C written with radix 2n.
The trick is to observe the following.
C = C1 · 2n + C0
= C1 · 2n
− C1 + C1 + C0
= C1 · (2n
− 1) + C1 + C0
= C1 ·Mn + C1 + C0
C1 + C0 (mod Mn)
So instead of having to divide by Mn in order to produce the remainder,
we only need to add the left half of a product to the right half of the product.