Deterministic integer factoring in time
Every deterministic integer factoring algorithm with a proved running time has had a fixed positive exponent: trial division , Lehman , Pollard and Strassen , Hittmeir , and Harvey's (2021), improved only by logarithmic factors since. The rigorous subexponential methods (Dixon, Lenstra-Pomerance) are randomized, and the deterministic sieves rest on unproved heuristics. Is there one deterministic algorithm that factors every positive integer in time , that is, in time for every ?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Computational number theory; integer factoring
- Posed by
- —
- Year posed
- —
- Years open
- —
- Solved
- 2026-10-29
- Model
- Claude Opus 5.5
- Vendor
- Anthropic
- Collaborators
- Isaac Rudich, Louis-Martin Rousseau
- Verification
- Lean-checked, statement unaudited
- Publication
- Preprint
- Significance
- 38 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1 (in Lean): one deterministic Turing machine (Mathlib's TM2 model, every alphabet finite, input and output in binary) outputs the smallest prime factor of and, for every , halts within steps on -bit inputs, so in time . Theorem 2 (not in Lean, a few lines): applying it at most times gives the complete factorization in time . The algorithm is galactic and slower than the heuristic sieves; what is new is a proved deterministic bound.
What the AI did
Per the paper and its Hexagon provenance statement, all the ideas were AI-generated: the reduction to counting divisors with prescribed leading bits, the choice of method (a re-proved part of the counting engine of Anthropic's 3-SAT preprint) and the whole 36,000-line Lean proof were produced by Claude Opus 5.5 agents, which also drafted the exposition. The two authors posed the questions, designed and audited the 13-line formal statement, and edited the text; they say they did not read the proof.
Verification
No independent mathematician has checked this yet. Lean-checked on this site's ladder, not Lean-verified. Checked here on 15 November 2026: the Hexagon paper 2610.00600v1 and its provenance page, which carry the AI disclosure. Palomar entry PALOMAR-2026-10-28-000015 v1 read: source IsaacRudich/SubexponentialDeterministicFactoring at commit 5f5ff8f, Lean v4.35.0, Comparator theorem Factoring.subexponentialRate, permitted axioms propext, Quot.sound and Classical.choice, kernel replays by Palomar (nanoda, con-ron). Challenge.lean (79 lines, Mathlib imports only) was read in full: factoring is Nat.minFac; the machine is a Mathlib TM2ComputableInTime with binary encodeNat on input and output; every stack alphabet must be finite, which closes the infinite-alphabet loophole in Mathlib's model; time is the step bound as a function of input bit length; and one machine comes before every k, with a constant per k. That is the headline, stated faithfully, for the smallest prime factor; full factorization is a short argument outside Lean. A grep of all 146 Lean files (about 36,000 lines) found no sorry outside the challenge stub and no axiom, admit, native_decide, implemented_by, extern or unsafe. Not rebuilt here, and the repository has no CI. No independent formal statement (Formal Conjectures or a tracker) was found.
Sources
- PaperHexagon PDF 2610.00600v1Harvey, An exponent one-fifth algorithm for deterministic integer factorisation (previous record)
- Lean proofLean repository at commit 5f5ff8f
- Lean statementHeadline statement (Challenge.lean)
- OtherHexagonPalomar PALOMAR-2026-10-28-000015 v1Related entry: the Exponential Time Hypothesis
Submitted by MellowGander562 on