Montgomery Multiplication
Thread Rating:
  • 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


.pdf   montgomery.pdf (Size: 46.72 KB / Downloads: 42)
Montgomery Multiplication

Duncan A. Buell

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.

Important Note..!

If you are not satisfied with above reply ,..Please


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 page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  MATRIX MULTIPLICATION ABSTRACT project girl 0 284 22-11-2012, 12:36 PM
Last Post: project girl
  Spatial Information Technology Center at Fulton-Montgomery Community College seminar flower 0 312 27-10-2012, 01:30 PM
Last Post: seminar flower
  A Karatsuba-based Montgomery Multiplier smart paper boy 0 775 28-07-2011, 04:12 PM
Last Post: smart paper boy
  Implementation of Strassen's Algorithm for Matrix Multiplication seminar class 0 2,672 02-05-2011, 04:42 PM
Last Post: seminar class