Can integers be factored in polynomial time?

Still open as of 2026.

The presumed hardness of factoring is what protects the RSA cryptosystem. The decision version of factoring lies in NP and co-NP, and even in UP and co-UP, so it is unlikely to be NP-complete. The fastest known classical method for large numbers, the general number field sieve, runs in heuristic time $\exp (((64/9{)}^{1/3}+o(1))(\ln N{)}^{1/3}(\ln \ln N{)}^{2/3})$, which is subexponential but far from polynomial. In 1994 Peter Shor showed that a quantum computer could factor in polynomial time. Whether a classical polynomial-time algorithm exists is open.

References

• Integer factorization (Wikipedia)