Método de factorización de Fermat

Todo número impar se puede representar de esta manera.

es el menor factor mayor o igual que la raíz cuadrada de

es el mayor factor menor o igual que

, por tanto, el número de pasos requeridos es aproximadamente: Si

tiene un factor próximo a su raíz cuadrada, el método funciona rápidamente.

, entonces el método solo necesita un paso, y esto es independiente del tamaño de

para realizar su factorización, se procede así: El tercer intento produce un cuadrado.

y subiendo desde ahí, quedan así tabulados los datos: En la práctica, se puede ignorar la última fila hasta que

, el método de Fermat ya lo habría encontrado.

; pero tras solo cuatro pasos con el método de Fermat, basta intentarlo hasta

para encontrar un factor o determinar la primalidad.

Esto sugiere la implementación de un método que combine los ya descritos.

y usar Fermat para los factores comprendidos entre

Esto deja una cota para la división por tentativa de

Siguiendo con el método de Fermat, se obtiene un rendimiento cada vez menor.

Así, normalmente uno pararía antes de llegar a este punto: No es necesario computar todas las raíces cuadradas de los

, ni siquiera todos los valores de

Por ejemplo, aquí se presenta de nuevo la tabla para

Los cuadrados son congruentes con 0, 1, 4, 5, 9 o 16 módulo 20.

produce 3, 4, 7, 8, 12 y 19 módulo 20 para estos valores.

es 1 o 9 mód 10; esto dará lugar a un Bcuad congruente con 4 mód 20, y si Bcuad es cuadrado,

Este proceso se puede realizar con cualquier módulo.

, Generalmente se toma una potencia de un primo distinto para cada módulo.

Dada una sucesión de valores de a (inicial, final y el "paso") y un módulo, se puede proceder así: Pero se puede detener la recursión cuando quedan pocos valores de a, es decir, cuando (Afin-Aini)/Apaso es pequeño.

Además, como el tamaño del paso de a' es constante, se pueden computar los sucesivos Bcuad mediante sumas.

El método de Fermat funciona de forma óptima cuando hay un factor cercano a la raíz cuadrada de n. A lo mejor se puede favorecer que así sea.

Si se conoce la razón aproximada de dos factores (

, quedando dos factores próximos que el método de Fermat, aplicado a nuv, hallará rápidamente.

, y tratar de factorizar cada nuv que surja.

El resultado final es el mismo: una diferencia de cuadrados mód n que, si no es trivial, puede emplearse para factorizar n.[2]​