Understanding Montgomery Multiplication
Understanding Montgomery Multiplication
Hi
I am writing the code I explained at
http://www.murga-linux.com/puppy/viewtopic.php?t=66710
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???
I am writing the code I explained at
http://www.murga-linux.com/puppy/viewtopic.php?t=66710
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???
- Attachments
-
- MM.zip
- (97.03 KiB) Downloaded 381 times
Thank you everyone
By the way, even though this question is not related to Puppy I think this forum is one of the best places to post it, as the members have given me suggestions to where I can find my answer
In other forums I would just have got things like "go search in Google" or something
By the way, even though this question is not related to Puppy I think this forum is one of the best places to post it, as the members have given me suggestions to where I can find my answer
In other forums I would just have got things like "go search in Google" or something
Last edited by mahaju on Wed 13 Apr 2011, 04:21, edited 1 time in total.
Understanding Montgomery Multiplication
mahaju,
- That is a real nice compliment to Puppians
- Wow, You've really picked up some excellent technical details here -
but I would still recomend the PTC forum, When you do get it figured out, and we just know you will, please return and update your posts, meanwhile, Try some Puppy's too. I'm pretty sure there is a "math Puppy", somebody will have to help me out here <:)
-
reference only.
http://collab.mathsoft.com/~mathcad2000
-
The new forum and blog - Join and search out these gentlemen - Also - Mona - if she is still present there.
-
http://communities.ptc.com/community/mathcad
-
=== Mathcad Forum Professional Experts ===
-
VFO - Russian Mathmatics Professor
VFO ochkovChangeToAtSigntwt.mpei.ac.ru
-
stuartafbruff - Math / Physics expert any topic
stuartafbruff stuartbruffChangeToAtSigngmail.com
-
jmG - Math / Physics expert any topic
jmG jmgiraudChangeToAtSigninfoteck.dr.qc.ca
-
Tom - Math / Physics expert any topic
Tom_Gutman tom_gutmanChangeToAtSignearthlink.net
-
http://collab.mathsoft.com/~Mathcad2000/guests
*** Search term Karatsuba ***
Topic: PARALLEL COMPUTE (5 of 13), Read 95 times
Conf: Mathcad Usage Chat
From: sgrode steen_______grode.dk
Date: Friday, July 11, 2008 04:08 PM
=== BE SURE TO LOOK AT THE LAST ENTRY ===
-
-
*** Message search results for exponentiation
Found 24 Messages.
Conference Topic Date
1 Feature Suggestions signed numbers and parenthesis 8/13/2009
2 Calculus & DEs Unusual curve 4/15/2009
3 Feature Suggestions Significant Digits 8/22/2008
4 Feature Suggestions Numerical format 5/31/2008
5 Mathcad Usage Chat Graph Correct Relation Wrong? 11/1/2007
6 Programming in Mathcad Error. These values cannot be compared? 7/24/2007
7 Mathcad Usage Chat symbolic commands 7/11/2007
8 Mathcad Usage Chat symbolic commands 7/11/2007
9 Mathcad Usage Chat Double Indefinite Integral 9/2/2006
10 Mathcad Usage Chat IEEE Standards 11/1/2005
11 Mathcad Usage Chat IEEE Standards 10/28/2005
12 Mathcad Usage Chat The argument for units 3/3/2005
13 Mathcad Usage Chat Integration novice 7/8/2004
14 Mathcad Usage Chat Reading Data Files 6/16/2004
15 Electrical Engineering Integration 5/13/2004
16 Probability & Statistics Taking Square Root of Matrix 4/7/2004
17 Algebra & Geometry Exp(Matrix) 2/4/2004
18 Mathcad Usage Chat BUG or mystic 12/23/2003
19 Mathcad Usage Chat Why do my units have decimal exponents? 8/26/2003
20 Feature Suggestions Units again! 8/18/2003
21 Feature Suggestions Units again! 8/18/2003
22 Algebra & Geometry (Complex value)^ (complex value) 3/18/2003
23 Algebra & Geometry A REAL WRONG ANSWER 4/18/2002
24 Mathcad Usage Chat Large Argument Airy Function Plot 2/15/2002
Enjoy,
jay
- That is a real nice compliment to Puppians
- Wow, You've really picked up some excellent technical details here -
but I would still recomend the PTC forum, When you do get it figured out, and we just know you will, please return and update your posts, meanwhile, Try some Puppy's too. I'm pretty sure there is a "math Puppy", somebody will have to help me out here <:)
-
reference only.
http://collab.mathsoft.com/~mathcad2000
-
The new forum and blog - Join and search out these gentlemen - Also - Mona - if she is still present there.
-
http://communities.ptc.com/community/mathcad
-
=== Mathcad Forum Professional Experts ===
-
VFO - Russian Mathmatics Professor
VFO ochkovChangeToAtSigntwt.mpei.ac.ru
-
stuartafbruff - Math / Physics expert any topic
stuartafbruff stuartbruffChangeToAtSigngmail.com
-
jmG - Math / Physics expert any topic
jmG jmgiraudChangeToAtSigninfoteck.dr.qc.ca
-
Tom - Math / Physics expert any topic
Tom_Gutman tom_gutmanChangeToAtSignearthlink.net
-
http://collab.mathsoft.com/~Mathcad2000/guests
*** Search term Karatsuba ***
Topic: PARALLEL COMPUTE (5 of 13), Read 95 times
Conf: Mathcad Usage Chat
From: sgrode steen_______grode.dk
Date: Friday, July 11, 2008 04:08 PM
=== BE SURE TO LOOK AT THE LAST ENTRY ===
-
-
*** Message search results for exponentiation
Found 24 Messages.
Conference Topic Date
1 Feature Suggestions signed numbers and parenthesis 8/13/2009
2 Calculus & DEs Unusual curve 4/15/2009
3 Feature Suggestions Significant Digits 8/22/2008
4 Feature Suggestions Numerical format 5/31/2008
5 Mathcad Usage Chat Graph Correct Relation Wrong? 11/1/2007
6 Programming in Mathcad Error. These values cannot be compared? 7/24/2007
7 Mathcad Usage Chat symbolic commands 7/11/2007
8 Mathcad Usage Chat symbolic commands 7/11/2007
9 Mathcad Usage Chat Double Indefinite Integral 9/2/2006
10 Mathcad Usage Chat IEEE Standards 11/1/2005
11 Mathcad Usage Chat IEEE Standards 10/28/2005
12 Mathcad Usage Chat The argument for units 3/3/2005
13 Mathcad Usage Chat Integration novice 7/8/2004
14 Mathcad Usage Chat Reading Data Files 6/16/2004
15 Electrical Engineering Integration 5/13/2004
16 Probability & Statistics Taking Square Root of Matrix 4/7/2004
17 Algebra & Geometry Exp(Matrix) 2/4/2004
18 Mathcad Usage Chat BUG or mystic 12/23/2003
19 Mathcad Usage Chat Why do my units have decimal exponents? 8/26/2003
20 Feature Suggestions Units again! 8/18/2003
21 Feature Suggestions Units again! 8/18/2003
22 Algebra & Geometry (Complex value)^ (complex value) 3/18/2003
23 Algebra & Geometry A REAL WRONG ANSWER 4/18/2002
24 Mathcad Usage Chat Large Argument Airy Function Plot 2/15/2002
Enjoy,
jay
Hello
Thank you all for your replies
I think my problem is that by choosing M=17 with n = 5, I can't just assume X and Y to be any numbers such as 8 and 11 (X and Y should have certain specific properties), but I'm still looking into it
@efiguy: I think that website is about mathcad software, but I have never used it
and what are all those email id's that you sent me? Are they the active users in that forum? I didn'e see how I can start a thread in that forum
@Lobster: This method is used in speeding up of cryptographic techniques such as RSA so I posted it in security section
But it's true that my question doesn't have anything to do with using Puppy
Thank you all for your replies
I think my problem is that by choosing M=17 with n = 5, I can't just assume X and Y to be any numbers such as 8 and 11 (X and Y should have certain specific properties), but I'm still looking into it
@efiguy: I think that website is about mathcad software, but I have never used it
and what are all those email id's that you sent me? Are they the active users in that forum? I didn'e see how I can start a thread in that forum
@Lobster: This method is used in speeding up of cryptographic techniques such as RSA so I posted it in security section
But it's true that my question doesn't have anything to do with using Puppy
Understanding Montgomery Multiplication
Hi mahaju,
- Yes I knew you did not have Mathcad, It is expensive, but your textual posts expressed the details very well - and that is what is important, just explain you do not have the program and do need some math help, paste the text from this forum to their forum, I guarantee they will help!!
- This group is a math forum first, then a how-to implement into the programs syntax.
- Do not be fearful, these are wonderful bright people that work with high school students and Cern physics designers as well. They will welcome you as one of their own.
- Your questions deserve a good answer, the active people following the PTC forum will recognise your talent and can provide that for you.
- The names I listed are for you to recognise as a "newbie" to their forum, they are some of the forums most helpful personages and that another member recommended you to them. PTC forum has an excellent search engine and that is your best way to start, lots of equations are posted as a gif image like in the "PARALLEL COMPUTE" topic.
-- Please Moderators, you have a gifted individual doing these posts, if you must move them - please keep together and offer him a PM message as to where they have moved
Thanks,
Jay
- Yes I knew you did not have Mathcad, It is expensive, but your textual posts expressed the details very well - and that is what is important, just explain you do not have the program and do need some math help, paste the text from this forum to their forum, I guarantee they will help!!
- This group is a math forum first, then a how-to implement into the programs syntax.
- Do not be fearful, these are wonderful bright people that work with high school students and Cern physics designers as well. They will welcome you as one of their own.
- Your questions deserve a good answer, the active people following the PTC forum will recognise your talent and can provide that for you.
- The names I listed are for you to recognise as a "newbie" to their forum, they are some of the forums most helpful personages and that another member recommended you to them. PTC forum has an excellent search engine and that is your best way to start, lots of equations are posted as a gif image like in the "PARALLEL COMPUTE" topic.
-- Please Moderators, you have a gifted individual doing these posts, if you must move them - please keep together and offer him a PM message as to where they have moved
Thanks,
Jay
- Lobster
- Official Crustacean
- Posts: 15522
- Joined: Wed 04 May 2005, 06:06
- Location: Paradox Realm
- Contact:
UnderstoodThis method is used in speeding up of cryptographic techniques
Sometimes it is difficult to select the right section.
Theoretically these cryptographic techniques can be beaten with quantum computing? How far ahead of existing technology would you say the intelligence services are? Ten or twenty years?
Back to pigeon post . . . better let you go back to your maths discussion.
Re: Understanding Montgomery Multiplication
Try sagelive - our mathematical puplet here http://www.murga-linux.com/puppy/viewtopic.php?t=62231efiguy wrote:Hi mahaju,
- Yes I knew you did not have Mathcad, It is expensive, but your textual posts expressed the details very well - and that is what is important, just explain you do not have the program and do need some math help, paste the text from this forum to their forum, I guarantee they will help!!
Fatdog64 forum links: [url=http://murga-linux.com/puppy/viewtopic.php?t=117546]Latest version[/url] | [url=https://cutt.ly/ke8sn5H]Contributed packages[/url] | [url=https://cutt.ly/se8scrb]ISO builder[/url]