A note on the practical complexity of the NFS in the medium prime case: Smoothness of Norms

Naomi Benger; Manuel Charlemagne; Kefei Chen

Paper 2013/147

A note on the practical complexity of the NFS in the medium prime case: Smoothness of Norms

Naomi Benger, Manuel Charlemagne, and Kefei Chen

Abstract

During an ongoing examination of the behaviour, in practice, of the Number Field Sieve (NFS) in the medium prime case we have noticed numerous interesting patterns. In this paper we present findings on run-time observations of an aspect of the sieving stage. The contributions of these observations to the computational mathematics community are twofold: firstly, they bring us a step closer to understanding the true practical effectiveness of the algorithm and secondly, they enabled the development of a test for the effectiveness of the polynomials used in the NFS. The results of this work are of particular interest to cryptographers: the run-time of the NFS determines directly the security level of some discrete logarithm problem based protocols, such as those arising in pairing-based cryptography.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: DLP NFS pairing based cryptography
Contact author(s): charlem @ sjtu edu cn
History: 2013-04-03: last of 3 revisions; 2013-03-15: received; See all versions
Short URL: https://ia.cr/2013/147
License: CC BY

BibTeX

@misc{cryptoeprint:2013/147,
      author = {Naomi Benger and Manuel Charlemagne and Kefei Chen},
      title = {A note on the practical complexity of the NFS in the medium prime case: Smoothness of Norms},
      howpublished = {Cryptology ePrint Archive, Paper 2013/147},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/147}},
      url = {https://eprint.iacr.org/2013/147}
}