**A reduction of the space for the parallelized Pollard lambda search on elliptic curves over prime finite fields and on anomalous binary elliptic curves**

*Igor Semaev*

**Abstract: **Let $E$ be an elliptic curve defined over a prime finite field
$F_p$ by a Weierstrass equation. In this paper we introduce a new
partition of $E(F_p)$ into classes which are generally larger than
$\{\pm R\}$. We give an effective procedure to compute
representatives of such classes. So one can iterate the
pseudorandom function, related to a discrete logarithm problem in
$E(F_p)$, on the set of representatives of classes and get
probably some speed up in computing discrete logarithms. The
underlying idea how to enlarge known classes on anomalous binary
elliptic curves is given.

**Category / Keywords: **public-key cryptography / elliptic curve cryptosystem, discrete logarithms, Pollard lambda search

**Date: **received 11 Aug 2003

**Contact author: **Igor Semaev at wis kuleuven ac be

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20030811:153411 (All versions of this report)

**Short URL: **ia.cr/2003/166

[ Cryptology ePrint archive ]