Timeline for Discrete logs vs. factoring
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2009 at 0:35 | comment | added | Harrison Brown | Hmm... I'm still a bit lost as to why classical algorithms tend to work nicely for both, though. For instance, the number field sieve (well, the rational sieve, which I actually understand) doesn't seem to be computing any sort of period... | |
| Nov 3, 2009 at 23:18 | history | edited | Steve Flammia | CC BY-SA 2.5 |
fixed typo
|
| Nov 3, 2009 at 17:48 | comment | added | Steve Flammia | Yes, the quantum Fourier transform can be employed to break elliptic curve crypto. As a rule of thumb (not a rigorous statement), anything that relies on abelian group structure is susceptible to a quantum attack. I say it's a rule of thumb because we don't know in general how to turn black box query algorithms into "real" quantum algorithms for all cases. But the raw black box algorithms are very powerful for any problem involving Abelian group structure, so if I were extremely paranoid, I would not trust any such crypto scheme. | |
| Nov 3, 2009 at 17:17 | comment | added | Harrison Brown | So does Shor's algorithm break elliptic-curve crypto, too? I was under the impression that it didn't, but admittedly that's mostly just because I've never had anyone tell me that it did. | |
| Nov 3, 2009 at 14:53 | history | answered | Steve Flammia | CC BY-SA 2.5 |