Criba cuadrática

El algoritmo de criba cuadrática (QS del inglés quadratic sieve), es un algoritmo de factorización de enteros y, en la práctica, el segundo método más rápido conocido (después de la criba general del cuerpo de números). Es todavía el más rápido para enteros que tienen 100 o menos dígitos decimales, y es considerado mucho más sencillo que la criba de cuerpos numéricos. Es un algoritmo de factorización de propósito general, lo que significa que su tiempo de ejecución únicamente depende el tamaño del entero a ser factorizado, y no sobre una estructura especial o propiedades. Fue inventado por Carl Pomerance en 1981 como una mejora a la criba lineal de Schroeppel.^[1]

Véase también

Factorización de curva elíptica de Lenstra
Test de primalidad

Referencias

↑ Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.

Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1st edición). Springer. ISBN 0-387-94777-9. Section 6.1: The quadratic sieve factorization method, pp. 227–244.