If the bit size is 128 bits, I know that BSGS is not possible due to memory issues.

I know that the complexity of Pollard-rho for 128 bits is 2^64.

and I know that it is not possible to do 2 ^ 64 operations on a typical computer.

Is there any other way? do solve 128bit ECDLP when ord(G)=prime number


1 Answer 1


Yes, Pollard-rho is the best algorithm known for solving hard instances of ECDLP (those where the generator is of prime order).

The current (public) record seems to be order $2^{117.35}$ for sect113r2 by Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe and Ralf Zimmermann in Faster elliptic-curve discrete logarithms on FPGAs (eprint, 2016). Notice that this is for a curve over a binary field, and prime fields are noticeably harder at equal size (because cary-less arithmetic is cheaper).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.