Lenstra’s Elliptic Curve Factorisation

Question

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.

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

3. 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?

Answer 1

Acutally it is all about luck if you find any factors or not. The Hasse-Theorem gives you a bound for the group order of a mod p reduced elliptic curve. Every point on the curve does have a order. Due to Lagrange of Group Theory you know that the order of the group elements have to divide the group order.

Since the Hasse Theorem just gives you an upper bound, multiple group orders are possible. If you are lucky, the points on your selected curve might form a group with a grouporder, that have many small prime factors. Becaue in this case it is possible, that any group element does have excatly this primefactor as element order.

On the other hand, if your group of points have a group order with only large primefactors, there can not be any element in the group with a small order, what means that u have to perform many multiplications before it is even possible to find a factor.

So if you exceed your limit k for multiple points on your curve, it is very likely that your group order does not have any primefactors smaller than k, so you should just get an new elliptic curve and hope that thats group order will have more small primefactors.