# Lenstra’s Elliptic Curve Factorisation

When using Lenstra’s algorithm for factorising a number with an elliptic curve, you have to choose some curve $$y^2=x^3+ax+b$$ and a non trivial point on the curve. For simplicity, I have always chosen $$a$$ and $$b$$ to be $$1$$, and the point on the curve at $$P(0,1)$$.

1. Should the values of $$a$$,$$b$$ and $$P(x,y)$$ really just be random, or do some values in particular work more efficiently, or is it dependant on the number you are trying to factorise?

After computing values of successive $$k!P$$ the multiplication starts to get very large, and so often a limit is given to k, in order to not exceed a certain run time.

1. Does this limit depend on the size of the number being factorised, or is there a go to value that is often used?

2. After reaching the limit of $$k$$ without having found any factors, what is the next step? I assumed that you would just either take another random elliptic curve or another non trivial point on the same curve and repeat the process, but will this actually lead to any factors being produced?

• Experiences indicate that it is a matter of luck which curve will work and how long it takes to get a factor. Depending on the size of a factor, we can approximately give the oprimal choice of $B1$ $B2$ can be chosen as $100\cdot B1$ , but GMP-ECM uses other, apparently better values $B2$. Commented Oct 4, 2020 at 18:01
• ECM is a probabilistic method. We have never a guarantee to eventually find a factor in a finite number ot trials. $B1$ will work (if we have the patience to run enough curves) if there is a $B1$-smooth number (one prime factor is allowed to be larger, but not larger than $B2$) in the range $[p-\sqrt{p},p+\sqrt{p}]$ , if $p$ is the factor we want to find eventually. Commented Oct 4, 2020 at 18:03
• ECM is the best method to find intermediate factors ($20$-$40$ digits) , with more effort factors upto $50$ or more digits can occasionally be found, the record is of course higher, if I remember right somewhere between $70$ and $80$ digits. Advantage : It does not matter how large the input is , but of course the curve takes more time for larger inputs. Commented Oct 4, 2020 at 18:07
• Concerning how the curves are selected , I cannot say much. I think, it is enough to vary one parameter, but I have never got into the details. Commented Oct 4, 2020 at 18:09