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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.