Talk:Shor's algorithm
Time complexity of Shor's algorithm
In Shor's original paper, he writes
"...Our quantum factoring algorithm takes asymptotically O((log n)^2 (log log n) (log log log n)) steps on a quantum computer, along with a polynomial (in log n) amount of post-processing time on a classical computer that is used to convert the output of the quantum computer to factors of n..."
How does this compare with the O((log n)^3) figure given on the Wikipedia page? (More importantly, how was the O((log n)^3) figure arrived at?) -Yipdw 06:02, 14 May 2006 (UTC)
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 [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
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."
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.
- This is briefly discussed at quantum computer#The power of quantum computers. At the present time, only factorisation and discrete log based ciphers are known to be seriously affected (if a QC of sufficient size could be built). A quantum computer could be used to attack a symmetric cipher, but it's speed up is "only" to take the square root of the number of steps. This is a huge speed up for typical block ciphers, but is trivially defeated by doubling the key size. There exists a standard, thoroughly studied method to double the key size of any block cipher, namely triple encryption. Further, the most common key size used today - 128 bits - would only be reduced to a work factor of the order of , which is still quite a tough job unless the information is extremely valuable. And the AES already has 192 and 256 bit modes built in. So, at our present level of knowledge, QC poses essentially no threat to symmetric encryption. Securiger 07:40, 6 Oct 2004 (UTC)
== Definition of f() in the 'classical part'
Shouldn't it be: : ? 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.
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. Aaron McDaid (talk - contribs) 10:34, 12 February 2006 (UTC)
- No. The step is correct. The chances that gcd(a,N) > 1 are very small when factoring large integers. So in practice this step should always fail to find a factor. Note, however, that the remainder of the algorithm rks if gcd(a,N)=1. Furthermore testing gcd(a,N) is important when factoring small integers such as 15. 24.228.93.22 14:47, 16 February 2006 (UTC)
external link removed
- I removed the external link simply because it is NOT an implementation of Shor's algorithm in php. Such an implementation is impossible because a quantum dynamical system cannot be simulated with a classical system. The implementation ignores the entire quantum portion of the algorithm.
LHon 09:42, 16 April 2006 (UTC)
- ...a quantum dynamical system cannot be simulated with a classical system... Sure it can, just not very efficiently. I'm putting the link back because it's relevant and not spam. —Keenan Pepper 16:58, 16 April 2006 (UTC)