Deterministic factoring in N^o(1) steps, Lean-checked, ideas by Claude
Awaiting review
Importance: major (4 of 5)The takeaway
The best proven deterministic factoring algorithms ran in time N^(1/5+o(1)) (Harvey; Harvey–Hittmeir). On 29 Oct Isaac Rudich and Louis-Martin Rousseau (Polytechnique Montréal) posted on Hexagon a Lean 4 proof that one deterministic Turing machine finds the smallest prime factor of every N within C_k·2^(n/k) steps for every k, i.e. N^o(1). The 13-line statement uses only Mathlib and is registered in Palomar; the proof is about 36,000 lines. The authors say every idea and all Lean code came from Claude agents, which they asked to apply the ETH refutation to factoring; they audited the statement, not the proof. The algorithm is ‘galactic’ and slower than the randomised and heuristic methods used in practice; what is new is a proven deterministic N^o(1) bound.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 29 October 2026
Your AI and this story
- GPT-6 Astra182 days after its cutoff
- Claude Opus 5.5121 days after its cutoff
- Gemini 4 Argon212 days after its cutoff
- Grok 4.7151 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 121 days before it.
Key facts
- Claim (Theorem 1, Lean name subexponentialRate): one deterministic Turing machine with finite alphabets outputs minFac(N) and, for every k ≥ 1, halts within C_k·2^(n/k) steps on every n-bit input; running time 2^o(n) = N^o(1). Full factorization in N^o(1) follows (Theorem 2, not in Lean)
- Before (paper): trial division N^(1/2), Lehman N^(1/3), Pollard–Strassen N^(1/4), Hittmeir N^(2/9), Harvey O(N^(1/5) log^(16/5) N), improved by Harvey–Hittmeir by a factor (log log N)^(3/5), ‘the record for every N’. ‘We know of no earlier deterministic bound of the form N^o(1), conditional or not.’ Randomised (Lenstra–Pomerance L_N[1/2]) and heuristic (number field sieve L_N[1/3]) methods remain far faster
- AI role (paper, verbatim): ‘We asked AI to apply the result of the ETH paper to factoring, and then to conjecture how much the exponent could be easily pushed down. The first request produced Theorem 1. ... All the ideas were AI-generated: the reduction, the choice of method, the proof plans and all of the Lean code were produced by AI agents (Claude, Anthropic). Our role was to pose the questions and design the statement.’ And: ‘We have audited this result, not the proof.’ Hexagon tools: Lean 4.35.0, Claude Opus 5.5
- Lean: the audit surface is Challenge.lean (13 lines of statement, imports only Mathlib’s Turing-machine, prime and log files); Solution.lean proves it; #print axioms gives propext, Classical.choice, Quot.sound; the machine model is Mathlib’s TM2 with a finite-alphabet condition added for every stack. Proof about 36,000 lines (35,000 in the Hexagon abstract)
- Uses Sections 3–5 of Anthropic’s ETH refutation (‘A 2^o(n) Time Algorithm for 3-SAT’), re-proved from scratch: the grouping lemma, the eight-square crossing identity and the exponent recursion; ‘Nothing of [OpenAI’s paper] enters the proof’, and nothing is imported from either Lean development (Anthropic’s runs to about 152,000 lines)
- Conjecture 1 (stated in Lean as SqrtLogLogConjecture): factoring in time exp(O(log N/√(log log N)))
- Context: written ‘less than 24 hours after the ETH refutations were posted’ as ‘a stepping stone for those working to understand the engine’; a follow-up paper is to explain the proof. No expert reaction or HN thread found on 29 Oct
What happened
Factoring is easy to verify and hard to do. With randomness or unproved heuristics, the number field sieve and its relatives are fast. Without randomness and with full proofs, the record stood at about N^(1/5), from Harvey’s 2021 algorithm and a small improvement by Harvey and Hittmeir.
Rudich and Rousseau asked Claude agents to apply the counting engine of the ETH refutations to factoring. The agents reduced factoring to counting the divisors of N with prescribed leading bits and counted them with the engine from Anthropic’s #3-SAT paper, re-proved in a separate Lean development. The result is a single deterministic machine that beats 2^(n/k) for every k. The authors checked the 13-line statement and registered the proof in Palomar. They say they did not read the 36,000-line proof and that no human-readable explanation of the engine exists yet.
Why it matters
If the certificate holds, it is the first concrete consequence of the claimed October ETH refutations outside SAT, and it moves a textbook bound in computational number theory. It has no practical effect: by the authors’ own comparison it is far slower than the randomised and heuristic methods already used to factor real numbers, so on its own it gives attackers of RSA nothing new. Its value is the short, checkable statement, which gives readers a way into the engine.
What is disputed or not yet verified
| Verification | Lean 4 proof registered in Palomar (PALOMAR-2026-10-28-000015); unrefereed Hexagon preprint; no human-readable proof yet |
|---|
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 2 primary
Primary
- Hexagon 2610.00600: Deterministic Factoring in Time N^o(1) (Rudich, Rousseau)hexagonmath.org, paper
- Palomar registry entry PALOMAR-2026-10-28-000015palomar-registry.org, code
Changes
- Coordinator spot-check against the Hexagon API record (title, abstract, 13-line statement, ~35,000-line proof match); wording made neutral about the still unverified ETH refutations
- Filed (Hexagon API record and PDF of 2610.00600; HN search found no thread)