A claim is circulating that integer factoring has been proven subexponential, with a deterministic worst-case bound, following reports that AI systems at Anthropic and OpenAI refuted the Exponential Time Hypothesis. Mathematician Elliot Glazer posted on X that "integer factorization has been proven subexponential (deterministically, worst-case bound)" and that the hard work came from Claude's version of the ETH refutation, with a bit more needed for factoring. A Lean 4 repository now backs a formal statement. Before anyone panics about encryption, this post sorts what is claimed from what is verified.
For the ETH background, see our earlier post on [OpenAI's claimed refutation](https://explainx.ai/blog/openai-exponential-time-hypothesis-false-kakeya-yang-mills-three-results-lean-collaborations-2026). For how labs are probing cryptography with AI, see [the Aaronson and Buterin discussion](https://explainx.ai/blog/ai-labs-probing-cryptography-break-aaronson-drake-buterin-claimed-vs-verified-2026).
## TL;DR: claimed vs. verified
| Statement | Status |
|---|---|
| A deterministic Turing machine finds the smallest prime factor of N in N^o(1) time | Claimed; formal Lean 4 proof in a public repo checks the stated theorem |
| The proof is correct as mathematics | Not independently refereed; unrefereed preprints underlie it |
| The Lean statement faithfully models factoring | Needs human audit; the authors designed it |
| Full factorization is covered | No: the repo states it formalizes only the smallest prime factor |
| RSA and current encryption are broken | No: the algorithm is galactic, with astronomically large constants |
| The result came from AI | Yes, per the repo: ideas and Lean code generated by Claude |
What does the repository say? #
The SubexponentialDeterministicFactoring repository, by Isaac Rudich and Louis-Martin Rousseau of Polytechnique Montreal and licensed Apache 2.0, contains a Lean 4 proof checked against Mathlib. Its claim: one deterministic Turing machine computes the smallest prime factor of any natural number N in time N^o(1). Precisely, for every k at least 1 there is a constant C_k such that the machine runs in C_k times 2 to the floor of n over k steps on n-bit inputs, which is about N^(1/k).
On provenance, the repository states: "The ideas and the Lean code were generated by AI (Claude, Anthropic)." The authors posed the questions and designed and audited the statement, but say they did not read the proof, which Lean checks.
It is organized to make the statement auditable. A Challenge.lean file states the theorem with sorry on purpose and imports only Mathlib. A Solution.lean proves the same statement by citing a lemma in an auxiliary folder of roughly 36,000 lines across 143 files, plus about 5,000 lines of copied files. The repo reports no sorry, admit, native_decide, unsafe, partial def or new axioms, with only the standard axioms (propext, Classical.choice, Quot.sound), and a Comparator tool configured to check that the solution matches the challenge.
What are the repo's own caveats? #
The authors list limits that matter more than the headline:
- "Factoring" means the smallest prime factor. Full factorization by repetition is not formalized.
- Machine model. Time is counted as steps on Mathlib's
TM2Turing machine model. - Constants. The C_k exist but are not computed, and are described as astronomically large.
- "Galactic" algorithm. It only beats existing methods for astronomically large N.
- A stronger conjecture is stated, not proved.
SqrtLogLogConjecture(factoring in time exp(O(log N over the square root of log log N))) was proposed by the AI and is explicitly unproved.
The repository also cites its sources: a 3-SAT preprint by Claude dated October 26, 2026, and an OpenAI preprint, "The Exponential Time Hypothesis Is False," dated October 17 and revised October 25, both unrefereed. It says the request that led to the factoring result was to apply the OpenAI preprint's result to factoring, and that none of that preprint's content enters the proof. For comparison, it points to Schonhage-Strassen (1971) and Harvey and Hittmeir's deterministic bounds with a fixed exponent.
What does Lean verify, and what does it not? #
Lean verifies that a stated theorem follows from the axioms of its logic. That is a very strong guarantee about the proof, and a weak one about the statement. If the definitions in Challenge.lean do not capture what a reader means by "factoring on a Turing machine," the theorem could be true and still beside the point. The authors designed the statement, so an independent audit of the definitions is the next step. This is the same lesson from our posts on Claude's 3SUM and APSP claim and Axiom's finite simple groups classification in Lean: a formal proof shifts the burden from checking steps to checking definitions.
Glazer also reported, per search coverage of his post, that he had an AI system audit the result and that the Lean certifies exactly what it says, though the English-language proof has errors. We could not independently open the full thread, so treat that as his report.
What about the second repository? #
A separate repository, factoring-connection, takes a different tone. It reports AI-assisted results on rigorous randomized factoring in several regimes (L[1/2, c], L[1/2, o(1)] and L[2/5]), conditional L[3/8], discrete logs, and deterministic bounds of N^(1/6) on average over balanced semiprimes and N^(1/5) worst case. It says Claude agents wrote the code and notes, GPT-6.1-sol via Codex CLI ran literature sweeps and adversarial reviews, and Opus critics reviewed the proofs, with parts formalized in Lean and others left as hypotheses.
Its audit status is stated plainly: the results are "proved internally and audited by blind AI referees, but NOT refereed by a human," with verdicts of "accept with fixes" and confidence figures such as about 70% for one window and about 55% for 3/8. The owner asks readers to treat them as claims until an expert checks the chain. At the time we read it the repo had zero stars and zero forks. This is useful transparency, and it also shows how little independent scrutiny exists so far.
Does this break encryption? #
Not on the evidence available. Three reasons:
- The algorithm is impractical. Subexponential in the theoretical sense can still be unusable. The repository says the constants are astronomically large and the benefit appears only for astronomically large inputs.
- The best practical methods already run in subexponential time. Factoring has long had subexponential algorithms such as the number field sieve, which is what real RSA key sizes are chosen against. The new claim is about a deterministic, rigorously proven bound, which is a theory milestone, not a faster attack on 2048-bit keys.
- Reporting agrees. An aggregator summary citing a report from The Information says the finding does not threaten current encryption methods, while raising questions about other assumptions. We could not open that report, so this is secondhand.
If you run systems that depend on RSA, nothing here changes your key-size guidance today. Standard advice about migrating toward post-quantum schemes is driven by different considerations.
How was the discovery described? #
Posts summarized by an aggregator say the core algorithm was found on October 16 by an internal Claude research model, using about 14 million output tokens with no human input, and that OpenAI's models separately reached a similar ETH result. We could not confirm those details from primary documents, and they come from social posts of individuals reacting to the news. What is documented in primary form are the two preprints (as cited by the repository) and the repositories themselves.
How should a non-specialist read "subexponential"? #
The word sounds dramatic, so it helps to pin it down. An algorithm is exponential if its running time doubles each time you add a bit to the input, as in a brute-force search for a factor. Subexponential means it grows more slowly than any such exponential, but it can still grow faster than every polynomial, which is what people usually mean by "efficient." Breaking a 2048-bit key still needs an astronomical amount of work under every subexponential method known.
The repository's formulation, a running time of C_k times 2 to the floor of n over k for every fixed k, says that for any root you pick, a machine exists that beats trial division up to that root by a constant factor. The catch is the constant: it depends on k and is never computed. That is why the authors call the algorithm galactic. The result matters as a statement about what is provable about the structure of the problem, and as evidence that automated systems can now produce formal results of this size. It does not hand anyone a faster tool today.
What should you watch? #
- Expert review of the Lean statement by complexity theorists and Lean/Mathlib maintainers.
- A human-readable proof that others can read. Glazer's reported note that the English version has errors is a red flag for exposition, not necessarily for correctness.
- Refereed versions of the OpenAI and Claude ETH preprints.
- Whether the sqrt-log-log conjecture becomes a real result.
- Cryptographers' statements. Any response from standards bodies would be the strongest signal about practical risk.
What this means for builders #
AI systems are now producing large formal artifacts faster than humans can read them. That raises a verification-tax problem: the cost of checking moves from "is each step valid" to "is the statement meaningful" and "is the trust base small." If you build with AI-generated proofs or code, keep your trusted statement small and human-reviewed, and require independent audit of definitions.
Related reading #
Based on the public repositories and posts as of October 30, 2026. We did not run the Lean proofs ourselves.