# Two questions on Shor's algorithm

Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from wikipedia. If not what is the 'right' number of comparable 'bit' operations in the classical model?

What is the hidden constant in $O((\log n)^{2+\epsilon})$?

As far as we know the $2$ in the exponent could be brought down to $1$. There have been many techniques in classical factoring/discrete log calculation that tried to reduce complexity over many decades. Has there been any attempt to bring the exponent from $2$ down to $1$? Or is there a proof that $2$ is the best that can be done?

• Could you provide the reference for that bound? – Juan Bermejo Vega Jul 31 '15 at 11:32
• Yes, people have tried to bring the exponent on the $\log$ down. And there's no proof that 2 is the best possible. – Peter Shor Jul 31 '15 at 12:52
• @PeterShor Thank you is there a reference on such attempted lower bounds or upper bounds? – 1.. Jul 31 '15 at 13:04
• Since people don't usually write up unsuccessful attempts, one wouldn't expect to find references. – Peter Shor Jul 31 '15 at 16:30
• @PeterShor Thank you. Is the hidden constant very small? – 1.. Jul 31 '15 at 23:23