O5b — Randomized polynomial-time integer factorization

Definitions and mathematical statement

For an integer $N\ge2$, its complete prime factorization is the list of distinct primes and positive exponents \[ N=p_1^{e_1}\cdots p_t^{e_t},\qquad p_1<\cdots<p_t. \] The input and every integer in the output are written in binary. The problem includes arbitrary composite inputs and prime powers, not only products of two primes.

Does a classical randomized algorithm compute this factorization in polynomial time in $\ell(N)=\lfloor\log_2N\rfloor+1$? An explicit equivalent search formulation asks for constants $C,c>0$ and a probabilistic algorithm which, on every $N$, uses at most $C(1+\ell(N))^c$ bit operations and returns the correct complete list with probability at least $2/3$, the probability being over its internal random bits. The guarantee is required separately for each input, rather than on average over a distribution of integers.

One can instead require a Las Vegas algorithm: every returned list is correct and the expected running time is polynomial in $\ell(N)$. These formulations agree here because a proposed list can be checked by multiplying the prime powers and testing the listed factors for primality; failed or incorrect trials can be rejected and repeated. Conversely, truncating an expected-polynomial computation gives constant success probability. The target is classical bit complexity; access to quantum operations is not part of the computational model.

Short English statement

Does complete integer factorization admit a classical randomized algorithm with polynomial running time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400005 (AMR-083-0005), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O5b, p7 / LNCS p297. Original source indexed by AMR-083-0005. https://mccurley.org/papers/open.ps.gz.