ON EFFICIENT DISCRETE LOGARITHM COMPUTATION ON ELLIPTIC CURVES
By
1Shalini Gupta, 2Kritika Gupta, 3Gajendra Pratap Singh and 4Kamalendra Kumar
1,2Department of Mathematics & Statistics, Himachal Pradesh University, Shimla, India-171005
3School of Computational and Integrative Sciences, Jawaharlal Nehru University, New Delhi, India-110067
4Department of Basic Science, Shri Ram Murti Smarak, College of Engineering and Technology, Bareilly, India-243202
Email: shalini.garga1970@gmail.com, kritika993@gmail.com, gajendra@gmail.jnu.ac.in, kamlendra.14kumar@gmail.com
(Received: October 10, 2023; In format: December 05, 2024; Revised: May 09, 2025; Accepted: July 14, 2025)
DOI: https://doi.org/10.58250/jnanabha_SI.2025.55103
Abstract
The proposed algorithm for computing discrete logarithms on elliptic curves involves choosing a prime with a large prime factor, an elliptic curve over the field of that prime and a random point of a certain order on the curve. The algorithm then chooses a set of primes optimized to minimize the size of a linear system and computes relations between the primes and random points on the curve using the Pollard rho algorithm. It then uses the Furer-Gathen algorithm to compute a summation polynomial for these relations and solves the linear system for the coefficients of the unknown logarithms of the prime factors of the curve's order using the conjugate gradient method and combines these logarithms to compute the discrete logarithm of any point on the curve.
2020 Mathematical Sciences Classification: 12E20, 94A60
Keywords and Phrases: Elliptic Curve; Discrete Logarithm Problem (DLP); Prime Field; Point Counting; Summation Polynoimal.