Author 
Message 
mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Sun 10 Apr 2011, 08:41 Post subject:
Understanding Montgomery Multiplication 

Hi
I am writing the code I explained at
http://www.murgalinux.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 m1 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???

Description 

Download 
Filename 
MM.zip 
Filesize 
97.03 KB 
Downloaded 
307 Time(s) 

Back to top



LeithR
Joined: 24 Jan 2011 Posts: 190 Location: Kemnay, Aberdeenshire/Scotland

Posted: Mon 11 Apr 2011, 11:10 Post subject:


Hi There mahaju, I've read both this post and also the one you refer to below. I'm not sure that this is the right forum for you to get answers. What you are asking is a fairly academic issue.
I agree with what sc0ttman said to your other post. Try stackoverflow.com

Back to top



mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Mon 11 Apr 2011, 20:43 Post subject:


Hi
I have seen that forum but I think it's just too flashy and quite difficult to use
Also I don't think I'll get a convincing answer to my question there as wel
Do you know of any other active forum where I may discuss theoretical questions such as these?
Thanks

Back to top



muggins
Joined: 20 Jan 2006 Posts: 6717 Location: hobart

Posted: Mon 11 Apr 2011, 22:00 Post subject:


How about:
http://www.mathhelpforum.com/mathhelp/
http://www.mymathforum.com/

Back to top



mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Mon 11 Apr 2011, 22:40 Post subject:


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
Last edited by mahaju on Wed 13 Apr 2011, 00:21; edited 1 time in total

Back to top



efiguy
Joined: 06 Sep 2006 Posts: 169

Posted: Tue 12 Apr 2011, 01:48 Post subject:
Understanding Montgomery Multiplication Subject description: Mathcad Forums 

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

Back to top



Lobster
Official Crustacean
Joined: 04 May 2005 Posts: 15177 Location: Paradox Realm

Posted: Tue 12 Apr 2011, 03:19 Post subject:


If off topic, please post in that section
In the off topic section I have received advice on mice killing for Buddhists,
central heating maintenance and Quantum mechanics
_________________ Puppy WIKI

Back to top



mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Tue 12 Apr 2011, 03:26 Post subject:


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

Back to top



efiguy
Joined: 06 Sep 2006 Posts: 169

Posted: Tue 12 Apr 2011, 09:21 Post subject:
Understanding Montgomery Multiplication Subject description: explanation 

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 howto 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

Back to top



mahaju
Joined: 11 Oct 2010 Posts: 491 Location: between the keyboard and the chair

Posted: Tue 12 Apr 2011, 09:50 Post subject:


Hi
After a lot of poking around I finally found out the page for posting in the forum
but it seems their UI is quite difficult to use
still if I get my answer it will be worth it
I just hope the helpful people you mentioned will stumble upon my post
Thanks

Back to top



Lobster
Official Crustacean
Joined: 04 May 2005 Posts: 15177 Location: Paradox Realm

Posted: Tue 12 Apr 2011, 12:52 Post subject:


Quote:  This method is used in speeding up of cryptographic techniques 
Understood
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.
_________________ Puppy WIKI

Back to top



jamesbond
Joined: 26 Feb 2007 Posts: 2988 Location: The Blue Marble

Posted: Tue 12 Apr 2011, 21:03 Post subject:
Re: Understanding Montgomery Multiplication Subject description: explanation 

efiguy 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!!
 Try sagelive  our mathematical puplet here http://www.murgalinux.com/puppy/viewtopic.php?t=62231
_________________ Fatdog64, Slacko and Puppeee user. Puppy user since 2.13.
Contributed Fatdog64 packages thread.

Back to top



