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

作者：Benger, Naomi; Charlemagne, Manuel^*; Chen, Kefei

来源：Journal of Shanghai Jiaotong University (Science), 2018, 23(1): 138-145.

DOI：10.1007/s12204-018-1919-8

• Computational mathematics
• Discrete logarithm problems
• Elliptic curve
• Number field sieve
• Polynomial selection
• Running time
• Runtimes
• Security level

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.

• 出版日期2018
• 单位杭州师范大学; University Of Michigan; The University of Michigan; 上海交通大学; university of michigan