El método de factorización de Fermat , llamado así en honor a Pierre de Fermat , se basa en la representación de un número entero impar como la diferencia de dos cuadrados :
Esa diferencia se puede factorizar algebraicamente como ; si ninguno de los factores es igual a uno, es una factorización adecuada de N.
Cada número impar tiene tal representación. De hecho, si es una factorización de N , entonces
Como N es impar, entonces cyd también son impares, por lo que esas mitades son números enteros . (Un múltiplo de cuatro también es una diferencia de cuadrados: sean c y d pares).
En su forma más simple, el método de Fermat podría ser incluso más lento que la división de prueba (en el peor de los casos). Sin embargo, la combinación de la división de prueba y la de Fermat es más eficaz que cualquiera de ellas por sí sola.
Se prueban varios valores de a , esperando que sea un cuadrado.
FermatFactor(N): // N debería ser impar a ← techo(sqrt(N)) b2 ← a*a - norte repita hasta que b2 sea un cuadrado: un ← un + 1 b2 ← a*a - norte // equivalentemente: // b2 ← b2 + 2*a + 1 // un ← un + 1 devolver a - sqrt(b2) // o a + sqrt(b2)
Por ejemplo, para factorizar , el primer intento de a es la raíz cuadrada de 5959 redondeada al siguiente entero, que es 78 . Entonces, . Como 125 no es un cuadrado, se hace un segundo intento aumentando el valor de a en 1. El segundo intento también falla, porque nuevamente 282 no es un cuadrado.
El tercer intento produce el cuadrado perfecto de 441. Entonces, , y los factores de 5959 son y .
Supongamos que N tiene más de dos factores primos. Ese procedimiento primero encuentra la factorización con los valores mínimos de a y b . Es decir, es el factor más pequeño ≥ la raíz cuadrada de N , y también lo es el factor más grande ≤ raíz de N. Si el procedimiento encuentra , eso demuestra que N es primo.
Para , sea c el factor subraíz más grande. , por lo que el número de pasos es aproximadamente .
Si N es primo (de modo que ), se necesitan pasos. Esta es una mala manera de demostrar la primalidad. Pero si N tiene un factor cercano a su raíz cuadrada, el método funciona rápidamente. Más precisamente, si c difiere menos que de , el método requiere sólo un paso; esto es independiente del tamaño de N . [ cita necesaria ]
Considere intentar factorizar el número primo N = 2345678917 , pero también calcule b y a − b en todo momento. Subiendo desde , podemos tabular:
En la práctica, uno no se molestaría con esa última fila hasta que b sea un número entero. Pero observe que si N tuviera un factor subraíz arriba de , el método de Fermat ya lo habría encontrado.
La división de prueba normalmente intentaría hasta 48.432; pero después de sólo cuatro pasos de Fermat, sólo necesitamos dividir hasta 47830 para encontrar un factor o demostrar la primalidad.
Todo esto sugiere un método de factorización combinado. Elija algún límite ; Utilice el método de Fermat para factores entre y . Esto da un límite para la división de prueba que es . En el ejemplo anterior, el límite para la división de prueba es 47830. Una opción razonable podría ser dar un límite de 28937.
En este sentido, el método de Fermat da rendimientos decrecientes. Seguramente nos detendríamos antes de este punto:
Al considerar la tabla de , se puede ver rápidamente que ninguno de los valores de son cuadrados:
No es necesario calcular todas las raíces cuadradas de , ni siquiera examinar todos los valores de a . Los cuadrados siempre son congruentes con 0, 1, 4, 5, 9, 16 módulo 20. Los valores se repiten con cada aumento de a en 10. En este ejemplo, N es 17 mod 20, por lo que restar 17 mod 20 (o sumar 3) , produce 3, 4, 7, 8, 12 y 19 módulo 20 para estos valores. Es evidente que sólo los 4 de esta lista pueden ser un cuadrado. Así, debe ser 1 mod 20, lo que significa que a es 1, 9, 11 o 19 mod 20; producirá a que termina en 4 mod 20 y, si es cuadrado, b terminará en 2 u 8 mod 10.
Esto se puede realizar con cualquier módulo. Usando el mismo ,
Generalmente se elige una potencia de un primo diferente para cada módulo.
Dada una secuencia de valores a (inicio, final y paso) y un módulo, se puede proceder así:
FermatSieve(N, astart, aend, astep, módulo) a ← empezar hacer tiempos de módulo : b2 ← a*a - norte si b2 es un cuadrado, módulo módulo: FermatSieve(N, a, aend, astep * módulo, NextModulus) terminara si a ← a + un paso final
Pero la recursividad se detiene cuando quedan pocos valores de a ; es decir, cuando (aend-astart)/astep es pequeño. Además, debido a que el tamaño del paso de a es constante, se pueden calcular b2 sucesivos con sumas.
El método de Fermat funciona mejor cuando hay un factor cerca de la raíz cuadrada de N.
Si se conoce la proporción aproximada de dos factores ( ), entonces se puede elegir un número racional cerca de ese valor. , y el método de Fermat, aplicado a Nuv , permitirá encontrar los factores y rápidamente. Entonces y . (A menos que c divida a u o d divida a v ).
Generalmente, si no se conoce la relación, se pueden probar varios valores e intentar factorizar cada Nuv resultante . R. Lehman ideó una forma sistemática de hacer esto, de modo que la división de prueba plus de Fermat pueda factorizar N en el tiempo. [1]
Las ideas fundamentales del método de factorización de Fermat son la base de la criba cuadrática y la criba de campos numéricos generales , los algoritmos más conocidos para factorizar semiprimos grandes , que son el "peor de los casos". La principal mejora que aporta el tamiz cuadrático sobre el método de factorización de Fermat es que en lugar de simplemente encontrar un cuadrado en la secuencia de , encuentra un subconjunto de elementos de esta secuencia cuyo producto es un cuadrado, y lo hace de una manera muy eficiente. El resultado final es el mismo: una diferencia de cuadrados mod n que, si no es trivial, puede usarse para factorizar n .
