Timeline for Concrete example of Montgomery Multiplication
Current License: CC BY-SA 4.0
44 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 10 at 15:39 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Fix stated number of limbs for T before loop on j
|
| Mar 5 at 5:04 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Add missing step
|
| Feb 22 at 12:05 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
p changed to N
|
| Jan 21 at 18:50 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Fix
|
| Jul 26, 2023 at 6:27 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Practical method to compute a Montgomery representative
|
| Jul 26, 2023 at 6:21 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Practical method to compute a Montgomery representative
|
| S Jul 24, 2023 at 17:14 | history | mod moved comments to chat | |||
| S Jul 24, 2023 at 17:14 | comment | added | fgrieu♦ | This discussion continues in this chat then this one, including programming details like how to implement $T\gets t_2\cdot\beta+t_1+q\cdot n_j+y_i\cdot x_j+r_j$ with x64 intrinsics. | |
| Jul 24, 2023 at 17:12 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Fix and improve "Conversion back to regular PNS"
|
| Jul 24, 2023 at 16:42 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Fix Z->R
|
| Jul 24, 2023 at 13:49 | comment | added | fgrieu♦ | @KevinStefanov: Montgomery arithmetic does not by itself gives a large speedup. A factor of 3 would be surprising even if we include the benefit of interleaving. The essential thing for 3000-bit numbers is using wide limbs so that $\ell=\lceil3000/\log_2(\beta)\rceil$ is as low as possible, AND an algorithm doing in the order of $2\ell^2$ limb multiplications per 3000×3000 multiplication and modular reduction, or something subquadratic like Karatsuba (but the later is much more complex and seldom attempted at first). | |
| Jul 24, 2023 at 13:29 | comment | added | Kevin Stefanov | So given this do you think it's worth it to implement Montgomery Multiplication to do those 3000 modular MUL operations with, instead of normal reduction after each MUL? If i want to make them run faster? | |
| Jul 24, 2023 at 13:27 | comment | added | Kevin Stefanov | N is a 3000-bit number, that's why after each MUL's 6000-bit result when we divide by N and get the remainder, we get back to a 3000-bit number, to be multiplied by the next 3000-bit number in the chain of several thousand sequential modular multiplications mod N (each number in the chain is 3000-bits). Then get another 6000-bit MUL result, divide by N and take remainder, which gets us back to a 3000-bit number, and so on and so forth. This way I perform about 3000 modular multiplications on 3000-bit numbers. | |
| Jul 24, 2023 at 13:12 | comment | added | Kevin Stefanov | Currently I've implemented 3000 sequential modular multiplications of 3000-bit numbers mod N as simply: compute one MUL, get a 6000-bit result, divide it by N and get the remainder, which you multiply by the next 3000-bit number, get another 6000-bit result, divide this by N and get the result, and so on. Is doing those in Montgomery Space gonna be much faster? Because you mentioned the same speedup is possible with interleaving with the usual modular multiplication which concerned me a bit whether I even need to implement Montgomery Multiplication in the first place. | |
| Jul 24, 2023 at 9:49 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 24, 2023 at 9:43 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 24, 2023 at 9:37 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 24, 2023 at 9:29 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
General algorithm for conversion back to regular PNS simplfies
|
| Jul 24, 2023 at 6:26 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 24, 2023 at 6:07 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 24, 2023 at 5:16 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 24, 2023 at 5:02 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Fix roseta stone
|
| Jul 23, 2023 at 18:32 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Actualy use q instead of m
|
| Jul 23, 2023 at 16:27 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 23, 2023 at 16:15 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Better conversion back to regular PNS. Give references. Align notation.
|
| Jul 22, 2023 at 12:43 | vote | accept | Kevin Stefanov | ||
| Jul 21, 2023 at 12:40 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Fully get rid of floor
|
| Jul 21, 2023 at 12:27 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 21, 2023 at 12:03 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Code optimization considerations. Align notation with MCA.
|
| Jul 21, 2023 at 8:48 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Consustent use of ⋅ for multiplication
|
| Jul 21, 2023 at 8:40 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
More on mod
|
| Jul 21, 2023 at 8:17 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 21, 2023 at 7:45 | vote | accept | Kevin Stefanov | ||
| Jul 21, 2023 at 7:48 | |||||
| Jul 21, 2023 at 5:30 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 21:32 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Remove spurios Beta term
|
| Jul 20, 2023 at 20:38 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
More details on testing result against 1 and N-1
|
| Jul 20, 2023 at 18:43 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 18:26 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 17:45 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 17:37 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 17:22 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 17:15 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 16:15 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jul 20, 2023 at 16:09 | history | answered | fgrieu♦ | CC BY-SA 4.0 |