Lenstra elliptic-curve factorization method
E824095
The Lenstra elliptic-curve factorization method is an integer factorization algorithm that uses properties of elliptic curves over finite fields to efficiently find nontrivial factors of large numbers, especially those with relatively small prime divisors.
Statements (51)
| Predicate | Object |
|---|---|
| instanceOf |
computational number theory algorithm
ⓘ
elliptic-curve method ⓘ integer factorization algorithm ⓘ |
| alsoKnownAs |
Lenstra ECM
NERFINISHED
ⓘ
elliptic curve method (ECM) for factorization ⓘ |
| basedOn | properties of elliptic curves modulo n ⓘ |
| betterThan | Pollard p-1 method for many inputs ⓘ |
| category | public-key cryptanalysis tool ⓘ |
| comparedTo |
Pollard p-1 factorization method
NERFINISHED
ⓘ
general number field sieve NERFINISHED ⓘ quadratic sieve ⓘ |
| complexityDependsOn | size of the smallest prime factor of n ⓘ |
| coreOperation |
elliptic-curve point multiplication
ⓘ
modular arithmetic ⓘ |
| field |
computational number theory
ⓘ
cryptography ⓘ number theory ⓘ |
| goal | integer factorization ⓘ |
| hasParameter |
number of random curves to try
ⓘ
second-stage bound B2 ⓘ smoothness bound B1 ⓘ |
| hasVariant | stage-2 ECM ⓘ |
| implementedIn |
GMP-ECM
NERFINISHED
ⓘ
PARI/GP NERFINISHED ⓘ SageMath NERFINISHED ⓘ |
| influenced | elliptic curve method (ECM) implementations in cryptographic libraries ⓘ |
| input | composite integer n ⓘ |
| introducedIn | 1985 ⓘ |
| inventor | Hendrik W. Lenstra Jr. NERFINISHED ⓘ |
| namedAfter | Hendrik Willem Lenstra Jr. NERFINISHED ⓘ |
| optimizedFor | integers with relatively small prime factors ⓘ |
| output |
failure indication if no factor found in given bounds
ⓘ
nontrivial factor of n ⓘ |
| probabilistic | true ⓘ |
| publication | Factoring integers with elliptic curves NERFINISHED ⓘ |
| publishedIn | Annals of Mathematics NERFINISHED ⓘ |
| purpose | to find nontrivial factors of composite integers ⓘ |
| randomized | true ⓘ |
| relatedTo |
RSA cryptosystem security
NERFINISHED
ⓘ
elliptic-curve cryptography ⓘ |
| reliesOn | failure of modular inversion revealing a nontrivial gcd ⓘ |
| step |
choose random elliptic curve modulo n
ⓘ
choose random point on the elliptic curve modulo n ⓘ compute greatest common divisor when inversion fails ⓘ compute scalar multiples of the point ⓘ perform group operations modulo n ⓘ |
| usedFor |
factoring RSA moduli with a relatively small prime factor
ⓘ
finding medium-size prime factors in GNFS precomputation ⓘ |
| uses |
elliptic curves over finite fields
ⓘ
group law on elliptic curves ⓘ |
| yearOfPublication | 1987 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.