Improved Algorithm for Solving Discrete Logarithm Problem by Expanding Factor  

作　　者：Bin Qi Jie Ma Kewei Lv 

机构地区：[1]State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China [2]Data Assurance Communication Security Research Center,Chinese Academy of Sciences,Beijing 100093,China [3]School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100093,China

出　　处：《China Communications》2020年第4期31-41,共11页中国通信（英文版）

基　　金：partially supported by National Key R&D Program of China(no.2017YFB0802500);The 13th Five-Year National Cryptographic Development Foundation(no.MMJJ20180208);Beijing Science and Technology Commission(no.2181100002718001);NSF(no.61272039).

摘　　要：The discrete logarithm problem(DLP)is to find a solution n such that g^n=h in a finite cyclic group G=,where h∈G.The DLP is the security foundation of many cryptosystems,such as RSA.We propose a method to improve Pollard’s kangaroo algorithm,which is the classic algorithm for solving the DLP.In the proposed algorithm,the large integer multiplications are reduced by controlling whether to perform large integer multiplication.To control the process,the tools of expanding factor and jumping distance are introduced.The expanding factor is an indicator used to measure the probability of collision.Large integer multiplication is performed if the value of the expanding factor is greater than the given bound.The improved algorithm requires an average of(1.633+o(1))q(1/2)times of the large integer multiplications.In experiments,the average large integer multiplication times is approximately(1.5+o(1))q(1/2).

关 键 词：discrete LOGARITHM ALGORITHM pollard’s KANGAROO ALGORITHM JUMPING DISTANCE 

分 类 号：TN918.1[电子电信—通信与信息系统]