International Association
for Cryptologic Research

During an ongoing examination of the practical complexity of the Number Field Sieve (NFS) in the medium prime case we have noticed numerous interesting patterns. In this paper we present findings on the complexity in practice 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 complexity 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 practical complexity of the NFS determines directly the security level of some discrete logarithm problem based protocols, such as those arising in pairing-based cryptography.