Search epoch.ai
Prime Factorization
Improve the constant factor in the exponent of GNFS.
On this page:
About the problem
Attempts by AI
AI prompts
Mathematician survey
About the problem
The best known classical algorithm for factoring large integers is the general number field sieve (GNFS). It is exponential in the number of digits of the number to be factored. While polynomial time quantum algorithms are known for integer factorization, it is not known whether polynomial time classical algorithms exist. It is more likely, however, that significant improvements to GNFS are possible.
The goal of this problem is to find such an improvement. We verify solutions numerically, by testing proposed algorithms on challenge integers with limited computational resources (e.g., running on a laptop). The challenges are selected to ensure that the only way to succeed would be to generate an improvement at least as good as a significant improvement in the constant factor in the exponent in GNFS runtime.
This would be a major breakthrough in computational number theory.
Warm-up: we ask for a program that can handle numbers of a size that is doable with existing techniques and software.
Attempts by AI
We have evaluated the following models on this problem. “Warm-up” refers to an easier variant of the problem with a known solution.
AI Prompts
The difficulty level can be tuned by setting the size of number to factor. 90 digits should be doable just using existing software. 150 digits is likely in "breakthrough" territory.
Warm-up
Full problem
Mathematician survey
The author assessed the problem as follows.