Método de factorización de Fermat

El método de factorización de Fermat , que recibe su nombre de Pierre de Fermat , se basa en la representación de un número entero impar como la diferencia de dos cuadrados :

${\displaystyle N=a^{2}-b^{2}.}$

Esa diferencia es factorizable algebraicamente como${\displaystyle (a+b)(ab)}$; si ninguno de los factores es igual a uno, es una factorización propia de N .

Cada número impar tiene tal representación. De hecho, si${\displaystyle N=cd}$es una factorización de N , entonces

${\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {cd}{2}}\right)^{2}.}$

Como N es impar, entonces c y d 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 por tanteo (en el peor de los casos). Sin embargo, la combinación de la división por tanteo y el método de Fermat es más eficaz que cualquiera de ellos por separado.

Uno prueba varios valores de a , esperando que${\displaystyle a^{2}-N=b^{2}}$, un cuadrado.

Factor de Fermat(N): // N debe ser impar a ← techo(sqrt(N)) b2 ← a*a - N repetir hasta que b2 sea un cuadrado: a ← a + 1 b2 ← a*a - N // equivalentemente: // b2 ← b2 + 2*a + 1 // a ← a + 1 devolver a - sqrt(b2) // o a + sqrt(b2)

Por ejemplo, para factorizar${\displaystyle N=5959}$, el primer intento para a es la raíz cuadrada de 5959 redondeada al siguiente entero, que es 78. Entonces${\displaystyle b^{2}=78^{2}-5959=125}$Como 125 no es un cuadrado perfecto, se hace un segundo intento aumentando el valor de a en 1. El segundo intento también falla, porque 282 tampoco es un cuadrado perfecto.

El tercer intento produce el cuadrado perfecto de 441. Por lo tanto,${\displaystyle a=80}$,${\displaystyle b=21}$y los factores de 5959 son${\displaystyle ab=59}$y${\displaystyle a+b=101}$.

Supongamos que N tiene más de dos factores primos. Ese procedimiento primero encuentra la factorización con los valores más pequeños de a y b . Es decir,${\displaystyle a+b}$es el factor más pequeño ≥ la raíz cuadrada de N , y por lo tanto${\displaystyle ab=N/(a+b)}$es el factor más grande ≤ raíz cuadrada de N. Si el procedimiento encuentra${\displaystyle N=1\cdot N}$, eso demuestra que N es primo.

Para${\displaystyle N=cd}$Sea c el factor de subraíz más grande.${\displaystyle a=(c+d)/2}$, por lo que el número de pasos es aproximadamente${\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}$.

Si N es primo (de modo que${\displaystyle c=1}$), uno necesita${\displaystyle O(N)}$pasos. Esta es una mala manera de probar 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${\displaystyle {\left(4N\right)}^{1/4}}$de${\displaystyle {\sqrt {N}}}$, el método requiere solo un paso; esto es independiente del tamaño de N.

Consideremos el intento de factorizar el número primo N = 2,345,678,917 , pero también calcular b y a − b en todo momento. Subiendo desde${\displaystyle {\sqrt {N}}}$redondeando al siguiente número entero, que es 48.433, 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 de subraíz más arriba${\displaystyle ab=47830.1}$El método de Fermat ya lo habría encontrado.

La división por ensayo normalmente probaría hasta 48.432; pero después de solo cuatro pasos de Fermat, solo necesitamos dividir hasta 47.830, para encontrar un factor o probar la primalidad.

Todo esto sugiere un método de factorización combinado. Elija algún límite.${\displaystyle a_{\mathrm {max} }>{\sqrt {N}}}$; utilice el método de Fermat para factores entre${\displaystyle {\sqrt {N}}}$y${\displaystyle a_{\mathrm {max} }}$. Esto establece un límite para la división de juicios que es${\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}$. En el ejemplo anterior, con${\displaystyle a_{\mathrm {max} }=48436}$La división de destino para juicio es 47830. Una opción razonable podría ser${\displaystyle a_{\mathrm {max} }=55000}$dando un límite de 28937.

