Timeline for Why isn't Montgomery modular exponentiation considered for use in quantum factoring?
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2020 at 9:38 | history | edited | CommunityBot |
Commonmark migration
|
|
| Dec 3, 2010 at 17:26 | comment | added | S Huntsman | So I still haven't heard anything, but I did find this: thescipub.com/abstract/10.3844/jcssp.2009.49.56 which seems to indicate a rather large space overhead their implementation of a reversible Montgomery multiplier. | |
| Nov 25, 2010 at 19:31 | vote | accept | S Huntsman | ||
| Nov 25, 2010 at 18:46 | history | bounty ended | CommunityBot | ||
| Nov 21, 2010 at 15:58 | comment | added | S Huntsman | @blackkettle: Thanks. I write him a few days ago and hope to hear back. Your translation is most helpful. | |
| Nov 21, 2010 at 12:49 | comment | added | Peter Shor | @blackkettle: determining that the space expansion is unavoidable would require new lower bound proof techniques in theoretical computer science, so it's very unlikely this will happen soon. What might happen is finding a more space-efficient way of doing Montgomery modular exponentiation. | |
| Nov 21, 2010 at 4:20 | comment | added | s8soj3o289 | @Peter Shor I didn't translate the very last paragraph, which discusses future directions for research, but the question you pose is precisely what the author wrote. It's unclear however, whether he actually went the distance to determine this or not. Unfortunately his office isn't on the main campus, otherwise I'd mosey on over and ask him myself. | |
| Nov 21, 2010 at 3:15 | comment | added | Peter Shor | Making certain computations reversible may require lots of extra space; this issue is discussed here. | |
| Nov 21, 2010 at 3:08 | comment | added | Peter Shor | It seems to me that the same thing may have gone wrong that goes wrong with Karatsuba's fast multiplication algorithm: making it reversible seems to require using a large number of extra qubits (i.e., space or memory). A good research question is whether this is unavoidable or not. Thanks for the translation. | |
| Nov 21, 2010 at 2:38 | history | edited | s8soj3o289 | CC BY-SA 2.5 |
added some more information
|
| Nov 19, 2010 at 15:53 | comment | added | S Huntsman | Added link to original question. I've seen his website, that's how I figured it was from a 2002 proceeedings. | |
| Nov 19, 2010 at 15:49 | comment | added | S Huntsman | Cripes, I thought I'd pasted this link in the original question. Apparently not: scholar.google.com/scholar?cluster=14809499008269761518 | |
| Nov 19, 2010 at 11:31 | history | answered | s8soj3o289 | CC BY-SA 2.5 |