5
$\begingroup$

It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. So are there faster algorithms after GNFS for classical computers? Note that the 1980s and 1990s saw a series of new factoring algorithms, including elliptic curve and quadratic sieve. And then progress stopped.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

From the first line of Wikipedia's GNFS page:

"the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than"

The following factorizations of RSA numbers used none other than the GNFS algorithm:

Conclusion: The top researchers in the field are breaking factorization records using none other than GNFS (usually the CADO-NFS implementation). If there was a faster factorization algorithm for arbitrary semi-primes, surely the groups of Zimmerman and Lenstra would be using it, or at least mentioning it somewhere in their papers. GNFS is still the fastest for arbitrary semi-primes. For specific semi-primes like $p^2$ where $p$ is prime, there's faster algorithms such as doing the square root.

A more interesting question might be: What are some recent developments in the field of factoring numbers on classical computers? I might also be interested if there's anything promising out there that's been developed recently and might have a chance at beating GNFS one day. Also if you look at the above references, the authors will tell you of great achievements in improving implementations of the GNFS algorithm (for example the matrix step used to be harder than the sieving itself, but that was sorted out at around the time of factoring RSA-220).

$\endgroup$
5
  • $\begingroup$ Graph of records there [disclaimer: self-reference]. Worth mentioning: GNFS is the best algorithm in the worst case: factoring a composite product of two large primes of about equal size. But for the average case of factoring a random integer, the best algorithm is a compound of various things. $\endgroup$
    – fgrieu
    Jul 25, 2020 at 19:20
  • $\begingroup$ @fgrieu Is RSA-250 not already there in my list? $\endgroup$ Jul 25, 2020 at 19:21
  • $\begingroup$ Did I mention RSA-250? ;-) Note: RSA-220, RSA-230, and RSA-232 are not records; the modulus is smaller than what was factored December 2009 with RSA-768. However they did improve on resources required. $\endgroup$
    – fgrieu
    Jul 25, 2020 at 19:27
  • $\begingroup$ @fgrieu You did! But you edited your comment now. The last edit of my answer was 8 minutes before the first version of your comments :) About those not being records, my answer says "The following factorizations of RSA numbers used..." not "The following records used..." $\endgroup$ Jul 25, 2020 at 19:31
  • 1
    $\begingroup$ Agreed for all. None of my comments where critics of your answer (I did the the upvote), just additional material. $\endgroup$
    – fgrieu
    Jul 25, 2020 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.