montgomery's modular multiplication algorithm

Posted in the Cryptography Forum

arkus

Mumbai, India

#1 Dec 8, 2008
hey m involved in one project tht uses this rsa encryption technique. i understood the basic methodology, but cant understand the montgomery's reduction technique they use to perform modular multiplication. It uses all that bit shifting or sth else which i cudn decipher. I wud be very greatful if someone could give a simple explanation with an example on how it works.
thnx
arkus

Mumbai, India

#2 Dec 8, 2008
somebody pls..
markh

Bayonne, NJ

#3 Dec 9, 2008
arkus, if you are are in a hurry, the most important thing to understand is that Montgomery multiplication is not necessary, in RSA. It makes RSA run faster, but everything will work fine without it.

If you want to understand Montgomery multiplication, I found two nice web pages:

http://www.nugae.com/encryption/fap4/montgome...

http://everything2.com/index.pl...

If you can find Montgomery's original paper, "Multiplication without trial division," it is a great piece of writing: very clear to understand.

But your post refers to "bit shifting" -- this is a basic technique of modular exponentiation, whether or not a Montgomery speed-up is used.

For an explanation of this basic modular exponentiation algorithm, see

http://en.wikipedia.org/wiki/Modular_exponent...

I highly recommend that you do your best, to understand the math used in these procedures.
esh

India

#4 Jan 19, 2009
can anyone suggest the site where i can get the complete verilog tutorials....
Cezane

Gwangju, Korea

#5 Nov 6, 2011
I am confused in the Montgomery modular multiplication and Montgomery reduction. Can anyone tell me what is the difference/relation between these two ?

Tell me when this thread is updated:

Subscribe Now Add to my Tracker

Add your comments below

Characters left: 4000

Please note by submitting this form you acknowledge that you have read the Terms of Service and the comment you are posting is in compliance with such terms. Be polite. Inappropriate posts may be removed by the moderator. Send us your feedback.

Cryptography Discussions

Title Updated Last By Comments
CYPHER : pehopouhir Dec 5 Vijai 2
What kind of code is this ? and how to decode it ? Dec 5 daydreaming 1
oaep Nov 30 Ron0805 1
Trusted third Party 's security and availabili... Nov 29 M Danyal 1
Cryptic images Nov '14 jonlin 1
Man Behind Secret Code at CIA Offers New Hint Nov '14 wichita-rick 2
Solve this? Nov '14 Chaos 1
More from around the web