Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.