TransWikia.com

Factoring algorithms after number field sieves

Computer Science Asked by Zirui Wang on October 21, 2021

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.

One Answer

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).

Answered by Nike Dattani on October 21, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP