• Sections
montgomery's modular multiplication a...

# 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
#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....

Judged:

1

1

Report Abuse Judge it!
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

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

Need help with Rail Fence cipher Oct 16 Zevvy 1
help please!! Oct 12 TheDarkOne13 2
Anonymous Document Authentication Sep 25 petewiedemann 1
Does anyone know what this is? Sep '17 Just_me 1
An unusual cipher for your enjoyment Aug '17 Andmunko 1
Generic Substitution Cipher Help (I think) Aug '17 Damein 1
Cube26A Cipher Aug '17 pvial00 1

#### Cryptography News

More Cryptography News from Topix »

More from around the web