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 Original: eprint.iacr.org/2013/147 ↗

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

Naomi Benger

Manuel Charlemagne

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: Preprint.
History: 2013-04-03: last updated; 2013-03-15: published
Short URL: https://ia.cr/2013/147
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2013/147}
}