کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4639628 | 1341242 | 2012 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Improved Pollard rho method for computing discrete logarithms over finite extension fields Improved Pollard rho method for computing discrete logarithms over finite extension fields](/preview/png/4639628.png)
It is clear that the distinctive feature of the normal basis representations, namely, the pp-th power of an element is just the cyclic shift of its normal basis representation where pp is the characteristic of the underlying field, can be used to speed up the computation of discrete logarithms over finite extension fields FpmFpm. We propose a variant of the Pollard rho method to take advantage of this feature, and achieve the speedup by a factor of m, rather than 3p−34p−3m, 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.
Journal: Journal of Computational and Applied Mathematics - Volume 236, Issue 17, November 2012, Pages 4336–4343