# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/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](https://doi.org/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](https://doi.org/10.1007/BFb0091534)

## Source

Imported from [FrontierMath: Open Problems, prime-factorization](https://epoch.ai/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.