1
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Peter
    Commented Oct 4, 2020 at 18:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Oct 4, 2020 at 18:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Oct 4, 2020 at 18:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Oct 4, 2020 at 18:09

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .