|
Practically speaking, ECM is considered a special-purpose factoring algorithm, as it is most suitable for finding small factors. {{As of|2006|alt=Currently}}, it is still the best algorithm for [[divisor]]s not exceeding 50 to 60 [[decimal|digits]], as its running time is dominated by the size of the smallest factor ''p'' rather than by the size of the number ''n'' to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general-purpose techniques. The largest factor found using ECM so far has 83 decimal digits and was discovered on 7 September 2013 by R. Propper.<ref>[http://www.loria.fr/~zimmerma/records/top50.html 50 largest factors found by ECM].</ref> Increasing the number of curves tested improves the chances of finding a factor, but they are not [[linear]] with the increase in the number of digits.
==Algorithm==
==Lenstra's elliptic-curve factorization==
The Lenstra elliptic-curve factorization method to find a factor of thea given natural number {{mvar|<math>n}}</math> works as follows:
# Pick a random [[elliptic curve]] over <math>\mathbb{Z}/n\mathbb{Z}</math>, with equation of the form <math>y^2 = x^3 + ax + b \pmod n</math> together with a non-trivial [[Point (geometry)|point]] <math>P(x_0,y_0)</math> on it.
#:This can be done by first picking random <math>x_0,y_0,a \in \mathbb{Z}/n\mathbb{Z}</math>, and then calculatingsetting <math>b = y_0^2 - x_0^3 - ax_0\pmod n</math> to assure the point is on the curve.
# "Addition"One ofcan define ''PAddition'' andof ''Q'' astwo points in general defines a group operation {{math|1=''P'' ⊕ ''Q''}} on the curve, whoseto productdefine cana [[Group (Mathematics)|Group]]. beThe computedaddition fromlaws formulasare given in the [[elliptic curve#The group law|article on elliptic curves]].
#:Using this assumption, weWe can form repeated multiples of a point ''<math>P''</math>: {{<math|1>[k]P =''kP'' = '' P'' ⊕ ... ⊕ '' + \ldots + P'' \text{(''k'' times)}}</math>. The addition formulasformulae involve the taking the modular slope of a chord joining ''<math>P''</math> and ''<math>Q''</math>, and thus division between residue classes modulo ''<math>n''</math>, performed using the [[extended Euclidean algorithm]]. In particular, division by some {{<math|1=''>v'' (mod '' \bmod n'')}}</math> includes calculation of the {{<math|1=[[greatest common divisor|>\gcd]](''v'', ''n'')}}</math>.
#: IfAssuming thewe calculate a slope is of the form ''<math>u''/''v''</math> with {{<math|1=>\gcd(''u'', ''n''v) = 1}}</math>, then {{if <math|1=''>v'' = 0 (mod ''n'')}} means\bmod thatn</math>, the result of the ⊕-point addition will be ∞<math>\infty</math>, the point "at infinity" corresponding to the intersection of the "vertical" line joining ''<math>P'' {{math|1=(''x'', ''y'')}}, {{math|1=''P''{{'}}(''x'', −''-y'')}}</math> and the curve. However, if {{<math|1=>\gcd(''v'', ''n'')}} is neither\neq 1, nor ''n''</math>, then the ⊕-point addition will not produce a meaningful point on the curve, which shows that our elliptic curve is not a group {{math|1=(mod ''n'')}}, but, more importantly for now, {{<math|1=>\gcd(''v'', ''n'')}}</math> is a non-trivial factor of ''<math>n''</math>.
# Compute ''eP''<math>[k]P</math> on the elliptic curve (mod<math>\bmod ''n''</math>), where ''e''<math>k</math> is a product of many small numbers: say, a product of small primes raised to small powers, as in the [[Pollard's p − 1 algorithm|{{math|1=''p'' − -1}} algorithm]], or the [[factorial]] <math>B!</math> for some not too large ''<math>B''</math>. This can be done efficiently, one small factor at a time. Say, to get ''<math>[B''!'']P''</math>, first compute <math>[2'']P''</math>, then <math>[3]([2'']P'')</math>, then <math>[4]([3!'']P'')</math>, and so on. Of<math>B</math> course,is ''B''picked shouldto be small enough so that ''<math>B''</math>-wise ⊕-point addition can be performed in reasonable time.
#*If we were able to finish all the calculations above without encountering non-invertible elements {{math|1=(mod ''<math>\bmod n</math>), it means that the elliptic curves'' (modulo primes)}} order is not [[Smooth number|smooth]] enough, thenso we need to try again with somea otherdifferent curve and starting point.
#*If we encounteredencounter a {{<math |1=>\gcd( ''v '', ''n '') }} at some stage that was neither\neq 1 nor ''n'', thenm</math> we are done: it is a non-trivial factor {{of <math |1=of ''>n ''}}</math>. ▼#*If at some stage we found {{math|1=''kP'' = ∞}} (''infinity'' on the elliptic curve), we should start over with a new curve and starting point, since this point {{math|∞}} is the group identity element, so is unchanged under any further addition operations.
▲#*If we encountered a {{math|1=gcd(''v'', ''n'')}} at some stage that was neither 1 nor ''n'', then we are done: it is a non-trivial factor {{math|1=of ''n''}}.
The time complexity depends on the size of the number's smallest prime factor and can be represented by {{math|1=exp[({{sqrt|2}} + [[Big O notation#Little-o notation|o]](1)) {{sqrt|ln ''p'' ln ln ''p''}}]}}, where ''p'' is the smallest factor of ''n'', or <math>L_p\left[\frac{1}{2},\sqrt{2}\right]</math>, in [[L-notation]].
==Why does the algorithm work?==
|
