Timeline for Modular exponentiation without range restriction
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2020 at 13:24 | history | edited | CommunityBot |
Commonmark migration
|
|
| Feb 19, 2018 at 9:34 | comment | added | Toby Speight |
Perhaps I was too concise and cryptic there, @chux. Or perhaps I haven't thought it through completely. We do know that (1+UINTMAX_MAX)%mod must be less than mod, but perhaps I was just pontificating on an idea without working it out properly. I might have to consider this a bit further.
|
|
| Feb 17, 2018 at 20:53 | comment | added | chux |
@TobySpeight The "we can multiply the upper result by (1+UINTMAX_MAX)%mod ..." needs more detail. The "upper" result is a full width uintmax_t and (1+UINTMAX_MAX)%mod is also a full width uintmax_t. The product of these 2, in essence, reenters the Alternative fall-back algorithm. The alternative may be promise, yet it seems to cycle back on itself - any ideas or reference to this?
|
|
| Feb 12, 2018 at 15:46 | comment | added | chux | The Alternative fall-back algorithm has merit and is a good idea. The expansion of the idea may have missed some carry concerns, yet it is likely faster than the bit-wise loop of the original code. | |
| Feb 12, 2018 at 15:43 | comment | added | chux | Concerning self-test: See comment. IAC, the test code is only an ancillary review part. Yet I do appreciate your thoughts about it. | |
| Feb 12, 2018 at 12:55 | comment | added | Toby Speight |
@vnp: even without Karatsuba's algorithm, I should have recognised that we're computing a square, so we have (h+l)²==h² + 2hl + l² for only three multiplications.
|
|
| Feb 12, 2018 at 12:16 | comment | added | vnp | Three multiplications, actually. | |
| Feb 12, 2018 at 12:04 | history | edited | Toby Speight | CC BY-SA 3.0 |
Mention faster alternative
|
| Feb 12, 2018 at 11:35 | history | answered | Toby Speight | CC BY-SA 3.0 |