Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 5 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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