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
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!