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.
- 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)
I think it may be a little strong to say that RSA will "become obsolete". Even if a practical QC running Shor's alg can be created, it may be so hard to do that only big organisations can feasibly do it. If so, RSA may still find a use for those who want protection against 'normal' threats (for a suitable definition of 'normal').
--DudeGalea 16:52, 22 May 2005 (UTC)
Shouldn't it be: : ? Evan Ettinger.
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)