Math Conjectures

Deterministic Polynomial-Time Integer Factoring

OPENLandmarkOpen problemProposed c. 1975 · Standard version

Canonical statement

Is there a deterministic algorithm that, on binary input N≥2N\geq2, outputs the prime factorization of NN in time polynomial in log⁡N\log N?
View source LaTeX
Is there a deterministic algorithm that, on binary input
\(N\geq2\), outputs the prime factorization of \(N\) in time polynomial
in \(\log N\)?
TCS-012:[Lenstra2000Factoring][Shor1997Factoring][Pomerance2008Factoring]
Theoretical computer scienceNumber theory

Notes

The problem asks whether the prime factorization of an integer N≥2N\geq 2 can be computed by a deterministic algorithm in time polynomial in log⁡N\log N, that is, in the bit length of the input. The question assumed its modern form around 1975; no single originating paper is documented.

The contrast with neighbouring problems is striking. Deciding whether NN is prime can be done in deterministic polynomial time, yet the best classical factoring algorithms, culminating in the quadratic and number field sieves, run only in subexponential time [Lenstra2000Factoring] [Pomerance2008Factoring]. Shor showed that a quantum computer can factor in polynomial time [Shor1997Factoring], so the obstruction is specifically classical.

No classical deterministic polynomial-time algorithm is known, and no hardness result rules one out; settling the problem requires producing one or the other.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.