Content deleted Content added
m capitalization and section names |
|||
Line 10:
# 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 setting <math>b = y_0^2 - x_0^3 - ax_0\pmod n</math> to assure the point is on the curve.
# One can define ''Addition'' of two points on the curve, to define a [[Group (
#:We can form repeated multiples of a point <math>P</math>: <math>[k]P = P + \ldots + P \text{ (k times)}</math>. The addition formulae involve 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>v \bmod n</math> includes calculation of the <math>\gcd(v,n)</math>.
#: Assuming we calculate a slope of the form <math>u/v</math> with <math>\gcd(u,v)=1</math>, then if <math>v = 0 \bmod n</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(x,y), P'(x,-y)</math> and the curve. However, if <math>\gcd(v,n) \neq 1, n</math>, then the point addition will not produce a meaningful point on the curve; but, more importantly, <math>\gcd(v,n)</math> is a non-trivial factor of <math>n</math>.
Line 19:
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]].
==Explanation==
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''.}}
Line 29:
The order of the group of an elliptic curve over '''Z'''<sub>''p''</sub> varies (quite randomly) between {{math|1=''p'' + 1 − 2{{sqrt|''p''}}}} and {{math|1=''p'' + 1 + 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.
==
The following example is from {{harvtxt|Trappe|Washington|2006}}, with some details added.
| |||