Lenstra Elliptic Curve Factorization - The Algorithm With Projective Coordinates

The Algorithm With Projective Coordinates

Before we consider the projective plane over /~, first have a look at the 'normal' projective space over . Now, instead of studying the points, the lines through the origin will be studied. The line can be represented a non-zero point if you use the equivalence relation ~ on it, given by: if and only if there exists a non-zero number such that, and . Due to this equivalence relation the space will be called a plane. In the projective plane, points, denoted by, are 'the same' as lines in a threedimensional space that go through the origin. Remark that the point does not exist here, because these does not represent a line. Now we observe that almost all lines go to the -plane, except from the lines parallel to this plane. This lines are in the projective plane the 'points of infinity' that are used in the affine -plane above.

In the algorithm only the group structure of an elliptic curve over the field is used. Therefore we not necessarily need the field . A finite field will also provide a group structure on the elliptic curve. However, considering the same curve and operation over /~ with not a prime does not give a group. The Elliptic Curve Method makes use of the failure cases of the addition law.

We now state the algorithm in projective coordinates. The neutral element is then given by the point in infinity . Let be a (positive) integer and consider the elliptic curve (a set of points with some structure on it) .

1. Pick in and let be unequal to zero.
2. Calculate . The elliptic curve is then in Weierstrass form given by and by using projective coordinates the elliptic curve is given by the homogenous equation . It has the point .
3. Choose an upperbound for this elliptic curve. Remark: You will only find factors if the group order of the elliptic curve over (denoted by #) is B-smooth, which means that all prime factors of # have to be less or equal to .
4. Calculate .
5. Calculate (k times) in the ring . Note that if # is -smooth and is prime (and therefore is a field) that . However, if only # is B-smooth for some divisor of, the product might not be (0:1:0) because addition and multiplication are not well-defined if is not prime. In this case, a non-trivial divisor can be found!
6. If not, then go back to step 2. If this does occur, then you will notice this when simplifying the product .

In point 5 it is said that under the right circumstances a non-trivial divisor can be found. As pointed out in Lenstra's article (Factoring Integers with Elliptic Curves) the addition needs the assumption . If are not and distinct (otherwise addition works similar, but a little different), then addition works as follows:

• To calculate:, ,
• ,
• ,
• ,
• .

If addition fails, this will be due calculating fails. In particular, because can not always be calculated if is not prime (and therefore is not a field). Without making use of being a field, one could calculate:

• ,
• ,
• ,
• , and simplify if possible.

This calculation is always legal and if the gcd of the -coordinate with is unequal to 1 or, so when simplifying fails, then a non-trivial divisor of is found.