Talk:Shor's algorithm: Difference between revisions
No edit summary |
No edit summary |
||
Line 13: | Line 13: | ||
Are there any encryption systems that would not be obsolete if a quantum computer becomes practical? That would be useful information to add here, if anyone knows. I have been trying to look this information up but nothing so far, anyone have any clues?--[[User:ShaunMacPherson|ShaunMacPherson]] 22:06, 12 Apr 2004 (UTC) |
Are there any encryption systems that would not be obsolete if a quantum computer becomes practical? That would be useful information to add here, if anyone knows. I have been trying to look this information up but nothing so far, anyone have any clues?--[[User:ShaunMacPherson|ShaunMacPherson]] 22:06, 12 Apr 2004 (UTC) |
||
One time pads would be unaffected. Richard Farmbrough. |
Revision as of 20:34, 2 May 2004
The article said the best classical factoring algorithms are O(e^N). The author presumably meant theta rather than O. The General Number Field Sieve [1] is significantly faster than that, with a running time of theta(exp(((64/9)*log N)1/3 (log log N)2/3). I've changed the sentence to claim superpolynomial rather than exponential. --LC
Okey dokey. You might want to make a wiki node on that. -- CYD
OK. It's integer factorization. --LC
Thanks! -- CYD
--
"Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer."
Are there any encryption systems that would not be obsolete if a quantum computer becomes practical? That would be useful information to add here, if anyone knows. I have been trying to look this information up but nothing so far, anyone have any clues?--ShaunMacPherson 22:06, 12 Apr 2004 (UTC)
One time pads would be unaffected. Richard Farmbrough.