Classical integer factorization

Start with 77. Multiplying 7 by 11 gives 77, and multiplying them again checks the answer. Factoring reverses that operation: given only 77, find its prime building blocks, 7 and 11. A prime is a whole number greater than 1 divisible only by 1 and itself. For much larger numbers, that search can require enormous work. The question is whether an ordinary classical computer can find every prime factor with a reliable efficiency guarantee as the number of written digits grows.[1]

Multiplication builds a number from its prime factors; factoring must find those building blocks from the number alone. For example, 77 gives 7 and 11. Can a classical method do this efficiently for every input, including repetitions of a prime factor?

The input length is its number of binary digits. For $N\geq1$, write $b=\lfloor\log_2 N\rfloor+1$. The target is an algorithm returning $N=\prod_i p_i^{a_i}$, with distinct primes $p_i$ and positive integer exponents $a_i$, within $Cb^c$ classical bit operations for fixed constants $C,c$; $N=1$ has an empty product. This is polynomial time: a fixed power of the written length, rather than of the number's value.

The deterministic and bounded-error randomized versions remain unresolved. A randomized method may use random choices; the chosen target requires success probability at least $2/3$ on each input and a polynomial time bound on every run. Repetition can increase that probability, but cannot replace the required time bound.[1] [2]

Researchers can factor many numbers and have completed remarkable individual calculations. RSA-250 was announced factored in 2020; RSA-260 and RSA-896 have published factors from September 2026. Each is a solved numerical example. The open question asks for one classical method with an efficiency guarantee covering every input, however long. Shor’s algorithm supplies a quantum answer, using a different kind of computation.[1] [3] [4] [5]

A common factoring strategy seeks two different squares with the same remainder. For example, $20^2$ and $13^2$ both leave remainder 15 when divided by 77. The greatest common divisor is the largest positive integer dividing both its arguments; here

$$\gcd(20-13,77)=7,\qquad\gcd(20+13,77)=11.$$

The general number field sieve collects arithmetic relations that can produce such congruences, but not every congruence yields a nontrivial factor. Its usual heuristic running-time estimate has the form $\exp(Kb^{1/3}(\log b)^{2/3})$, for a positive constant $K$, apart from lower-order terms. As $b$ grows, this exceeds every fixed power of $b$.

Pollard's $p-1$ method instead benefits when a prime factor $p$ has $p-1$ built from small prime factors. Neither mechanism supplies the required general classical bound; failing to find one also does not prove that none exists.[1] [2] [4] [8] [9]

An easy check does not automatically give an easy way to find an answer. Factoring makes that gap tangible and helps us compare classical and quantum computers. It also matters for RSA: finding a key’s prime factors allows recovery of its private operation. RSA can fail through other attacks too, so a factoring milestone describes one route through a larger cryptographic subject.[1] [6] [7]

For a two-prime RSA modulus $N=pq$, the factors reveal $\varphi(N)=(p-1)(q-1)$. This lets the private exponent $d$ be computed as an inverse of the public exponent $e$ modulo $\varphi(N)$: their product leaves remainder one. Factoring is therefore sufficient to recover the RSA private operation. It does not establish an equivalence between factoring and all RSA inversion or protocol attacks.

Shor takes another route: a quantum procedure finds a multiplicative order, the first positive exponent returning a chosen number to remainder one. Classical greatest-common-divisor calculations can turn a suitable order into factors. The contrast asks whether changing computational resources enables a task that every classical method must find expensive. The quantum algorithm is known, but the classical efficiency question remains open; an unconditional lower bound would have to rule out all algorithms in that chosen model.[1] [6] [7] [8]