Editing Lenstra elliptic-curve factorization (section)

==The algorithm with projective coordinates==

Before considering the projective plane over <math>(\Z/n\Z)/\sim,</math> first consider a 'normal' [[projective space]] over <math>\mathbb{R}</math>: Instead of points, lines through the origin are studied. A line may be represented as a non-zero point <math>(x,y,z)</math>, under an equivalence relation ~ given by: <math>(x,y,z)\sim(x',y',z')</math> ⇔ ∃ '''''c''''' ≠ 0 such that ''x' = '''c'''x'', ''y' = '''c'''y'' and ''z' = '''c'''z''. Under this equivalence relation, the space is called '''the projective plane''' <math>\mathbb{P}^2</math>; points, denoted by <math>(x:y:z)</math>, correspond to lines in a three-dimensional space that pass through the origin. Note that the point <math>(0:0:0)</math> does not exist in this space since to draw a line in any possible direction requires at least one of x',y' or z' ≠ 0. Now observe that almost all lines go through any given reference plane - such as the (''X'',''Y'',1)-plane, whilst the lines precisely parallel to this plane, having coordinates (''X,Y'',0), specify directions uniquely, as 'points at infinity' that are used in the affine (''X,Y'')-plane it lies above.

In the algorithm, only the group structure of an elliptic curve over the field <math>\mathbb{R}</math> is used. Since we do not necessarily need the field <math>\mathbb{R}</math>, a finite field will also provide a group structure on an elliptic curve. However, considering the same curve and operation over <math>(\Z/n\Z)/\sim</math> with {{mvar|n}} 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 at infinity <math>(0:1:0)</math>. Let {{mvar|n}} be a (positive) integer and consider the elliptic curve (a set of points with some structure on it) <math>E(\Z/n\Z)=\{(x:y:z) \in \mathbb{P}^2\ |\ y^2z=x^3+axz^2+bz^3\}</math>.

# Pick <math>x_P,y_P,a \in \Z/n\Z</math> with {{mvar|a}} ≠ 0.
# Calculate <math>b = y_P^2 - x_P^3 - ax_P</math>. The elliptic curve {{mvar|E}} is then in Weierstrass form given by <math>y^2 = x^3 + ax + b</math> and by using projective coordinates the elliptic curve is given by the homogeneous equation <math>ZY^2=X^3+aZ^2X+bZ^3</math>. It has the point <math>P=(x_P:y_P:1)</math>.
# Choose an upperbound <math>B \in \Z</math> for this elliptic curve. Remark: You will only find factors {{mvar|p}} if the group order of the elliptic curve {{mvar|E}} over <math>\Z/p\Z</math> (denoted by <math>\#E(\Z/p\Z)</math>) is [[Smooth number|B-smooth]], which means that all prime factors of <math>\#E(\Z/p\Z)</math> have to be less or equal to {{mvar|B}}.
# Calculate <math>k={\rm lcm}(1,\dots ,B)</math>.
# Calculate <math>k P := P + P + \cdots + P </math> (''k'' times) in the ring <math>E(\Z/n\Z)</math>. Note that if <math>\#E(\Z/n\Z)</math> is {{mvar|B}}-smooth and {{mvar|n}} is prime (and therefore <math>\Z/n\Z</math> is a field) that <math>kP = (0:1:0)</math>. However, if only <math>\#E(\Z/p\Z)</math> is B-smooth for some divisor {{mvar|p}} of {{mvar|n}}, the product might not be (0:1:0) because addition and multiplication are not well-defined if {{mvar|n}} is not prime. In this case, a non-trivial divisor can be found.
# If not, then go back to step 2. If this does occur, then you will notice this when simplifying the product <math>kP.</math>

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 <math>\gcd(x_1-x_2,n)=1</math>. If <math>P,Q</math> are not <math>(0:1:0)</math> and distinct (otherwise addition works similarly, but is a little different), then addition works as follows:

* To calculate: <math> R = P + Q;</math> <math>P = (x_1:y_1:1), Q = (x_2:y_2:1)</math>,
* <math>\lambda =(y_1-y_2) (x_1-x_2)^{-1}</math>,
* <math> x_3 = \lambda^2 - x_1 - x_2</math>,
* <math> y_3 = \lambda(x_1-x_3) - y_1</math>,
* <math> R = P + Q = (x_3:y_3:1)</math>.

If addition fails, this will be due to a failure calculating <math>\lambda.</math> In particular, because <math>(x_1-x_2)^{-1}</math> can not always be calculated if {{mvar|n}} is not prime (and therefore <math>\Z/n\Z</math> is not a field). Without making use of <math>\Z/n\Z</math> being a field, one could calculate:

* <math>\lambda'=y_1-y_2</math>,
* <math> x_3' = {\lambda'}^2 - x_1(x_1-x_2)^2 - x_2(x_1-x_2)^2</math>,
* <math> y_3' = \lambda'(x_1(x_1-x_2)^2-x_3') - y_1(x_1-x_2)^3</math>,
* <math> R = P + Q = (x_3'(x_1-x_2):y_3':(x_1-x_2)^3)</math>, and simplify if possible.

This calculation is always legal and if the gcd of the {{mvar|Z}}-coordinate with {{mvar|n}} ≠ (1 or {{mvar|n}}), so when simplifying fails, a non-trivial divisor of {{mvar|n}} is found.