# Why does Lenstra ECM work?

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

-
Have you studied or worked with some of the simpler factoring methods like Pollard's rho? It would help to have some clearer idea of your math background, e.g. understanding of elementary number theory. –  hardmath Dec 5 '12 at 17:26
Yes, I studied Pollard's Rho (with Pollard p-1 and William p+1) –  knm241 Dec 5 '12 at 18:02
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. –  hardmath Dec 7 '12 at 0:23