Montgomery Multiplication
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 project report helper Active In SP Posts: 2,270 Joined: Sep 2010 04-10-2010, 03:42 PM .   montgomery.pdf (Size: 46.72 KB / Downloads: 42) 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.