| 摘要: |
| Pollard kangaroo算法是解决区间N上离散对数问题很有效的方法，在平均意义下需要进行2 √N次群操作.而Galbraith 和Ruprai对容易进行求逆运算的群，利用等价类的方法，将平均意义下需要的群操作次数降低到了1.36 √N.在Galbraith和Ruprai的基础上，对算法进行了优化，调整了家袋鼠和野袋鼠的活动区间，将区间分别变为了原来的0.8581倍，从而将平均意义下需要的群操作次数降低到了1.338√N. |
| 关键词: 离散对数问题 椭圆曲线 袋鼠算法 逆映射 等价类 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金（61272499，10990011）；信息保障技术重点实验室（KJ-11-02） |
|
| Improvements on the Discrete Logarithm Algorithm with Equivalence Classes |
|
ZHANG Guo-Liang1, HU Zhi2, XU Mao-Zhi1
|
|
1.LMAM, School of Mathematical Sciences, Peking University, Beijing 100871, China;2.Beijing International Center for Mathematical Research, Peking University, Beijing 100871, China
|
| Abstract: |
| The pollard kangaroo method is a very effective way to solve the discrete logarithm problem in an interval of size N, which needs approximately 2 √N group operations under heuristic average case. For those fast inversion groups, Galbraith and Ruprai use equivalence classes method to lower the times of group operations which are needed under heuristic average case to approximately 1.36 √N.Based on Galbraith and Ruprai, this paper optimizes the method and adjusts the active interval of the tame kangaroos and wild kangaroos, in a way of changing each of their intervals to approximately 0.8581 times the original one, so that the group operations under heuristic average case is lowered to approximately 1.338√N. |
| Key words: discrete logarithm problem elliptic curves pollard kangaroo method inverse map equivalence class |
