Content deleted Content added
Correct spelling of Paul ZImmermann's name. |
Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
Line 23:
If ''p'' and ''q'' are two prime divisors of ''n'', then {{math|1=''y''<sup>2</sup> = ''x''<sup>3</sup> +}} {{math|1=''ax'' + ''b'' (mod ''n'')}} implies the same equation also {{math|1=modulo ''p''}} and {{math|1=modulo ''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'' > 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'' + 1}} and {{math|1=''q'' + 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 ∞ {{math|1=modulo ''p''}} but not {{math|1=modulo ''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'') = ''p''}} or {{math|1=gcd(''v'', ''q'') = ''q'',}} but not both. That is, {{math|1=gcd(''v'', ''n'')}} gave a non-trivial factor {{math|1=of ''n''.}}
ECM is at its core an improvement of the older [[Pollard's p − 1 algorithm|{{math|1=''p'' − 1}} algorithm]]. The {{math|1=''p'' − 1}} algorithm finds prime factors ''p'' such that {{math|1=''p'' − 1}} is [[smooth number|b-powersmooth]] for small values of ''b''. For any ''e'', a multiple of {{math|1=''p'' − 1,}} and any ''a'' [[relatively prime]] to ''p'', by [[Fermat's little theorem]] we have {{math|1=''a''<sup>''e''</sup> ≡ 1 ([[modular arithmetic|mod]] ''p'')}}. Then {{math|1=[[greatest common divisor|gcd]](''a''<sup>''e''</sup> − 1, ''n'')}} is likely to produce a factor of ''n''. However, the algorithm fails when {{math|1=''p''
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 {{math|1=''p'' − 1.}}
| |||