About the problem
This problem asks for an algorithm that can factor semiprimes \(N = p \cdot q\) faster than the best known classical methods can. The tests leave a large enough margin that any positive score is very likely to be an algorithmic breakthrough.
Warm-up: we ask for a program that can handle numbers of a size that is doable with existing techniques and software.
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
Produce an algorithm that can factor balanced 90-digit semiprimes on a typical modern laptop in under ten minutes.
Full problem
Produce an algorithm that can factor balanced 150-digit semiprimes on a typical modern laptop in under ten minutes.
Mathematician survey
The author assessed the problem as follows.
a majority of those working in a subfield (≈100)
10–50
3–10 years
a major advance in a broader field; one of the best results of the year
in a leading general journal
very likely: any solution would lead to a rich set of follow-on work
80–95%