Improved Pollard rho method for computing discrete logarithms over finite extension fields

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:236

Article

Wang, Ping¹  Zhang, Fangguo¹ 

[1] Sun Yat Sen Univ, Sch Informat Sci & Technol, Guangzhou 510006, Guangdong, Peoples R China

关键词: Pollard rho method;    Normal basis representation;    Discrete logarithm;   

DOI  :  10.1016/j.cam.2012.03.019

来源: Elsevier

【 摘 要 】

It is clear that the distinctive feature of the normal basis representations, namely, the p-th power of an element is just the cyclic shift of its normal basis representation where p is the characteristic of the underlying field, can be used to speed up the computation of discrete logarithms over finite extension fields F-p(m) We propose a variant of the Pollard rho method to take advantage of this feature, and achieve the speedup by a factor of root m, rather than 3p-3/4p-3 root m, the previous result reported in the literature. Besides the theoretical analysis, we also compare the performances of the new method with the previous algorithm in experiments, and the result confirms our analysis. Due to the MOV reduction, our method can be applied to paring-based cryptosystems over binary or ternary fields. (C) 2012 Elsevier B.V. All rights reserved.

【 授权许可】

Free