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
#1
04-10-2010, 03:42 PM


.

.pdf   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 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.
Reply

Important Note..!

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

ASK 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 page

Quick Reply
Message
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 280 22-11-2012, 12:36 PM
Last Post: project girl
  Spatial Information Technology Center at Fulton-Montgomery Community College seminar flower 0 302 27-10-2012, 01:30 PM
Last Post: seminar flower
  A Karatsuba-based Montgomery Multiplier smart paper boy 0 768 28-07-2011, 04:12 PM
Last Post: smart paper boy
  Implementation of Strassen's Algorithm for Matrix Multiplication seminar class 0 2,670 02-05-2011, 04:42 PM
Last Post: seminar class