En este sentido, el método de Fermat ofrece rendimientos decrecientes. Sin duda, uno se detendría antes de llegar a este punto:

Al considerar la tabla para${\displaystyle N=2345678917}$, uno puede darse cuenta rápidamente de que ninguno de los valores de${\displaystyle b^{2}}$son cuadrados:

No es necesario calcular todas las raíces cuadradas de${\displaystyle a^{2}-N}$, ni siquiera examinar todos los valores de a . Los cuadrados son siempre congruentes con 0, 1, 4, 5, 9, 16 módulo 20, porque estos son los residuos cuadráticos de 20. Los valores se repiten con cada aumento de a en 10. En este ejemplo, N es 17 mod 20, por lo que restando 17 mod 20 (o sumando 3),${\displaystyle a^{2}-N}$produce 3, 4, 7, 8, 12 y 19 módulo 20 para estos valores. Es evidente que solo el 4 de esta lista puede ser un cuadrado. Por lo tanto,${\displaystyle a^{2}}$debe ser 1 mod 20, lo que significa que a es 1, 9, 11 o 19 mod 20; producirá un${\displaystyle b^{2}}$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${\displaystyle N=2345678917}$,

Generalmente se elige una potencia de un número primo diferente para cada módulo.

Dada una secuencia de valores a (inicio, fin y paso) y un módulo, se puede proceder de la siguiente manera:

Tamiz de Fermat(N , astart, aend, astep, módulo) a ← astart hacer módulo veces : b2 ← a*a - N Si b2 es un cuadrado, módulo módulo: FermatSieve(N , a, aend, astep * módulo, NextModulus) endif a ← a + un paso final

Pero la recursión se detiene cuando quedan pocos valores de a ; es decir, cuando ( aend-astart )/ astep es pequeño. Además, como el tamaño del paso de a es constante, se pueden calcular b2 sucesivos mediante sumas.

El método de Fermat funciona mejor cuando hay un factor cercano a la raíz cuadrada de N.

Si la razón aproximada de dos factores (${\displaystyle d/c}$) es conocido, entonces un número racional${\displaystyle v/u}$se puede elegir cerca de ese valor.${\displaystyle Nuv=cv\cdot du}$y el método de Fermat, aplicado a Nuv , hallará los factores${\displaystyle cv}$y${\displaystyle du}$rápido. Entonces${\displaystyle \gcd(N,cv)=c}$y${\displaystyle \gcd(N,du)=d}$(A menos que c divida a u o d divida a v ).

Generalmente, si no se conoce la proporción, varios${\displaystyle u/v}$Se pueden probar valores y tratar de factorizar cada Nuv resultante . R. Lehman ideó una forma sistemática de hacerlo, de modo que la división de Fermat más la división de prueba puede factorizar N en${\displaystyle O(N^{1/3})}$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 cuerpos numéricos generales , los algoritmos más conocidos para factorizar semiprimos grandes , que son el "peor caso". La principal mejora que la criba cuadrática introduce sobre el método de factorización de Fermat es que, en lugar de simplemente encontrar un cuadrado en la secuencia de${\displaystyle a^{2}-n}$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 módulo n que, si no es trivial, puede usarse para factorizar n .

• Completando el cuadrado
• Factorización de polinomios
• Teorema del factor
• Regla FOIL
• factorización monoide
• Triángulo de Pascal
• factor primo
• Factorización
• Método de factorización de Euler
• Factorización de enteros
• Síntesis de programas
• Tabla de factorizaciones enteras gaussianas
• factorización única

• Fermat (1894), Obras de Fermat , vol.  2, pág.  256
• McKee, J (1999). "Acelerando el método de factorización de Fermat" . Matemáticas de la Computación . 68 (228): 1729– 1737. doi : 10.1090/S0025-5718-99-01133-3 .

• Tiempo de ejecución de la factorización de Fermat , en blogspot.in
• Calculadora en línea de factorización de Fermat , en windowspros.ru