4
$\begingroup$

I came across Lenstra ECM algorithm and I wonder why it works. Please refer for simplicity to Wikipedia section Why does the algorithm work

I NOT a math expert but I understood first part well enough (I suppose), what I miss is

When this is the case, $kP$ does not exist on the original curve, and in the computations we found some $v$ with either $\text{gcd}(v,p)=p$ or $\text{gcd}(v,q)=q$, but not both. That is, $\text{gcd}(v,n)$ gave a non-trivial factor of $n$.

As far as I know this has to do with the fact that $E(\mathbb Z/n\mathbb Z)$ is not a group if $n$ is not prime so some element (i.e. $x_1-x_2$) is not invertible but what is the link between non invertible elements and $n$ factors?

Thanks to everyone

  • 0
    I'm fond of David Bressoud's book, **Factorization and Primality Testing**. If you are interested in arithmetic of elliptic curves, then another favorite is Silverman and Tate's **Rational Points on Elliptic Curves**. You can look for reviews, etc. in Google Books or at bookseller websites.2012-12-07

1 Answers 1

0

Read this paper.

enter image description here

this is just a piece of hole paper.