Content deleted Content added
→External links: Fixed link |
|||
Line 15:
# Compute <math>[k]P</math> on the elliptic curve (<math>\bmod n</math>), where <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|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. <math>B</math> is picked to be small enough so that <math>B</math>-wise point addition can be performed in reasonable time.
#*If we finish all the calculations above without encountering non-invertible elements (<math>\bmod n</math>), it means that the elliptic curves' (modulo primes) order is not [[Smooth number|smooth]] enough, so we need to try again with a different curve and starting point.
#*If we encounter a <math>\gcd(v,n) \neq 1,
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]].
| |||