Improvements to the Descent Step in the Number Field Sieve for Discrete Logarithms
- Resource Type
- Conference
- Authors
- Liu, Liwei; Xu, Maozhi
- Source
- 2020 International Conference on Computer, Information and Telecommunication Systems (CITS) Computer, Information and Telecommunication Systems (CITS), 2020 International Conference on. :1-6 Oct, 2020
- Subject
- Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
General Topics for Engineers
Robotics and Control Systems
Signal Processing and Analysis
Lattices
Two dimensional displays
Complexity theory
Generators
Tools
Testing
Smoothing methods
cryptography
discrete logarithm problem
number field sieve
descent
- Language
The discrete logarithm problem (DLP) is a cornerstone in the public-key cryptography with various applications. Recently there is a new computational record for the DLP in a 795-bit prime field using the number field sieve for discrete logarithms (NFS-DL). The main technique used in the computation is choosing good parameters for each step of NFS-DL which reduces the time estimated by the asymptotic complexity significantly. In this article, we propose a new algorithm to find relations for high degree prime ideals and remove the previous restriction that only degree one prime ideals are allowed to appear in the descent step. This will increase the success probability of the descent step and reduce the actual running time. As the descent step could be done separately in some sense, improving the descent step is beneficial to find optimal parameters such as the smoothness bound which may result in better performance of the NFS-DL algorithm. We also give an experiment to demonstrate the effectiveness of our algorithm.