Questions tagged [montgomery-multiplication]

A modular multiplication algorithm invented by Peter Montgomery that allows modular arithmetic to be performed efficiently when the modulus is large (typically several hundred bits).

Filter by
Sorted by
Tagged with
7 votes
1 answer
2k views

How does Montgomery reduction work?

I want to reduce a multi-precision integer $x$ modulo a prime $p$, very fast. Performing the traditional Euclidean division for only calculating the modulo, is inefficient and modular reduction is at ...
Aravind A's user avatar
  • 1,020
8 votes
2 answers
2k views

RSA Timing Attack on "Extra" Montgomery Reduction

In "A practical implementation of the timing attack", the authors take advantage of a timing difference that stems from "extra reductions" that occur when multiplying numbers in the Montgomery form. ...
kkl's user avatar
  • 383
1 vote
1 answer
595 views

Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation

I'm confused about how one might supposedly bypass the final subtraction of the modulus in radix-2 montgomery modular multiplication, when used in a modular exponentiation algorithm. The following two ...
asmvolatile's user avatar
3 votes
0 answers
244 views

Montgomery modular multiplication – confusion with subtraction of modulus

I'm reading the paper “COMPARISON OF SCALABLE MONTGOMERY MODULAR MULTIPLICATION IMPLEMENTATIONS EMBEDDED IN RECONFIGURABLE HARDWARE” (PDF) on hardware algorithms for montgomery multiplication for ...
asmvolatile's user avatar
2 votes
1 answer
908 views

Concrete example of Montgomery Multiplication

I have read about Montgomery Multiplication on several sites, but I haven't found any examples on specific numbers that explain the algorithm to someone who doesn't have a PhD in number theory. I know ...
Kevin Stefanov's user avatar
2 votes
1 answer
1k views

Montgomery Exponentiation - selecting input value R for a given BigInteger

I have Montgomery exponentiation working, but it's working quite slow. I suspect there are two reasons for this - I implemented it bit size instead of word size (I didn't realize at the time that ...
Saf's user avatar
  • 205