In this presentation I will outline two projects which I have been working on during my PhD. Both projects are related to the elliptic curve discrete logarithm problem (ECDLP): the theoretical foundation of many modern cryptosystems.First I will outline how we have set a new record by solving the ECDLP over a 112-bit prime field using a cluster of PlayStation 3 game consoles in 2009.Next, the negation map optimization is discussed: this is an technique to speed up the Pollard rho method when solving the ECDLP. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. I will present that previously published approaches to deal with this problem are plagued by recurring cycles: effective alternative countermeasures are proposed.