Results 1 to 1 of 1

Math Help - Understanding Montgomery Multiplication

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    4

    Understanding Montgomery Multiplication

    Hi
    I am writing the code I explained at
    Puppy Linux Discussion Forum :: View topic - Checking overflow in C
    to implement Montgomery Multiplication for 1024 bit numbers. I am having a bit of a problem the theory behind it. I am attaching here the article I am referencing as a bitmap file. I understand what it is trying to say in equation 1, but how does it relate to the algorithm given at the bottom of the page? I can see that the loop from 0 t m-1 and the divide by 2 represent the multiplication by r^-1, but why add the M though (line 5 of algorithm). I know it has something to do with the division by M that should be performed (since we are working mod M) but I don't quite see the connection.
    Also, when I tried the following numerical:
    X=8 (01000b)
    Y=11 (01011b)
    M=17 (10001b)
    with n = 5 (obvious, depending on the number of bits in binary representation of M; please see the line just below equation 1),
    supplying the values of X, Y and M in equation 1 gives

    88/32 mod 17 = 2 mod 17 = 2

    However, taking their binary values and applying the given algorithm gives me the result 00111b (7 decimal)

    Where did I go wrong???
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiplication of 2xy^2. (-3x^2. y)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 1st 2011, 05:02 PM
  2. [SOLVED] Multiplication
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: February 26th 2011, 09:33 PM
  3. multiplication
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 23rd 2008, 04:50 AM
  4. sq rt multiplication
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 20th 2008, 09:38 AM
  5. Set Multiplication
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 6th 2006, 07:16 AM

Search Tags


/mathhelpforum @mathhelpforum