D. H. Lehmer y R. E. Powers sugirieron una idea parecida en un artículo publicado en 1931,[3] utilizando fracciones continuas.
John Brillhart y Michael Morrison en 1975[4] muestran cómo mejorar el algoritmo utilizando el álgebra lineal sobre
John D. Dixon muestra la eficiencia del algoritmo en un artículo publicado en 1981.
[5] El algoritmo de criba cuadrática, debido a Carl Pomerance,[6] utiliza ideas similares a las de este método.
es compuesto y no es la potencia de un primo, la ecuación
como producto de dos enteros coprimos entre sí.
(esto se puede hacer gracias al Teorema chino del resto) encontramos una solución a
La idea básica del algoritmo es intentar encontrar dos enteros
m c d ( x − a , n )
Buscar al azar estos enteros lleva mucho tiempo y no hace eficaz el método.
Lo que se hace para tener más probabilidad de "colisión" es tomar enteros cuyos cuadrados tengan factores primos pequeños.
Más concretamente: tomamos una "base de factores"
formada por enteros pequeños y buscamos
al cuadrado no es otra cosa que obtener una combinación lineal de las k-uplas que sea la nula módulo 2.
O sea que es un problema de álgebra lineal en
, que puede resolverse en forma rápida.
el entero compuesto que deseamos factorizar.
al conjunto de los primos menores o iguales que
Supongamos que hemos encontrado suficientes de estos números (suficientes en general significa poco más que el cardinal de
Utilizamos el álgebra lineal (como se describe en la sección anterior) para encontrar un producto
Encontramos varios enteros cuyos cuadrados son factorizados (módulo
Al tener 5 4-uplas, debe haber una que sea combinación de las otras (módulo 2); o lo que es lo mismo, una suma de estas 4-uplas tendrá todas sus entradas pares.
Esto quiere decir que al multiplicar los primeros cuatro números, su cuadrado será
Esta combinación hallada no nos da ningún factor, ya que
Buscamos otra suma que nos dé con entradas pares: las tres últimas.
pequeño entonces es fácil saber si un entero se factoriza sobre
pero complicado saber si un entero se factoriza sobre
La clave para optimizar este método es escoger el valor adecuado de
Esto hace que el tiempo de ejecución del algoritmo tenga un orden
, pero Schnorr y Knuth lograron mejorar la prueba, asegurando que