On improvements of the r-adding walk in a finite field of characteristic 2

Abstract

It is currently known from the work of Shoup and Nechaev that a generic algorithm to solve the discrete logarithm problem in a group of prime order must have complexity at least k where N is the order of the group. In many collision search algorithms this complexity is achieved. So with generic algorithms one can only hope to make the k smaller. This k depends on the complexity of the iterative step in the generic algorithms. The comes from the fact there is about iterations before a collision. So if we can find ways that can reduce the amount of work in one iteration then that is of great interest and probably the only possible modification of a generic algorithm. The modified r-adding walk allegedly does just that. It claims to reduce the amount of work done in one iteration of the original r-adding walk. In this paper we study this modified r-adding walk, we critically analyze it and we compare it with the original r-adding walk.

Keywords:

• r-adding walk
• Discrete logarithm problem
• Generic algorithms