Editing Lenstra elliptic-curve factorization (section)

==Explanation==

If ''p'' and ''q'' are two prime divisors of ''n'', then {{math|1=''y''<sup>2</sup>&nbsp;=&nbsp;''x''<sup>3</sup>&nbsp;+}} {{math|1=''ax''&nbsp;+&nbsp;''b''&nbsp;(mod&nbsp;''n'')}} implies the same equation also {{math|1=modulo&nbsp;''p''}} and {{math|1=modulo&nbsp;''q''.}} These two smaller elliptic curves with the <math>\boxplus</math>-addition are now genuine [[group (mathematics)|groups]]. If these groups have ''N''<sub>''p''</sub> and ''N<sub>q</sub>'' elements, respectively, then for any point ''P'' on the original curve, by [[Lagrange's theorem (group theory)|Lagrange's theorem]], {{math|1=''k''&nbsp;>&nbsp;0}} is minimal such that <math>kP=\infty</math> on the curve modulo ''p'' implies that ''k'' divides ''N''<sub>''p''</sub>; moreover, <math>N_p P=\infty</math>. The analogous statement holds for the curve modulo ''q''. When the elliptic curve is chosen randomly, then ''N''<sub>''p''</sub> and ''N''<sub>''q''</sub> are random numbers close to {{math|1=''p''&nbsp;+&nbsp;1}} and {{math|1=''q''&nbsp;+&nbsp;1,}} respectively (see below). Hence it is unlikely that most of the prime factors of ''N''<sub>''p''</sub> and ''N''<sub>''q''</sub> are the same, and it is quite likely that while computing ''eP'', we will encounter some ''kP'' that is &infin; {{math|1=modulo&nbsp;''p''}} but not {{math|1=modulo&nbsp;''q'',}} or vice versa. When this is the case, ''kP'' does not exist on the original curve, and in the computations we found some ''v'' with either {{math|1=gcd(''v'',''p'')&nbsp;=&nbsp;''p''}} or {{math|1=gcd(''v'',&nbsp;''q'')&nbsp;=&nbsp;''q'',}} but not both. That is, {{math|1=gcd(''v'',&nbsp;''n'')}} gave a non-trivial factor {{math|1=of&nbsp;''n''.}}

ECM is at its core an improvement of the older [[Pollard's p &minus; 1 algorithm|{{math|1=''p''&nbsp;&minus;&nbsp;1}} algorithm]]. The {{math|1=''p''&nbsp;&minus;&nbsp;1}} algorithm finds prime factors ''p'' such that {{math|1=''p''&nbsp;&minus;&nbsp;1}} is [[smooth number|b-powersmooth]] for small values of ''b''. For any ''e'', a multiple of {{math|1=''p''&nbsp;&minus;&nbsp;1,}} and any ''a'' [[relatively prime]] to ''p'', by [[Fermat's little theorem]] we have {{math|1=''a''<sup>''e''</sup>&nbsp;&equiv;&nbsp;1 ([[modular arithmetic|mod]] ''p'')}}. Then {{math|1=[[greatest common divisor|gcd]](''a''<sup>''e''</sup>&nbsp;&minus;&nbsp;1,&nbsp;''n'')}} is likely to produce a factor of ''n''. However, the algorithm fails when {{math|1=''p''&nbsp;−&nbsp;1}} has large prime factors, as is the case for numbers containing [[strong prime]]s, for example.

ECM gets around this obstacle by considering the [[group (mathematics)|group]] of a random [[elliptic curve]] over the [[finite field]] '''Z'''<sub>''p''</sub>, rather than considering the [[multiplicative group]] of '''Z'''<sub>''p''</sub> which always has order&nbsp;{{math|1=''p''&nbsp;&minus;&nbsp;1.}}

The order of the group of an elliptic curve over '''Z'''<sub>''p''</sub> varies (quite randomly) between {{math|1=''p''&nbsp;+&nbsp;1&nbsp;&minus;&nbsp;2{{sqrt|''p''}}}} and {{math|1=''p''&nbsp;+&nbsp;1&nbsp;+&nbsp;2{{sqrt|''p''}}}} by [[Hasse's theorem on elliptic curves|Hasse's theorem]], and is likely to be smooth for some elliptic curves.  Although there is no proof that a smooth group order will be found in the Hasse-interval, by using [[heuristic]] probabilistic methods, the [[Canfield–Erdős–Pomerance theorem]] with suitably optimized parameter choices, and the [[L-notation]], we can expect to try {{math|1='''[[L-notation|L]]'''[{{sqrt|2}}/2, {{sqrt|2}}]}} curves before getting a smooth group order. This heuristic estimate is very reliable in practice.