Fermat 's factorización método , el nombre de Pierre de Fermat , se basa en la representación de un extraño número entero 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 adecuado de N .
Cada número impar tiene tal representación. De hecho, sies una factorización de N , entonces
Desde N es impar, entonces c y d también son impares, por lo que esas mitades son números enteros. (A múltiplo de cuatro es también una diferencia de cuadrados: que c y d sea aún.)
En su forma más simple, el método de Fermat podría ser incluso más lento que la división de prueba (el peor de los casos). No obstante, la combinación de la división de prueba y la de Fermat es más eficaz que cualquiera de las dos.
Método básico
Uno prueba varios valores de a , esperando que, un cuadrado.
FermatFactor (N): // N debe ser impar a ← techo (raíz cuadrada (N)) b2 ← a * a - N repita hasta que b2 sea un cuadrado: a ← a + 1 b2 ← a * a - N // de forma equivalente: // b2 ← b2 + 2 * a + 1 // a ← a + 1 devuelve a - sqrt (b2) // o a + sqrt (b2)
Por ejemplo, factorizar , el primer intento para a es la raíz cuadrada de 5959 redondeada al siguiente entero, que es 78 . Luego,. Dado que 125 no es un cuadrado, se realiza un segundo intento aumentando el valor de a en 1. El segundo intento también falla, porque 282 tampoco es un cuadrado.
Intentar: | 1 | 2 | 3 |
---|---|---|---|
a | 78 | 79 | 80 |
b 2 | 125 | 282 | 441 |
B | 11.18 | 16,79 | 21 |
El tercer intento produce el cuadrado perfecto de 441. Entonces, , y los factores de 5959 son y .
Suponga que N tiene más de dos factores primos. Este procedimiento primero encuentra la factorización con el mínimo de los valores de una y b . Es decir,es el factor más pequeño ≥ la raíz cuadrada de N , por lo quees el factor más grande ≤ Raíz N . Si el procedimiento encuentra, eso muestra que N es primo.
Para , sea c el factor de subraíz más grande., por lo que el número de pasos es aproximadamente .
Si N es primo (de modo que), uno necesita pasos. Ésta es una mala forma de demostrar la originalidad. 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 solo un paso; esto es independiente del tamaño de N . [ cita requerida ]
División de Fermat y Trial
Considere el factor de tratar de número primo N = 2345678917 , sino también de cómputo b y un - b en todas partes. Subiendo desde, podemos tabular:
a | 48,433 | 48,434 | 48,435 | 48,436 |
---|---|---|---|---|
b 2 | 76.572 | 173,439 | 270.308 | 367,179 |
B | 276,7 | 416,5 | 519,9 | 605,9 |
a - b | 48.156,3 | 48.017,5 | 47.915,1 | 47.830,1 |
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 arriba, El método de Fermat ya lo habría encontrado.
La división de prueba normalmente probaría hasta 48,432; pero después de solo cuatro pasos de Fermat, solo necesitamos dividir hasta 47830, para encontrar un factor o probar la primordialidad.
Todo esto sugiere un método de factorización combinado. Elige un límite; utilizar 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, con el límite para la división de prueba es 47830. Una opción razonable podría ser dando un límite de 28937.
En este sentido, el método de Fermat da rendimientos decrecientes. Seguramente uno se detendría antes de este punto:
a | 60,001 | 60,002 |
---|---|---|
b 2 | 1.254.441.084 | 1.254.561.087 |
B | 35.418,1 | 35.419,8 |
a - b | 24.582,9 | 24.582,2 |
Mejora del tamiz
Al considerar la mesa para , se puede decir rápidamente que ninguno de los valores de son cuadrados:
a | 48,433 | 48,434 | 48,435 | 48,436 |
---|---|---|---|---|
b 2 | 76.572 | 173,439 | 270.308 | 367,179 |
B | 276,7 | 416,5 | 519,9 | 605,9 |
No es necesario calcular todas las raíces cuadradas de , ni siquiera examinar todos los valores de a . Los cuadrados son siempre congruentes con 0, 1, 4, 5, 9, 16 módulo 20. Los valores se repiten con cada aumento de a por 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 solo los 4 de esta lista pueden ser un cuadrado. Por lo tanto,debe ser 1 mod 20, lo que significa que a es 1, 9, 11 o 19 mod 20; producirá unque 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,
módulo 16: | Los cuadrados son | 0, 1, 4 o 9 |
N mod 16 es | 5 | |
entonces Solo puede ser | 9 | |
y una debe haber | 3 o 5 o 11 o 13 módulo 16 | |
módulo 9: | Los cuadrados son | 0, 1, 4 o 7 |
N mod 9 es | 7 | |
entonces Solo puede ser | 7 | |
y una debe haber | 4 o 5 módulo 9 |
Generalmente, se elige una potencia de un primo diferente para cada módulo.
Dada una secuencia de un -valores (inicio, final y de paso) y un módulo, se puede proceder de este modo:
FermatSieve (N, astart, aend, astep, módulo) a ← astart hacer tiempos de módulo : b2 ← a * a - N si b2 es un cuadrado, módulo módulo: FermatSieve (N, a, aend, astep * módulo, NextModulus) terminara si a ← a + un paso enddo
Sin embargo, la recursividad se detiene cuando unos unos permanecen-valores; es decir, cuando (aend-astart) / astep es pequeño. Además, debido a que el tamaño de paso de a es constante, se pueden calcular b2 sucesivos con adiciones.
Se puede realizar una mejora modular adicional aplicando el algoritmo de división como una transformación afín, es decir , , , sobre cualquier anillo entero dónde . Después de una pequeña cantidad de álgebra, se puede concluir que y donde s y t son idénticos para determinar los acarreos que se hacen al multiplicar los divisores sobre la base . [ cita requerida ]
Mejora del multiplicador
Método de Fermat funciona mejor cuando hay un factor de cerca de la raíz cuadrada de N .
Si la razón aproximada de dos factores () se conoce, entonces el número racional se puede elegir cerca de ese valor. Por ejemplo, si, luego es una buena estimación para el menor de un par de divisores. , y los factores son aproximadamente iguales: el de Fermat, aplicado a Nuv , los encontrará rápidamente. Luego y . (A menos que c divida a u o d divida a v .) Una generalización adicional de este enfoque supone que, significa que .
Generalmente, si se desconoce la relación, varios Se pueden probar los valores y tratar de factorizar cada Nuv resultante . R. Lehman ideó una forma sistemática de hacer esto, de modo que la división de prueba más de Fermat pueda factorizar N enhora. [1]
Otras mejoras
Las ideas fundamentales del método de factorización de Fermat son la base del tamiz cuadrático y el tamiz de campo numérico general , los algoritmos más conocidos para factorizar semiprimas grandes , que son el "peor caso". La principal mejora que ofrece 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 mod cuadrado n que, si no es trivial, se puede usar para factorizar n .
Ver también
Notas
- ^ Lehman, R. Sherman (1974). "Factorizar números enteros grandes" (PDF) . Matemáticas de la Computación . 28 (126): 637–646. doi : 10.2307 / 2005940 .
Referencias
- Fermat (1894), Oeuvres de Fermat , 2 , pág. 256
- McKee, J (1999). "Acelerando el método de factorización de Fermat" . Matemáticas de la computación (68): 1729-1737.
enlaces externos
- Tiempo de ejecución de factorización de Fermat , en blogspot.in
- Calculadora en línea de factorización de Fermat , en windowspros.ru