Puppy Linux Discussion Forum

mahaju

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

LeithR · Joined: 24 Jan 2011 Posts: 74 Location: Aberdeen/Scotland

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

mahaju · 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

muggins · Joined: 20 Jan 2006 Posts: 6660 Location: lisbon

How about:

http://www.mathhelpforum.com/math-help/
http://www.mymathforum.com/

mahaju · 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

efiguy · Joined: 06 Sep 2006 Posts: 169

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

Lobster · 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 Laughing

mahaju · 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

efiguy · Joined: 06 Sep 2006 Posts: 169

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

mahaju · 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
Smile

Thanks

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

jamesbond · Joined: 26 Feb 2007 Posts: 1540 Location: The Blue Marble