Impact of algorithms for factoring using elliptic curves over $\mathbb{Q}$

Question

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

• Factoring integers and computing elliptic curve rational points, Iftikhar A. Burhanuddin and Ming-Deh A. Huang.

• Factoring integers using elliptic curves over Q, Xiumei Li, Jinxiang Zeng, arXiv:1207.0274v2.

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?

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.