A Note on the Behaviour of the Number Field Sieve in the Medium Prime Case: Smoothness of Norms
Autor: | Naomi Benger, Kefei Chen, Manuel Charlemagne |
---|---|
Rok vydání: | 2018 |
Předmět: |
060201 languages & linguistics
Multidisciplinary Theoretical computer science Smoothness (probability theory) Computer science Computational mathematics 06 humanities and the arts 02 engineering and technology Prime (order theory) Running time General number field sieve Elliptic curve Discrete logarithm 0602 languages and literature 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Security level |
Zdroj: | Journal of Shanghai Jiaotong University (Science). 23:138-145 |
ISSN: | 1995-8188 1007-1172 |
DOI: | 10.1007/s12204-018-1919-8 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |