While detecting prime numbers is computationally fast ($O(\log^3 n)$), the fastest known algorithms to split a composite number into its prime factor are very slow (RSA cryptography relies on this assumption). Even the best known algorithms like the number field sieve all run in subexponential time. (Shor's algorithm actually provides a polynomial time algorithm, but on quantum computers.)

I know it is believed that no fast (classical) algorithm exists, but is there a "feeling" as to what could be the optional running time? Often there is a heuristic as to how far you can push the performance long before anybody actually achieves it.

  • $\begingroup$ I was at a talk once where Sarnak said this belief is not well-founded. He compared it to believing the Riemann Hypothesis is false because we haven't found a proof yet. $\endgroup$ – RghtHndSd Jan 5 '15 at 0:47
  • $\begingroup$ As I understand integer factorization is in FNP, so a polynomial time algorithm would imply FNP=FP, and hence NP=P, so I think it is justified to say that it is wide belief that no such algorithm exists? $\endgroup$ – Markus Shepherd Jan 5 '15 at 8:05
  • $\begingroup$ Sorry, this would obviously only hold if the problem was FNP complete. Still, it would have implications to complexity classes that remain unlikely. $\endgroup$ – Markus Shepherd Jan 5 '15 at 8:07
  • $\begingroup$ If I am informed right, it is unknown whether prime factorization is NP-complete, so it could be in P, even if $NP\ne P$. What do you mean with "optimal running time" ? With much good luck, or if the factorization is easy, you will get the result very quickly. Please be more precise! $\endgroup$ – Peter Jan 5 '15 at 12:23
  • $\begingroup$ Indeed, it is conjectured to be in NP-intermediate. What I mean: the fastest known general algorithm is the general number field sieve with a running time of $e^{(\sqrt[3]{64/9} + o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}$. Since the problem is expected not to be in P, we don't expect it to be pushed to $O(\ln^k n)$, but what is the "feeling" in the research community how far we may get, at least in theory? $\endgroup$ – Markus Shepherd Jan 5 '15 at 14:36

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.