Talk:Shor's algorithm: Difference between revisions

Content deleted Content added

Inline

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.

Revision as of 22:06, 12 April 2004 edit ShaunMacPherson (talk \| contribs) Pending changes reviewers 3,043 edits No edit summary ← Previous edit		Revision as of 20:34, 2 May 2004 edit undo Rich Farmbrough (talk \| contribs) Edit filter managers, Autopatrolled, Extended confirmed users, File movers, IP block exemptions, Pending changes reviewers, Rollbackers, Template editors 1,720,893 edits No edit summary Next edit →
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.