Rudich and Rousseau: "Deterministic Factoring in Time N^o(1)"
A deterministic Turing machine computes the smallest prime factor of every N in N^o(1) steps: for every k ≥ 1, within C_k·2^(n/k) steps on n-bit inputs.
What was claimed: A deterministic Turing machine computes the smallest prime factor of every N in N^o(1) steps: for every k ≥ 1, within C_k·2^(n/k) steps on n-bit inputs.
What Lean states: A 13-line statement using only Mathlib; a proof of about 35,000 lines (Palomar PALOMAR-2026-10-28-000015 v1) — 13-line Mathlib statement: ∀ k ≥ 1, ∃ C_k bounding steps by C_k·2^(n/k) (~35,000-line proof generated by Claude Opus 5.5).
Prose only / the gap: Magnitude of existential C_k and the crossover input size where the bound improves on N^(1/5+o(1)).
Verification & replays: None found in the sources read. Not replayed by SeamCert.
What the public sources report
Every item below is attributed to the published paper, replay, or commentary that reported it.
| Previous best | Deterministic factoring in N^(1/5+o(1)). [1] |
|---|---|
| How | Reduces factoring to counting divisors with prescribed leading bits, counted with the engine behind the ETH refutations, re-proved rather than imported. [1] |
| Provenance | The ideas and the Lean proof were generated by Claude Opus 5.5. The authors specified and audited the formal statement and "did not read the proof, which is checked by Lean". [1][2] |
| Independent replays | None found in the sources we read. |
Open specification seams (our reading)
Our reading of the sources above: the places where the formal Lean statement and the informal headline claim can still come apart.
- The constant C_k is existential: the statement says nothing about how large it is, so nothing about the input size from which this beats N^(1/5).
- The 13-line statement is the whole audit surface. Its machine model and input encoding need the same reading as the ETH statements.
- The claim is about deterministic, proved bounds; heuristic methods such as the number field sieve are a different comparison.
Footnotes & Sources
- Isaac Rudich and Louis-Martin Rousseau, "Deterministic Factoring in Time N^o(1)" (Hexagon 2610.00600v1)
- Papex, "Has the ETH refutation been verified?" (31 October 2026)
Sources read on 7 November 2026. Spotted an error or a newer independent replay? Write to [email protected].