sa ›› 2018, Vol. 23 ›› Issue (1): 138-145.doi: 10.1007/s12204-018-1919-8

• • 上一篇    下一篇

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. (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)
  • 出版日期:2018-02-01 发布日期:2018-02-01
  • 通讯作者: CHARLEMAGNE Manue E-mail: charlem@sjtu.edu.cn

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. (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

摘要: 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

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.

中图分类号: