Puppy Linux Discussion Forum Forum Index Puppy Linux Discussion Forum
Puppy HOME page : puppylinux.com
"THE" alternative forum : puppylinux.info
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

The time now is Wed 26 Nov 2014, 07:34
All times are UTC - 4
 Forum index » Off-Topic Area » Security
Understanding Montgomery Multiplication
Post_new_topic   Reply_to_topic View_previous_topic :: View_next_topic
Page 1 of 1 Posts_count  
Author Message
mahaju


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

PostPosted: Sun 10 Apr 2011, 08:41    Post_subject:  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???
Confused
MM.zip
Description 
zip

 Download 
Filename  MM.zip 
Filesize  97.03 KB 
Downloaded  252 Time(s) 
Back to top
View user's profile Send_private_message 
LeithR

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

PostPosted: 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
View user's profile Send_private_message 
mahaju


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

PostPosted: 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
View user's profile Send_private_message 
muggins

Joined: 20 Jan 2006
Posts: 6690
Location: lisbon

PostPosted: Mon 11 Apr 2011, 22:00    Post_subject:  

How about:

http://www.mathhelpforum.com/math-help/
http://www.mymathforum.com/
Back to top
View user's profile Send_private_message 
mahaju


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

PostPosted: 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

Edited_time_total
Back to top
View user's profile Send_private_message 
efiguy


Joined: 06 Sep 2006
Posts: 169

PostPosted: Tue 12 Apr 2011, 01:48    Post_subject: Understanding Montgomery Multiplication
Sub_title: 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
View user's profile Send_private_message 
Lobster
Official Crustacean


Joined: 04 May 2005
Posts: 15117
Location: Paradox Realm

PostPosted: 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 Laughing

_________________
Puppy WIKI
Back to top
View user's profile Send_private_message Visit_website 
mahaju


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

PostPosted: 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
View user's profile Send_private_message 
efiguy


Joined: 06 Sep 2006
Posts: 169

PostPosted: Tue 12 Apr 2011, 09:21    Post_subject: Understanding Montgomery Multiplication
Sub_title: 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 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
Back to top
View user's profile Send_private_message 
mahaju


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

PostPosted: 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
Smile

Thanks
Back to top
View user's profile Send_private_message 
Lobster
Official Crustacean


Joined: 04 May 2005
Posts: 15117
Location: Paradox Realm

PostPosted: Tue 12 Apr 2011, 12:52    Post_subject:  

Quote:
This method is used in speeding up of cryptographic techniques


Understood Cool
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. Smile

_________________
Puppy WIKI
Back to top
View user's profile Send_private_message Visit_website 
jamesbond

Joined: 26 Feb 2007
Posts: 2230
Location: The Blue Marble

PostPosted: Tue 12 Apr 2011, 21:03    Post_subject: Re: Understanding Montgomery Multiplication
Sub_title: 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.murga-linux.com/puppy/viewtopic.php?t=62231
_________________
Fatdog64, Slacko and Puppeee user. Puppy user since 2.13.
Contributed Fatdog64 packages thread
Back to top
View user's profile Send_private_message 
Display_posts:   Sort by:   
Page 1 of 1 Posts_count  
Post_new_topic   Reply_to_topic View_previous_topic :: View_next_topic
 Forum index » Off-Topic Area » Security
Jump to:  

Rules_post_cannot
Rules_reply_cannot
Rules_edit_cannot
Rules_delete_cannot
Rules_vote_cannot
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0788s ][ Queries: 12 (0.0071s) ][ GZIP on ]