Jump to content

Talk:Shor's algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Rich Farmbrough (talk | contribs) at 20:34, 2 May 2004. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Shor%27s_algorithm&oldid=3829267"