Recently a few papers have appeared that describe a new approach to factoring, using elliptic curves over $\mathbb{Q}$. See, e.g.,

However, these papers don't seem to describe the complexity of these novel methods. What is the running time of these methods? Are these methods faster than the standard known algorithms for factoring? What is the impact of these new ideas on the security of RSA and other factoring-based cryptosystems? Should we be concerned?


1 Answer 1


I don't think there's anything to worry about here. Remarks 4.2 and 4.3 in the second paper point out that these approaches need to first find a point on a curve with a very large conductor/discriminant, and that seems to be very hard. (Harder than factoring the integer using NFS.)

There are many ways to compute factorings and discrete logarithms where you first do some very hard number theoretic computations (e.g. related to an elliptic curve over the rationals), then easily factor or compute a d.log. I designed such an algorithm myself once, and it was utterly useless.


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.