A variant of Pollard's Rho method for the ECDLP over a field of characteristic two

Abstract

The security of the elliptic curve cryptography (ECC) depends on the inability to compute the multiplicand given the original and product points. The problem to find this multiplicand is called the elliptic curve discrete logarithm problem (ECDLP). The baby-step giant-step algorithm is a generic algorithm that can be applied for ECDLPs. The running time of this algorithm and the space complexity are, where  is group order. This paper shows how to apply Pollard's Rho Method to solve the same ECDLPs which has about the same running time as the baby-step giant-step algorithm, but only a small memory requirement.