Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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) – user5572685 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

Read this paper.

enter image description here

this is just a piece of hole paper.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.