Quadratic sieve
Criba cuadrática
- Date
- 1981 · confidence high
- Place
- Athens, Georgia, United States
- Credited to
- Carl Pomerance
- Field
- Knowledge & symbols
What it is
Integer factorization algorithm using sieved square congruences, faster than classical methods for numbers up to about 100 digits; an improvement on Schroeppel's linear sieve.
What it led to
- cryptanalysis of RSA with moderate key sizes
- general number field sieve algorithm
- applied computational number theory
- modern factorization libraries