# Lenstra's Elliptic Curve Algorithm

I am currently trying to understand Lenstra's Elliptic Curve Algorithm for factoring integers. As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate.

They describe the algorithm as follows:

I have some questions about some of the steps:

To Step 1): Why must the $gcd(n,6)$ be $1$? And why shouldn't $n$ be of the form $m^r$?

To Step 4): Why must $gcd(4b^3 + 27c^2, n)=1$ hold? I found a sentence in Lenstra's paper (H.W.Lenstra Jr. 'Facoting Integers with Elliptic Curves'), but I don't see why it is true:

"if $6(4a^3+27b^2)\in (\mathbb{Z}/n\mathbb{Z})^*$ then $E$ is called an elliptic curve over $\mathbb{Z}/n\mathbb{Z}$ and in this case $E(\mathbb{Z}/n\mathbb{Z})$ has a natural abelian group law"

To Step 6): Why is the point $kP$ of the form $(\frac{a_k}{d_k^2}, \frac{b_k}{d_k^3})$? I saw a Lemma that said:

"$P=(x,y)\in E(\mathbb{Q})$ then $\exists e\in\mathbb{N}$, $m,l\in\mathbb{Z}$ with $gcd(e,l)=gcd(e,m)=1$ and $x=(\frac{m}{e^2})$, $y=(\frac{l}{e^3})$."

But here we have no information about $a_k, b_k$ and $d_k$ do we?

I would be really happy if someone could help me understand this algorithm.
All the best, Luca

• If $n$ has a common factor with $6$, then you found a factor :-) I think the technical reason is that in characteristics two or three the elliptic curves cannot be brought into the familiar form $y^2=x^3+bx+c$. The transformations that bring a general EC to this form require division by two and three. – Jyrki Lahtonen Jul 7 '14 at 15:16
• If $\gcd(4b^3+27c^2,n)>1$ then the elliptic curve has bad reduction modulo $n$ (if $n$ were a prime). IIRC most of the theoretical justification for the rest of the algorithm then breaks down: the group law (?), facts about the order of the group (?). – Jyrki Lahtonen Jul 7 '14 at 15:21
• what means 'bad reduction'? and $n$ is required to be a composite integer, no? – Luca Jul 7 '14 at 15:36
• Bad reduction means that the reduced curve is singular. Strictly speaking one needs to make sure about a minimal model and all that. All this stuff would appear in most books on elliptic curves e.g. Cassels, Silverman's arithmetic etc. – sdf Jul 8 '14 at 1:16
• If you actually want to implement this algorithm then you absolutely must obtain Prime Numbers: A Computational Perspective, by Richard Crandall and Carl Pomerance. Come to think of it, you should obtain it anyway if you are interested in such matters. – TonyK Jul 14 '14 at 19:55

I am going try to answer this myself as far as I understood what happens in the algorithm.

Step 1: Here we must have that $gcd(n,6)$ is $1$ so that we can work with the Weierstraß normal form which only works in characteristic not equal to $2$ or $3$. I think the reason for $n$ not of the form $m^r$ is efficiency. The test of taking the square-root or $n^\frac{1}{r}$ is faster than going through the whole algorithm.

Step 4: Here we need $gcd(4b^3+27c^2,n)$ to be 1 so that $n$ and the discriminant of the curve have no common factors. Then, by reducing the curve modulo $p$, if we find such, we will have a non-singular curve.

Step 6: We calculate $kP$ in $\mathbb{Z}/n\mathbb{Z}$ (how we do that is explained later and includes some cases, since we must see that we can calculate the $\lambda$ in the formula of adding points, as the denominator might not have an inverse in $\mathbb{Z}/n\mathbb{Z}$). So the coordinates of $kP$ are rational numbers. And there we have a Lemma in Silverman:
If $P=(X,Y)\in E(\mathbb{Q})$ then $\exists e\in\mathbb{N}$ and $m,n\in\mathbb{Z}$ with $gcd(e,n)=gcd(e,m)=1$ and $X=\frac{m}{e^2}$ and $Y=\frac{m}{e^3}$.
So we can write $kP$ in this form. We do this to see in Step 7 if we found our non-trivial factor of n, or if we need to start over.
Note, we want $kP$ to be the point at infinity. If our chosen point $P=(x_1,y_1)$ has infinite order, and we get $kP$ is this point at infinity, then there must be a prime-factor $p$ of $n$, such that $E(\mathbb{F}_p)$ divides k. Then the points of $E(\mathbb{F}_p)$ have order dividing $k$. And hence, if $kP$ is the point at infinity then $p$ divides the denominator of the coordinates of $kP$, hence $d_k$.

I hope this was not too chaotically written down and might help someone else.
If there are faults in my explanation, please write a comment!