Factoring integers much faster than the number field sieve

Much of public-key cryptography rests on the difficulty of factoring a product of two large primes. The best classical algorithms, the elliptic curve method and the quadratic and number field sieves, have stood for decades. Epoch asks for a program that factors semiprimes so much faster than these methods would that only a new algorithmic idea could explain it.

Problem

Let $N = pq$ be a product of two primes.

Task. Give a classical algorithm that factors such $N$ substantially faster than the best known methods: Lenstra's elliptic curve method (ECM) when one factor is much smaller than the other [1], and the quadratic sieve or the general number field sieve (GNFS) when the factors are balanced [2].

Epoch makes "substantially faster" measurable. For each challenge it estimates the single-threaded time the best classical method would need, from calibrated cost models based on the standard subexponential complexities, and gives credit only for a speedup above

$$16 \times 10 \times 1000 \approx 1.6 \times 10^5,$$

the three factors allowing for parallel cores, calibration error, and the genuine algorithmic gain required.

Background

Whether integers can be factored in polynomial time on a classical computer is a central open question in computational complexity; formal-conjectures states it in Lean as isPolyTime_primeFactorsList in IntegerFactorization.lean. Lenstra's elliptic curve method (1987) finds a prime factor in time governed mainly by the size of that factor [1]. The number field sieve, whose development is collected in [2], has the best known heuristic running time for general $N$.

What is known

• ECM is the method of choice when one factor is small; the quadratic sieve and GNFS dominate for balanced semiprimes (Epoch's cost model uses these three regimes).
• No classical algorithm with an asymptotically better running time than GNFS is known for general $N$.
• Epoch notes a risk of false negatives: its margin is deliberately large, so even a notable algorithmic improvement could be rejected.

What would count as progress

• A program, together with a description of the algorithm, that factors challenge semiprimes beyond the cutoff speedup. Correctness is trivial to check by multiplying the factors.
• Epoch scores submissions with its own verifier: a Python or Sage program receives $N$ and prints the two prime factors. It is run on up to 20 challenges within 30 minutes; the submitter may fix the bit sizes of $p$ and $q$ (between 3 and 3000 bits), and only challenges the cost model prices well above the cutoff can score.
• Independently of timing, a heuristic or rigorous analysis giving a smaller asymptotic exponent than the number field sieve would be the real contribution.

References

1. H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649–673. doi:10.2307/1971363
2. A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Math. 1554, Springer (1993). doi:10.1007/BFb0091534

Source

Imported from FrontierMath: Open Problems, prime-factorization, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.