Welcome to the resource topic for 2023/801
Title:
We Are on the Same Side. Alternative Sieving Strategies for the Number Field Sieve
Authors: Charles Bouillaguet, Ambroise Fleury, Pierre-Alain Fouque, Paul Kirchner
Abstract:The Number Field Sieve (NFS) is the state-of-the art algorithm for integer
factoring, and sieving is a crucial step in the NFS. It is a very
time-consuming operation, whose goal is to collect many relations. The
ultimate goal is to generate random smooth integers mod N with their prime
decomposition, where smooth is defined on the rational and algebraic sides
according to two prime factor bases.
In modern factorization tool, such as \textsf{Cado-NFS}, sieving is split into
different stages depending on the size of the primes, but defining good
parameters for all stages is based on heuristic and practical arguments. At
the beginning, candidates are sieved by small primes on both sides, and if
they pass the test, they continue to the next stages with bigger primes, up to
the final one where we factor the remaining part using the ECM algorithm. On
the one hand, first stages are fast but many false relations pass them, and we
spend a lot of time with useless relations. On the other hand final stages are
more time demanding but outputs less relations. It is not easy to evaluate the
performance of the best strategy on the overall sieving step since it depends
on the distribution of numbers that results at each stage.
In this article, we try to examine different sieving strategies to speed up
this step since many improvements have been done on all other steps of the
NFS. Based on the relations collected during the RSA-250 factorization and all
parameters, we try to study different strategies to better understand this
step. Many strategies have been defined since the discovery of NFS, and we
provide here an experimental evaluation.
ePrint: https://eprint.iacr.org/2023/801
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .