Comparative Efficiency of Algorithms for Solving the Elliptic Curve Discrete Log Problem: A Case Study of Brute Force, Pollard’s Rho, and Shank’s Baby-Step Giant-Step

Elliptic curves have many applications in public-key cryptography and are used in various real-world scenarios. The security of these cryptosystems depends on the elliptic curve discrete log problem. While there are papers that test these algorithms in practical settings, there is a lack of comparisons between them on the same system. In this article, we compare the time required by three methods to solve this problem: Brute Force, Pollard’s Rho, and Shank’ Baby-Step-Giant-Step (BSGS) for an elliptic curve E over F p of order approximately 2 19 . We then extrapolate the results to estimate the time needed to solve this problem for an elliptic curve E ' over F p of order approximately 2 160 . Our findings indicate that, as expected, the Brute Force method resulted in the slowest solving time. On the curve of order approximately 2 19 , Shanks’ BSGS method yielded the fastest solving time. However, when the results were extrapolated for the higher-order curve of approximately 2 160 , Pollard’s Rho method proved to be the most efficient.