Paper 2023/801

We Are on the Same Side. Alternative Sieving Strategies for the Number Field Sieve

Charles Bouillaguet, Sorbonne University, French National Centre for Scientific Research, Laboratoire de Recherche en Informatique de Paris 6
Ambroise Fleury, CEA LIST
Pierre-Alain Fouque, Univ. Rennes, French National Centre for Scientific Research, Institut de Recherche en Informatique et Systèmes Aléatoires
Paul Kirchner

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.

Available format(s)
Attacks and cryptanalysis
Publication info
NFSsievinginteger factoring
Contact author(s)
charles bouillaguet @ lip6 fr
ambroise fleury @ cea fr
pierre-alain fouque @ irisa fr
paul kirchner @ irisa fr
2023-06-06: approved
2023-05-31: received
See all versions
Short URL
No rights reserved


      author = {Charles Bouillaguet and Ambroise Fleury and Pierre-Alain Fouque and Paul Kirchner},
      title = {We Are on the Same Side. Alternative Sieving Strategies for the Number Field Sieve},
      howpublished = {Cryptology ePrint Archive, Paper 2023/801},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.