Abstract
As we examine the behaviour of the number field sieve (NFS) in the medium prime case, we notice various patterns that can be exploited to improve the running time of the sieving stage. The contributions of these observations to the computational mathematics community are twofold. Firstly, we clarify the understanding of the true practical effectiveness of the algorithm. Secondly, we propose a test for a better choice of the polynomials used in the NFS. These results are of particular interest to cryptographers as the run-time of the NFS directly determines the security level of some discrete logarithm problem based protocols.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
POLLARD J M. Monte Carlo methods for index computation (mod p) [J]. Mathematics of Computation, 1978, 32: 918–924.
TESKE E. Speeding up Pollards Rho method for computing discrete logarithms [C]//Algorithmic Number Theory Symposium (ANTS IV) in LNCS. Berlin: Springer-Verlag, 1998: 541–543.
BAILEY D V, BALDWIN B, BATINA L, et al. The Certicom challenges ECC2-X [C]//Workshop on Special Purpose Hardware for Attacking Cryptographic Systems. [s.l.]: SHARCS, 2009: 1–32.
BAILEY D V, BATINA L, BERNSTEIN D J, et al. Breaking ECC2K-130 [EB/OL]. (2017-07-29). https://eprint.iacr.org/2009/541.
BAI S, BRENT R P. On the efficiency of Pollards Rho method for discrete logarithms [C]//Fourteenth Computing: The Australasian Theory Symposium (CATS2008). Wollongong: Australian Computer Society Inc., 2008: 125–131.
JOUX A, LERCIER R, SMART N, et al. The number field sieve in the medium prime case [C]//Advances in Cryptology (CRYPTO 2006). Berlin: Springer-Verlag, 2006: 326–344.
ZAJAC P. Remarks on the NFS complexity [EB/OL]. (2017-07-29). http://eprint.iacr.org/.
BERNSTEIN D J. Predicting NFS time [R]. Nancy: Cado Workshop on Integer Factorization, 2008.
GÖLOĞLU F, GRANGER R, MCGUIRE G, et al. On the function field sieve and the impact of higher splitting probabilities: Application to discrete logarithms in \({F_{{2^{1971}}}}\) and \({F_{{2^{3164}}}}\) [C]//Advances in Cryptology (CRYPTO 2013). Berlin: Springer-Verlag, 2013: 109–128.
GÖLOĞLU F, GRANGER R, MCGUIRE G, et al. Solving a 6120-bit dlp on a desktop computer [C]//Selected Areas in Cryptography (SAC 2013). Berlin: Springer-Verlag, 2013: 136–152.
JOUX A. Faster index calculus for the medium prime case: Application to 1 175-bit and 1 425-bit finite fields [C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer-Verlag, 2013: 177–193.
HILDEBRAND A, TENENBAUM G. Integers without large prime factors [J]. Journal de Théorie des Nombres de Bordeaux, 1993, 5(2): 411–484.
BERNSTEIN D J. Arbitrarily tight bounds on the distribution of smooth integers [J]. Number Theory for the Millennium, 2002, 1: 49–66.
KRAUSE U. Abschätzungen für die function ψ k(x, y) in algebraischen Zahlkörpern [J]. Manuscripta Mathematica, 1990, 69: 319–331.
CANFIELD E R, ERDÖS P, POMERANCE C. On a problem of Oppenheim concerning “factorisatio numerorum” [J]. Journal of Number Theory, 1983, 17: 1–28.
LENSTRA A K, VERHEUL E R. Selecting cryptographic key sizes [C]//International Workshop on Public Key Cryptography. London: Springer-Verlag, 2000: 446–465.
LENSTRA A K. Unbelievable security: Matching AES security using public key systems [C]//International Conference on the Theory and Application of Cryptology and Information Security. London: Springer-Verlag, 2001: 67–86.
SMART N. ECRYPT II yearly report on algorithms and keysizes (2011-2012) [R]. Kortrijk: University of Leuven, 2012.
KOBLITZ N, MENEZES A. Pairing-based cryptography at high security levels [C]//IMA International Conference on Cryptography and Coding. Berlin: Springer-Verlag, 2005: 13–36.
BENGER N, SCOTT M. Constructing tower extensions for the implementation of pairing-based cryptography [C]//Arithmetic of Finite Fields, Third International Workshop (WAIFI 2010). Istanbul: Springer, 2010: 180–195.
The R Core Team. R: A language and environment for statistical computing [M]. Vienna: The R Core Team, 2010.
BOX G E P, COX D R. An analysis of transformations [J].Journal of the Royal Statistical Society, 1964, 26: 211–252.
BERNSTEIN D J. Implementation of ψ estimation method of “arbitrarily tight bounds on the distribution of smooth integers” [EB/OL]. (2017-07-29). https://cr.yp.to/psibound.html.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Benger, N., Charlemagne, M. & Chen, K. A Note on the Behaviour of the Number Field Sieve in the Medium Prime Case: Smoothness of Norms. J. Shanghai Jiaotong Univ. (Sci.) 23, 138–145 (2018). https://doi.org/10.1007/s12204-018-1919-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12204-018-1919-8