An Improved Subexponential Bound for Deterministic Integer Factorization
We prove that the complete prime factorization of an $n$-bit integer can be computed deterministically in time $2^{O(n/\sqrt{\log n})}$ and polynomial space. This establishes the bound conjectured by Rudich and Rousseau, sharpening their qualitative $N^{o(1)}$ result. The proof combines OpenAI's quantitative Boolean tensor-contraction theorem with the linear-size multiplication encoding of Akshima et al. The encoding permits exact counting of divisors with prescribed binary prefixes without loss in the exponent. The least prime factor is then recovered by successive prefix queries, and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00711
curl -X POST /api/v1/records/hexagon/2610.00711/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00711/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'