Timeline for Efficient setup for a Montgomery multiplication
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2015 at 10:42 | history | edited | CodesInChaos | CC BY-SA 3.0 |
edited tags; edited title
|
| Nov 23, 2012 at 16:25 | comment | added | President James K. Polk | @fgrieu: Thanks for the link, I hadn't seen that paper before. | |
| Nov 23, 2012 at 16:05 | comment | added | fgrieu♦ | @jug: I fully agree with both of your comments in this thread. In hardware, Montgomery has advantages, and is (thus) used in many hardware modexp. I was answering to GregS, and his "Actual experiments for most processors and implementations seem to show the Montgomery is a big win against the naive algorithm"; I'm more in agreement with the opinion on page 61 of Modern Computer Arithmetic 0.5.9. | |
| Nov 23, 2012 at 15:18 | comment | added | j.p. | @fgrieu: With "costly" I didn't mean time. Instead I meant space on the chip for the HW trying to guess the quotient. I agree with you that in theory Montgomery isn't a big win, but in practice one needs to know well how to divide efficiently (e.g., the long division algorithm in Knuth's Art of Computer Programming is not optimal: neither back addition nor the use of a simple division in necessary), and using faster multiplications like Karatsuba's in long division is not as easy as it is in Montgomery multiplication. | |
| Nov 23, 2012 at 15:15 | comment | added | fgrieu♦ | @GregS: I am not using asymptotics as in $O(b^2)$, but number of operations. Properly coded with either Montgomery or classical algorithms, $X⋅Y\bmod N$ with operands of $b$ words cost $o(2⋅b^2)$ multiply-and-add; the result can be reduced to $o(b)$ words as the computation progresses; and there are $o(b)$ determinations of a word of quotient. With Montgomery 1 such determination costs 1 multiplication, and never errs; with classical algorithms, it cost more (perhaps 8 times), and may err, but that does not change the $o(2⋅b^2)$ cost, for the (rare) "error" case can be turned into a speedup. | |
| Nov 23, 2012 at 13:53 | comment | added | President James K. Polk | @fgrieu: You are miscounting. Montgomery does not replace a single division by O(b**2) multiplies, it replaces all the divisions those multiplies. But asymptotic analysis miss the point because the asymptotics are the same for both algorithms. Montgomery trades a division for a multiplies, adds, and a right shift. Actual experiments for most processors and implementations seem to show the Montgomery is a big win against the naive algorithm. | |
| Nov 23, 2012 at 7:45 | comment | added | fgrieu♦ | @GregS: That's a fallacy. Montgomery replaces division by an operation that also has cost $o(b^2)$ multiplications of $w$-bit operands and addition of the result, where $b$ is the number of $w$-bit words in the modulus. | |
| Nov 22, 2012 at 21:37 | vote | accept | bob | ||
| Nov 22, 2012 at 17:24 | comment | added | President James K. Polk | @fgrieu: Montgomery avoids division entirely. | |
| Nov 14, 2012 at 14:32 | comment | added | bob | @mikeazo: I said you're correct and also +1'd your comment as it is indeed one way to solve the thing. But you know how it is in today's world: you spare every single bit that you can :D Also, the computation of $R^2 \mod N$ must be performed each time the modulus changes, so depending on the setting, this can happen often and might not be easily precomputed. | |
| Nov 14, 2012 at 14:05 | comment | added | mikeazo | Bob and Jug, I know the purpose of montgomery multiplication. My point was, you only compute $R^2$ once if I understand things right. Then you can use it for all future computations. | |
| Nov 14, 2012 at 13:10 | history | edited | bob | CC BY-SA 3.0 |
edited body
|
| Nov 14, 2012 at 13:00 | history | tweeted | twitter.com/#!/StackCrypto/status/268700106440732673 | ||
| Nov 14, 2012 at 9:39 | comment | added | fgrieu♦ | I challenge the widely stated opinion that Montgomery modular multiplication is significantly more efficient than regular modular multiplication: the number of elementary multiply-and-add for $b$-word numbers is $o(2⋅b^2)$ in both cases. The naive implementation of regular modular multiplication makes more memory accesses, but that can be fixed. Key advantages of Montgomery multiplication are elsewhere: quotient estimation never errs, so there is no necessity to recover from that, which may creates a side-channel leakage. | |
| Nov 14, 2012 at 9:08 | answer | added | j.p. | timeline score: 5 | |
| Nov 14, 2012 at 8:51 | comment | added | j.p. | @mikeazo: The idea of using Montgomery multiplication is also to avoid implementing long division (quite costly in HW, and not as easy as one might think in SW). | |
| Nov 14, 2012 at 8:10 | comment | added | bob | @mikeazo: This is one way to do it, of course. But it is not efficient as it requires a true multiplication mod $N$ whereas the purpose of Montgomery's multiplication was to be more efficient. Hence, although the cost for it gets lower with the number of Montgomery multiplications performed in this representation, one wants to reduce it if possible. | |
| Nov 14, 2012 at 8:09 | comment | added | bob | @B-Con: I'd say as much as Montgomery multiplication has: I'm not sure if there are many other settings where one wants to compute modular exponentiations with a modulus of 4096 bits :D | |
| Nov 14, 2012 at 8:06 | history | edited | bob | CC BY-SA 3.0 |
added 663 characters in body; edited title
|
| Nov 14, 2012 at 0:26 | comment | added | mikeazo | Can you not just do normal multiplication to compute the square of the constant? | |
| Nov 13, 2012 at 20:29 | comment | added | B-Con | Does this have anything specifically to do with cryptography? It might be better suited for Stack Overflow. | |
| Nov 13, 2012 at 15:35 | history | asked | bob | CC BY-SA 3.0 |