Speeding up elliptic curve discrete logarithm computations with point halving

被引：5

作者：

Zhang, Fangguo ^{[1
]}

Wang, Ping ^{[1
]}

机构：

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

来源：

DESIGNS CODES AND CRYPTOGRAPHY | 2013年 / 67卷 / 02期

基金：

中国国家自然科学基金;

关键词：

Pollard rho method; Elliptic curve discrete logarithm; Point halving; Random walk; CRYPTOSYSTEMS; FACTORIZATION; POLLARD; SEARCH;

D O I：

10.1007/s10623-011-9599-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Pollard rho method and its parallelized variants are at present known as the best generic algorithms for computing elliptic curve discrete logarithms. We propose new iteration function for the rho method by exploiting the fact that point halving is more efficient than point addition for elliptic curves over binary fields. We present a careful analysis of the alternative rho method with new iteration function. Compared to the previous r-adding walk, generally the new method can achieve a significant speedup for computing elliptic curve discrete logarithms over binary fields. For instance, for certain NIST-recommended curves over binary fields, the new method is about 12-17% faster than the previous best methods.

引用

页码：197 / 208

页数：12