Deterministic Factoring in Time $N^{o(1)}$
The current best upper bound for deterministic factoring is $N^{1/5+o(1)}$. We provide a Lean certificate that there exists a deterministic Turing machine that computes the smallest prime factor of every $N$ in $N^{o(1)}$ steps: for every $k\ge 1$ it runs within $C_k\,2^{n/k}$ steps on $n$-bit inputs. The algorithm reduces factoring to counting divisors with prescribed leading bits, and counts them by leveraging the counting engine used to refute the Exponential Time Hypothesis (ETH). The Lean statement that a reader must check to verify the proof is only 13 lines and only uses Mathlib. The…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00600
curl -X POST /api/v1/records/hexagon/2610.00600/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00600/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'