Content deleted Content added
m Removed obsolete comment |
Aaron McDaid (talk | contribs) pointed out possible error in the classical part. Also, I put section headings on the questions to organize this page a little. |
||
Line 1:
==speed of various classical factoring algorithms==
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 [http://citeseer.nj.nec.com/398050.html] is significantly faster than that, with a running time of theta(exp(((64/9)*log N)<sup>1/3</sup> (log log N)<sup>2/3</sup>). I've changed the sentence to claim superpolynomial rather than exponential. --[[user:LC|LC]]
Line 8 ⟶ 9:
==Encryption schemes not vulnerable to quantum computing==
"Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer."
Line 18:
== Definition of f() in the 'classical part'
Shouldn't it be: :<math>f(r) = a^r\ \mbox{mod}\ N</math> ? Evan Ettinger.
== Jones' Algorithm==
Shor and Jones (Jones's Period Proxy Algorithm) use the same algorithm, however, Shor focusses on using a quantum computer and Jones looks for hyper-reduced reptends to solve in polynomial time.
[[User:166.70.15.234|166.70.15.234]] 18:10, 2 Apr 2005 (UTC)
==Error in the 'classical' part==
Isn't this wrong:
:''If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.''
It should be ''trivial'' factor, shouldn't it? I'll change it myself soon if no-one replies. [[User:Aaron McDaid|Aaron McDaid]] <small>([[User_talk:Aaron McDaid|talk]] - [[Special:Contributions/Aaron McDaid|contribs]]) </small> 10:34, 12 February 2006 (UTC)
[[Category:To do]]
| |||