| dc.description.abstract | The discrete logarithm problem has been studied during the past decades for its important application in cryptography and other fields. It is very useful in the public key cryptography, which is widely used for Internet safety. Using current computers to solve general discrete logarithm problem seems still not possible within reasonable time, since no polynomial time algorithms has been found for general cases. However, over finite fields of small characteristic, the factor base discrete logarithm can be solved much faster with heuristic polynomial time algorithms.
This thesis is mainly based on the previous study of factor base discrete logarithm in Kummer extension which is published recently by Xiao-Zhuang-Cheng [14] and we focused on further calculation in this study.. The previous research calculated the determinant of the lattice to verify the hypothesis. It showed pretty good results for all q's such that log2(q2(q-1)) < 5000, and in this thesis we pushed the limit to log2(q2(q-1)) <10000. During the calculation, we tried different strategies to improve the efficiency, by transferring the matrices and splitting q's into several groups. We achieved 1000% speed-up for most q's in the range and discovered some possible structures to group q's in calculation.
In the thesis, we'll go through the basic backgrounds of the study, and then introduce the main methods and experiments done in the study. We'll discuss the grouping of q's and the efficiency improvement. In the end we'll summarize the progress and the possible future work of this study. | en_US |
