On Pollard's rho method for solving the elliptic curve discrete logarithm problem

Abstract:     Cryptosystems based on elliptic curves are in wide-spread use, they are considered secure because of the difficulty to solve the elliptic curve discrete logarithm problem. Pollard's rho method is regarded as the best method for attacking the logarithm problem to date, yet it is still not efficient enough to break an elliptic curve cryptosystem. This is because its time complexity is O(√n) and for uses in cryptography the value of n will be very large. The objective of this thesis is to see if there are ways to improve Pollard's rho method. To do this, we study some modifications of the original functions used in the method. We also investigate some different functions proposed by other researchers to see if we can find a version that will improve the performance. From the experiments conducted on these modifications and functions, we can conclude that we get an improvement in the performance for some of them.