Montgomery Multiplication
project report helper Active In SP Posts: 2,270 Joined: Sep 2010 
04102010, 03:42 PM
. montgomery.pdf (Size: 46.72 KB / Downloads: 41) 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 longrunning 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 nth 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, nbit 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. 



Important Note..!
If you are not satisfied with above reply ,..PleaseASK HERE
So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this pagePossibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
MATRIX MULTIPLICATION ABSTRACT  project girl  0  280 
22112012, 12:36 PM Last Post: project girl 

Spatial Information Technology Center at FultonMontgomery Community College  seminar flower  0  302 
27102012, 01:30 PM Last Post: seminar flower 

A Karatsubabased Montgomery Multiplier  smart paper boy  0  768 
28072011, 04:12 PM Last Post: smart paper boy 

Implementation of Strassen's Algorithm for Matrix Multiplication  seminar class  0  2,670 
02052011, 04:42 PM Last Post: seminar class 