Metodo fermat

El método de factorización de Fermat se basa en la representación de un número natural impar como la diferencia de dos cuadrados:


Esa diferencia se puede factorizar algebraicamente como ; sininguno de esos factores es igual a 1, se trata de una factorización propia de n.

Todo número impar se puede representar de esta manera. En efecto, si es una factorización de n, entonces


Como nes impar, c y d también son impares, por lo que su semisuma y semidiferencia son ambos enteros. (Un múltiplo de cuatro también es una diferencia de cuadrados: en ese caso se pueden plantear c y d comonúmeros pares.)

En su forma más simple, el método de Fermat puede ser incluso más lento que el de división por tentativa en el peor de los casos. Sin embargo, la combinación de división portentativa y el método de Fermat es más efectivo que el uso exclusivo de uno de ellos.
.Si n tiene más de dos factores primos, este procedimiento primero encuentra la factorización con el menor valor de a yb. Es decir, es el menor factor mayor o igual que la raíz cuadrada de n. Por tanto, es el mayor factor menor o igual que . Si el procedimiento devuelve , entonces n debe ser primo.

Para , sea cel mayor factor menor que la raíz. , por tanto, el número de pasos requeridos es aproximadamente:

.
Si n es primo (es decir, ), ¡hacen falta pasos! Esta es desde luego una mala forma de demostrarla primalidad de un número. Pero si n tiene un factor próximo a su raíz cuadrada, el método funciona rápidamente. Concretamente, si c difiere de en menos de , entonces el método sólo necesita unpaso, y esto es independiente del tamaño de n.

Ejemplo[editar]
Tómese el número para realizar su factorización, se procede así:

A: 78 79 80
Bcuad: 125 282 441
El tercer intento produce uncuadrado. , , y los factores son y .

Factorización de Fermat y división por tentativa[editar]
Intentemos factorizar el número primo n=2345678917, pero también calcular b y a-b. Empezando por y...