6
$\begingroup$

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:

enter image description here

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

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 7 '14 at 15:16
  • 3
    $\begingroup$ 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 (?). $\endgroup$ – Jyrki Lahtonen Jul 7 '14 at 15:21
  • $\begingroup$ what means 'bad reduction'? and $n$ is required to be a composite integer, no? $\endgroup$ – Luca Jul 7 '14 at 15:36
  • 2
    $\begingroup$ 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. $\endgroup$ – sdf Jul 8 '14 at 1:16
  • 1
    $\begingroup$ 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. $\endgroup$ – TonyK Jul 14 '14 at 19:55
2
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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