A Note on the Behaviour of the Number Field Sieve in the Medium Prime Case: Smoothness of Norms

doi:10.1007/s12204-018-1919-8

Journal of Shanghai Jiao Tong University (Science) ›› 2018, Vol. 23 ›› Issue (1): 138-145.doi: 10.1007/s12204-018-1919-8

Previous Articles Next Articles

A Note on the Behaviour of the Number Field Sieve in the Medium Prime Case: Smoothness of Norms

BENGER Naomi1, CHARLEMAGNE Manuel2*, CHEN Kefei3 (陈克非)

(1. School of Mathematical Sciences, University of Adelaide, Adelaide 5005, Australia; 2. University of Michigan - Shanghai Jiao Tong University Joint Institute, Shanghai Jiao Tong University, Shanghai 200240, China; 3. School of Science, Hangzhou Normal University, Hangzhou 311121, China)
(1. School of Mathematical Sciences, University of Adelaide, Adelaide 5005, Australia; 2. University of Michigan - Shanghai Jiao Tong University Joint Institute, Shanghai Jiao Tong University, Shanghai 200240, China; 3. School of Science, Hangzhou Normal University, Hangzhou 311121, China)

Online:2018-02-01 Published:2018-02-01
Contact: CHARLEMAGNE Manue E-mail: charlem@sjtu.edu.cn

Abstract

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.

Key words: number field sieve (NFS), pairing friendly elliptic curves, polynomial selection

摘要： 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.

关键词: number field sieve (NFS), pairing friendly elliptic curves, polynomial selection

CLC Number:

O 17
O 23

BENGER Naomi1, CHARLEMAGNE Manuel2*, CHEN Kefei3 (陈克非). A Note on the Behaviour of the Number Field Sieve in the Medium Prime Case: Smoothness of Norms[J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(1): 138-145.

References

[1] POLLARD J M. Monte Carlo methods for index computation(mod p) [J]. Mathematics of Computation,1978, 32: 918-924. [2] TESKE E. Speeding up Pollards Rho method forcoputing discrete logarithms [C]//Algorithmic NumberTheory Symposium (ANTS IV) in LNCS. Berlin:Springer-Verlag, 1998: 541-543. [3] BAILEY D V, BALDWIN B, BATINA L, et al. TheCerticom challenges ECC2-X [C]//Workshop on SpecialPurpose Hardware for Attacking CryptographicSystems. [s.l.]: SHARCS, 2009: 1-32. [4] BAILEY D V, BATINA L, BERNSTEIN D J,et al. Breaking ECC2K-130 [EB/OL]. (2017-07-29).https://eprint.iacr.org/2009/541. [5] BAI S, BRENT R P. On the efficiency of PollardsRho method for discrete logarithms [C]//FourteenthComputing: The Australasian Theory Symposium(CATS2008). Wollongong: Australian Computer SocietyInc., 2008: 125-131. [6] JOUX A, LERCIER R, SMART N, et al. The numberfield sieve in the medium prime case [C]//Advances inCryptology (CRYPTO 2006). Berlin: Springer-Verlag,2006: 326-344. [7] ZAJAC P. Remarks on the NFS complexity [EB/OL].(2017-07-29). http://eprint.iacr.org/. [8] BERNSTEIN D J. Predicting NFS time [R]. Nancy:Cado Workshop on Integer Factorization, 2008. [9] G¨OLOˇGLU F, GRANGER R, MCGUIRE G, et al.On the function field sieve and the impact of highersplitting probabilities: Application to discrete logarithmsin F21971 and F23164 [C]//Advances in Cryptology(CRYPTO 2013). Berlin: Springer-Verlag, 2013:109-128. [10] G¨OLOˇGLU F, GRANGER R, MCGUIRE G, etal. Solving a 6120-bit dlp on a desktop computer[C]//Selected Areas in Cryptography (SAC 2013).Berlin: Springer-Verlag, 2013: 136-152. [11] JOUX A. Faster index calculus for the medium primecase: Application to 1 175-bit and 1 425-bit finite fields[C]//Annual International Conference on the Theoryand Applications of Cryptographic Techniques. Berlin:Springer-Verlag, 2013: 177-193. [12] HILDEBRAND A, TENENBAUM G. Integers withoutlarge prime factors [J]. Journal de Th′eorie desNombres de Bordeaux, 1993, 5(2): 411-484. [13] BERNSTEIN D J. Arbitrarily tight bounds on the distributionof smooth integers [J]. Number Theory for theMillennium, 2002, 1: 49-66. [14] KRAUSE U. Absch¨atzungen f¨ur die function ψk(x, y)in algebraischen Zahlk¨orpern [J]. Manuscripta Mathematica,1990, 69: 319-331. [15] CANFIELD E R, ERD¨OS P, POMERANCE C. Ona problem of Oppenheim concerning “factorisatio numerorum”[J]. Journal of Number Theory, 1983, 17:1-28. [16] LENSTRA A K, VERHEUL E R. Selecting cryptographickey sizes [C]//International Workshop on PublicKey Cryptography. London: Springer-Verlag, 2000:446-465. [17] LENSTRA A K. Unbelievable security: Matching AESsecurity using public key systems [C]//InternationalConference on the Theory and Application of Cryptologyand Information Security. London: Springer-Verlag, 2001: 67-86. [18] SMART N. ECRYPT II yearly report on algorithmsand keysizes (2011-2012) [R]. Kortrijk: University ofLeuven, 2012. [19] KOBLITZ N, MENEZES A. Pairing-based cryptographyat high security levels [C]//IMA InternationalConference on Cryptography and Coding. Berlin:Springer-Verlag, 2005: 13-36. [20] BENGER N, SCOTT M. Constructing tower extensionsfor the implementation of pairing-based cryptography[C]//Arithmetic of Finite Fields, Third InternationalWorkshop (WAIFI 2010). Istanbul: Springer,2010: 180-195. [21] The R Core Team. R: A language and environment forstatistical computing [M]. Vienna: The R Core Team,2010. [22] BOX G E P, COX D R. An analysis of transformations[J].Journal of the Royal Statistical Society, 1964, 26:211-252. [23] BERNSTEIN D J. Implementation of ψ estimationmethod of “arbitrarily tight bounds on the distributionof smooth integers” [EB/OL]. (2017-07-29).https://cr.yp.to/psibound.html.

A Note on the Behaviour of the Number Field Sieve in the Medium Prime Case: Smoothness of Norms

A Note on the Behaviour of the Number Field Sieve in the Medium Prime Case: Smoothness of Norms

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	HOHBERGER Horst1, KLEIN Markus2. Focal Points at Infinity for Short-Range Scattering Trajectories [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(1): 146-157.
[2]	HAO Lili1,2 (郝丽丽), LI Xiaoyan1* (李晓艳), LIU Song1 (刘松), JIANG Wei1 (蒋威). Adomian’s Method Applied to Solve Ordinary and Partial Fractional Differential Equations [J]. Journal of shanghai Jiaotong University (Science), 2017, 22(3): 371-376.