Improving the parallelized Pollard lambda search on anomalous binary curves

Abstract:

The best algorithm known for finding logarithms on an elliptic curve $(E)$ is the (parallelized) Pollard lambda collision search. We show how to apply a Pollard lambda search on a set of equivalence classes derived from $E$, which requires fewer iterations than the standard approach. In the case of anomalous binary curves over $F_{2^m}$, the new approach speeds up the standard algorithm by a factor of $\sqrt {2m}$.