Editing Lenstra elliptic-curve factorization (section)

==Twisted Edwards curves==

{{Main | Twisted Edwards curve}}
The use of [[Edwards curve]]s needs fewer modular multiplications and less time than the use of [[Montgomery curve]]s or [[Weierstrass's elliptic functions|Weierstrass curves]] (other used methods). Using Edwards curves you can also find more primes.

'''Definition.''' Let <math>k</math> be a field in which <math>2 \neq 0</math>, and let <math>a,d \in k\setminus\{0\}</math> with <math>a\neq d</math>. Then the twisted Edwards curve <math>E_{E,a,d}</math> is given by <math>ax^2+y^2=1+dx^2y^2.</math> An Edwards curve is a twisted Edwards curve in which <math>a=1</math>.

There are five known ways to build a set of points on an Edwards curve: the set of affine points, the set of projective points, the set of inverted points, the set of extended points and the set of completed points.

The set of affine points is given by:

:<math>\{(x,y)\in \mathbb{A}^2 : ax^2+y^2=1+dx^2y^2\}</math>.

The addition law is given by

:<math>(e,f),(g,h) \mapsto \left(\frac{eh+fg}{1+ degfh},\frac{fh-aeg}{1-degfh}\right).</math>

The point (0,1) is its neutral element and the inverse of <math>(e,f)</math> is <math>(-e,f)</math>.

The other representations are defined similar to how the projective Weierstrass curve follows from the affine.

Any [[elliptic curve]] in Edwards form has a point of order 4. So the [[torsion group]] of an Edwards curve over <math>\Q</math> is isomorphic to either <math>\Z/4\Z, \Z/8\Z, \Z/12\Z,\Z/2\Z \times \Z/4\Z</math> or <math>\Z/2\Z\times \Z/8\Z</math>.

The most interesting cases for ECM are <math>\Z/12\Z</math> and <math>\Z/2\Z\times \Z/8\Z</math>, since they force the group orders of the curve modulo primes to be divisible by 12 and 16 respectively. The following curves have a torsion group isomorphic to <math>\Z/12\Z</math>:

* <math>x^2+y^2=1+dx^2y^2</math> with point <math>(a,b) </math> where <math>b \notin\{-2,-1/2,0,\pm1\}, a^2=-(b^2+2b) </math> and <math>d=-(2b+1)/(a^2b^2) </math>
* <math>x^2+y^2=1+dx^2y^2</math> with point <math>(a,b) </math> where <math>a=\frac{u^2-1}{u^2+1}, b=-\frac{(u-1)^2}{u^2+1}</math> and <math>d=\frac{(u^2+1)^3(u^2-4u+1)}{(u-1)^6(u+1)^2}, u\notin\{0,\pm1\}.</math>

Every Edwards curve with a point of order 3 can be written in the ways shown above. Curves with torsion group isomorphic to <math>\Z/2\Z\times \Z/8\Z</math> and <math>\Z/2\Z\times \Z/4\Z</math> may be more efficient at finding primes.<ref name=Bernstein2008>{{cite web|last1=Berstein|first1=Daniel J.|last2=Birkner|first2=Peter|last3=Lange|first3=Tanja|author3-link=Tanja Lange|last4=Peters|first4=Christiane|title=ECM Using Edwards Curves|url=https://eprint.iacr.org/2008/016.pdf|website=Cryptology ePrint Archive|date=January 9, 2008}} (see top of page 30 for examples of such curves)</ref>