Método de factorización de Fermat

El método de factorización de Fermat es un algoritmo para factorizar (factorizar) un número entero impar , propuesto por Pierre Fermat ( 1601 - 1665 ) en 1643 . $norte$

El método se basa en buscar tales enteros y que satisfagan la relación , lo que lleva a una descomposición de . $X$ $y$ $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$

Historia

A principios del siglo XVII en Francia, las ideas matemáticas comenzaron a difundirse activamente entre los científicos a través de la correspondencia. En 1638, Pierre Fermat se unió al círculo de eruditos correspondientes . La correspondencia era una forma conveniente de comunicarse, ya que Fermat vivía en Toulouse , y muchos de sus conocidos científicos vivían en París . Una de estas científicas fue Maren Mersenne , que se dedicaba a la distribución de cartas, reenvío y comunicación de muchos científicos entre ellos. El 26 de diciembre de 1638, en una carta a Mersenne , Fermat mencionó que había encontrado un método por el cual uno podía encontrar divisores de números positivos, pero omitió detalles y una descripción del método. En ese momento, Mersenne también mantuvo correspondencia con el matemático francés Bernard Frenicle de Bessy , quien, como Fermat, se dedicaba a la teoría de números , en particular, a los divisores de números naturales y números perfectos . A principios de 1640 , al enterarse de que Fermat había recibido un método para encontrar divisores, Frenicle escribió a Mersenne, quien le envió la carta de Fermat. Mersenne fue durante mucho tiempo el enlace entre los dos matemáticos en su correspondencia. Fue en las cartas a Frenicle que Fermat pudo probar la corrección del método de factorización, así como por primera vez formular y justificar las disposiciones principales del teorema, que más tarde se denominó pequeño teorema de Fermat [1] [2 ] .

Justificación

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

Si es impar, entonces existe una correspondencia biunívoca entre la factorización y la representación como diferencia de cuadrados con , dada por las fórmulas $n>1$ $n=a\cdot b$ $n=x^{2}-y^{2}$ $x>y>0$ ${\ estilo de visualización x = (a + b)/2,}$ ${\ estilo de visualización y = (ab)/2,}$ $a=x+y$ ${\ estilo de visualización b = xy.}$

Prueba

Si se da la factorización , entonces la relación se cumple: . Así, se obtiene una representación en forma de diferencia de dos cuadrados. $n=a\cdot b$ $n=a\cdot b=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {ab}{2}}\right)^ {2}$

Por el contrario, si se da eso , entonces el lado derecho se puede factorizar: [3] . $n=x^{2}-y^{2}$ ${\ estilo de visualización (xy) (x + y)}$

Descripción del algoritmo

Para factorizar un número impar, se busca un par de números tales que , o . En este caso, los números y son divisores , posiblemente triviales (es decir, uno de ellos es igual a 1 y el otro es igual a ). $norte$ $(x, y)$ $x^2 - y^2 = norte$ ${\ estilo de visualización (xy) \ cdot (x + y) = n}$ ${\ estilo de visualización (x + y)}$ ${\ estilo de visualización (xy)}$ $norte$ $norte$

En el caso no trivial, la igualdad equivale a , es decir, a lo que es un cuadrado . $x^2 - y^2 = norte$ ${\ estilo de visualización x^{2}-n=y^{2}}$ ${\ estilo de visualización x^{2}-n}$

La búsqueda de un cuadrado de este tipo comienza con - el número más pequeño para el cual la diferencia no es negativa. $x=\left\lceil {\sqrt {n))\right\rceil$ ${\ estilo de visualización x^{2}-n}$

Para cada valor a partir de , calcule y verifique si este número no es un cuadrado exacto. Si no, aumente en uno y pase a la siguiente iteración. $k\in {\matemáticas {N}),$ $k=1$ $\left(\left\lceil {\sqrt {n))\right\rceil +k\right)^{2}-n$ $k$

Si es un cuadrado exacto, es decir, entonces se obtiene la expansión: $\left(\left\lceil {\sqrt {n))\right\rceil +k\right)^{2}-n$ $x^{2}-n=\left(\left\lceil {\sqrt {n))\right\rceil +k\right)^{2}-n=y^{2},$

n=x^{2}-y^{2}=(x+y)(xy)=a\cdot b,

donde $x=\left\lceil {\sqrt {n))\right\rceil +k.$

Si es trivial y único, entonces es simple. $norte$

En la práctica, el valor de la expresión en el paso -ésimo se calcula teniendo en cuenta el valor en el paso -ésimo: ${\ estilo de visualización (k + 1)}$ $k$

(s+1)^{2}-n=s^{2}+2s+1-n,

dónde $s=\left\lceil {\sqrt {n))\right\rceil +k.$

Ejemplos

Ejemplo de iteración baja

Tomemos un número . Calcular Para calcularemos los valores de la función . Para mayor simplicidad, construiremos una tabla que contendrá los valores y en cada paso de iteración. Obtenemos: $n=10873$ $s=\left\lceil {\sqrt {n}}\right\rceil =105.$ ${\ estilo de visualización k = 0,1,2,...}$ $s+k$ $y=(s+k)^{2}-n$ ${\ sqrt {y}}$

$k$	$y$	${\ sqrt {y}}$
una	363	19.052
2	576	24

Como se puede ver en la tabla, ya en el segundo paso de iteración se obtuvo un valor entero . ${\ sqrt {y}}$

Así, se produce la siguiente expresión: . De ahí se sigue que $(105+2)^{2}-n=24^{2}$ $n=107^{2}-24^{2}=131\cdot 83=10873.$

Un ejemplo con un gran número de iteraciones

Sea entonces o $n=89755.$ ${\ sqrt {n}} \ aproximadamente 299.591$ $s=\left\lceil {\sqrt {n}}\right\rceil =300.$

$k$	$y$	${\ sqrt {y}}$
77	52374	228.854
78	53129	230.497
79	53886	232.134
80	54645	233.763
81	55406	235.385
82	56169	237

{\ sqrt {y}} = 237

a=s+k+{\sqrt {y}}=300+82+237=619

b=s+k-{\sqrt {y}}=300+82-237=145

Esta expansión no es finita, ya que, obviamente, el número no es primo: $145$ $145=29\cpunto 5.$

Como resultado, la descomposición final del número original en el producto de factores primos $norte$ $89755=5\cdot 29\cdot 619.$

Evaluación del desempeño

La mayor eficiencia de cálculo por el método de factorización de Fermat se logra cuando los factores del número son aproximadamente iguales entre sí. Esto proporciona una búsqueda de secuencia relativamente corta [4] $norte$

s^{2}-n,\ (s+1)^{2}-n,\ (s+2)^{2}-n,\ \puntos \ (s+k)^{2} -norte.

En el peor de los casos, cuando, por ejemplo, cerca de a está cerca de 1, el algoritmo de Fermat funciona peor que el método de búsqueda del divisor . Número de iteraciones para un caso dado $a$ $norte,$ $b$

\operatorname {Iter} (n)={\frac {a+b}{2}}-\left\lceil n^{1/2}\right\rceil \approx {\frac {n}{2 }}-\left\lceil n^{1/2}\right\rceil ,

es decir, es obvio que tiene el orden $En).$

El método de factorización de Fermat funcionará tan bien como el método de enumeración de divisores si es posible obtener una estimación para un divisor más grande a partir de aquí . Por lo tanto, el método de Fermat tiene una estimación exponencial y, como método de división de prueba, no es adecuado para descomponer números grandes . Puede mejorar la eficiencia si primero intenta dividir un número por números de 2 a alguna constante B y luego busca divisores usando el método de Fermat. Tal campaña ayuda a deshacerse de los pequeños divisores del número [5] . $\operatorname {Iter} (n)<n^{1/2},$ $a<4n^{1/2}.$ $norte$ $norte$

Optimización de divisores

Supongamos que estamos tratando de factorizar el número n = 2345678917 usando el método de Fermat, pero además de b también calculamos a − b . A partir de , se puede escribir: ${\ sqrt {n}}$

a	48 433	48 434	48 435	48 436
segundo 2	76 572	173 439	270 308	367 179
b	276.7	416.5	519.9	605.9
un - b	48.156,3	48.017,5	47,915.1	47.830,1

Si ahora empezáramos a usar el método de enumeración de divisores para descomponer un número , entonces tendría sentido verificar divisores solo hasta 47,830, y no hasta 48,432, ya que si hubiera un divisor mayor, entonces se encontraría por el método de Fermat. . Entonces, en solo cuatro pasos, el método de Fermat verificó todos los divisores desde 47,830 hasta 48,432. $norte$ $norte$ $norte$

Por lo tanto, es posible combinar el método de Fermat con el método de enumeración de divisores. Es suficiente elegir un número y usar el método de Fermat para verificar los divisores entre y , y los divisores restantes se pueden verificar enumerando los divisores, y los divisores deben verificarse solo hasta el número [6] . $c>{\sqrt {n}}$ $C$ ${\ sqrt {n}}$ $c-{\sqrt {c^{2}-n))$

En el ejemplo anterior, cuando , los divisores deben iterarse hasta el número 47830. También, por ejemplo, puede elegir el número que da el borde 28937. ${\ estilo de visualización c = 48436}$ ${\ estilo de visualización c = 55000}$

La combinación de métodos es buena, porque con una diferencia suficiente entre los divisores de un número, el método de enumeración de divisores es más eficiente que el método de Fermat [5] . Esto se ilustra con el siguiente ejemplo: $norte$

a	60 001	60 002
segundo 2	1 254 441 084	1 254 561 087
b	35.418,1	35.419,8
un - b	24.582,9	24.582,2

Método de tamiz

Al buscar el cuadrado de un número natural en una secuencia de números, no es necesario que calcules la raíz cuadrada de cada valor en esa secuencia, ni siquiera verifiques todos los valores posibles para un . Por ejemplo, considere un número : ${\ estilo de visualización a^{2}-n}$ ${\ estilo de visualización n = 2345678917}$

a	48 433	48 434	48 435	48 436
segundo 2	76 572	173 439	270 308	367 179
b	276.7	416.5	519.9	605.9

Inmediatamente, sin calcular la raíz cuadrada, puede decir que ninguno de los valores en la tabla es un cuadrado. Basta, por ejemplo, utilizar el hecho de que todos los cuadrados de los números naturales tomados módulo 20 son iguales a uno de los siguientes valores: 0, 1, 4, 5, 9, 16. Estos valores se repiten para cada aumento en a por 10. En el ejemplo de módulo 20, por lo tanto, restando 17 (o sumando 3), obtenemos que el número módulo 20 es igual a uno de los siguientes: 3, 4, 7, 8, 12, 19. Pero como es un número natural, de aquí obtenemos que el módulo 20 solo puede ser igual a 4. Por lo tanto, el módulo 20 y /o el módulo 10. Por lo tanto, puede verificar la raíz de la expresión no para todos , sino solo para aquellos que terminan en 1 o 9 [6] . $segundo^{2}$ ${\ estilo de visualización n = 17}$ $segundo^{2}$ $b$ $segundo^{2}$ ${\ estilo de visualización a ^ {2} = 1}$ $un=1$ ${\ estilo de visualización a = 9}$ ${\ estilo de visualización a^{2}-n}$ $a$

De manera similar, cualquier potencia de varios números primos se puede usar como módulo. Por ejemplo, tomando el mismo número , encontramos ${\ estilo de visualización n = 2345678917}$

Módulo 16:	los cuadrados son iguales	0, 1, 4 o 9
	n mod 16 es igual	5
	por lo tanto es igual $un ^ 2$	9
	y un es	3, 5, 11 o 13 módulo 16
Módulo 9:	los cuadrados son iguales	0, 1, 4 o 7
	n mod 9 es igual	7
	por lo tanto es igual $un ^ 2$	7
	y un es	4 o 5 módulo 9

Optimización del multiplicador

El método de Fermat funciona bien cuando el número tiene un factor que es aproximadamente igual a la raíz cuadrada de [5] . $norte$ $norte$

Si conoces la razón aproximada entre los factores del número , entonces puedes elegir un número racional que sea aproximadamente igual a esta razón. Entonces podemos escribir la siguiente igualdad: , donde los factores y están cerca debido a las suposiciones hechas. Por lo tanto, al aplicar el método de Fermat para expandir el número , se pueden encontrar rápidamente. Además, para encontrar y, puede usar las igualdades y (en caso de que no sea divisible por y no sea divisible por ). ${\ estilo de visualización d/c}$ $norte$ ${\ estilo de visualización u/v}$ $nuv=cv\cdot du$ ${\ estilo de visualización cv}$ $du$ ${\ estilo de visualización nuv}$ $C$ $d$ ${\ estilo de visualización \ gcd (n, cv) = c}$ ${\ estilo de visualización \ gcd (n, du) = d}$ $tu$ $C$ $v$ $d$

En general, cuando no se conoce la relación entre los factores , se puede intentar usar diferentes relaciones e intentar expandir el número resultante . Un algoritmo basado en este método fue propuesto por primera vez por el matemático estadounidense Sherman Lehman en 1974 [7] y se llama método Lehman . El algoritmo factoriza de manera determinista un número natural dado en operaciones aritméticas [8] , pero actualmente solo tiene interés histórico y casi nunca se usa en la práctica [9] . $norte$ ${\ estilo de visualización u/v}$ ${\ estilo de visualización nuv}$ $norte$ $O(n^{{1/3}})$

El Método Krajczyk-Farm

Maurice Krajczyk propuso una generalización del método de Fermat en 1926. Propuso considerar en lugar de pares de números que satisfagan la relación , buscar pares de números que satisfagan una comparación más general. Tal comparación se puede encontrar multiplicando varias comparaciones de la forma , donde son números pequeños, cuyos productos serán ser un cuadrado. Para ello, podemos considerar pares de números , donde es un número entero ligeramente mayor que , y . Krajczyk notó que muchos de los números obtenidos de esta manera se descomponen en pequeños factores primos, es decir, los números son suaves [10] . ${\ estilo de visualización (x, y),}$ ${\ estilo de visualización x^{2}-y^{2}=n,}$ $x^{2}\equiv y^{2}{\pmod {n}}.$ ${\displaystyle u_{i}^{2}\equiv v_{i))$ $v_{i}$ ${\ estilo de visualización (u_ {i}, v_ {i})}$ $tu_{yo}$ ${\ sqrt n}$ $v_{i}=u_{i}^{2}-n$ $v_{i}$ $v_{i}$

La secuencia de acciones según Krajcik [11]

Encuentre el conjunto de pares que satisfacen la relación ${\ estilo de visualización (x, y),}$ $x\equiv y{\pmod {n)).$
Determinar la descomposición total o parcial de números y factores para cada par $X$ $y$ ${\ estilo de visualización (x, y).}$
Elija pares cuyo producto satisfaga la relación ${\ estilo de visualización (x, y),}$ $x^{2}\equiv y^{2}{\pmod {n}}.$
Factorizar un número . $norte$

Ejemplo [12]

Usando el método Krajczyk-Farm, descomponemos el número El número es el primero cuyo cuadrado es mayor que el número : ${\ estilo de visualización n = 2041.}$ $46$ $norte$ ${\ estilo de visualización 46 ^ {2} = 2116.}$

Calcular el valor de la función para todo Obtenemos $v(u)=u^{2}-n$ ${\ estilo de visualización u = 46,47, \ puntos}$ $75,168,263,360,459,560,\puntos$

Según el método de Fermat, sería necesario continuar con los cálculos hasta encontrar el cuadrado de cualquier número. Según el método de Krajczyk-Fermat, entonces es necesario buscar sucesivamente aquellos para los que Entonces $Reino Unido}$ $v(u_{1})v(u_{2})\dots v(u_{k})=y^{2},u_{1}u_{2}\dots u_{k}=x.$

x^{2}=u_{1}^{2}u_{2}^{2}\dots u_{k}^{2}\equiv (u_{1}^{2}-n)\ cdot (u_{2}^{2}-n)\cdots (u_{k}^{2}-n)=v(u_{1})\cdot v(u_{2})\dots v(u_{ k})=y^{2}{\pmod {n}}.

Del algoritmo de Krajczyk-Fermat se deduce que todos los números resultantes se pueden factorizar fácilmente. ${\ estilo de visualización (u_ {k}^{2}-n)}$

En realidad: $75=3\cdot 5^{2},\ 168=2^{3}\cdot 3\cdot 7,\ 360=2^{3}\cdot 3^{2}\cdot 5,\ 560 =2^{4}\cpunto 5\cpunto 7.$

Obviamente, el producto de los cuatro números obtenidos será un cuadrado: Entonces ya podemos calcular $2^{{10}}\cdot 3^{4}\cdot 5^{4}\cdot 7^{2}.$ $(x,y):$

x=46\cdot 47\cdot 49\cdot 51\equiv 311{\pmod {2041)),

y=2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7\equiv 1416{\pmod {2041)).

A continuación, utilizando el algoritmo de Euclides, encontramos . $\gcd(1416-311,2041)=13$

De este modo, $2041=13\cdot 157.$

Algoritmo de Dixon

En 1981, el matemático John Dixon de la Universidad de Carleton publicó su propio método de factorización basado en las ideas de Krajczyk [13] [14] [15] [16] .

El algoritmo de Dixon se basa en el concepto de bases factoriales y es una generalización del algoritmo de factorización de Fermat. En el algoritmo, en lugar de pares de números que satisfagan la ecuación, se buscan pares de números que satisfagan una ecuación más general , para cuya solución Krajczyk notó varios hechos útiles. Complejidad computacional del algoritmo [17] $x^2 - y^2 = norte$ $x^2 \equiv y^2\pmod{n}$

T=O\left({L\left({n}\right)}^{2}\right),

dónde $L\left({n}\right)=\exp {\left({\sqrt {\ln {n}\cdot \ln {\ln {n))))\right)}.$

Otras mejoras

La idea del método de factorización de Fermat subyace a algunos de los algoritmos más rápidos para factorizar semiprimos grandes : el método de tamiz cuadrático y el método de tamiz de campo numérico general . La principal diferencia entre el método de tamiz cuadrático y el método de Fermat es que en lugar de buscar un cuadrado, la secuencia contiene pares de tales números cuyos cuadrados son iguales en valor absoluto (cada uno de estos pares puede ser una descomposición de un número ). Luego, entre los pares de números encontrados, se busca el par que es la expansión del número . [Dieciocho] ${\ estilo de visualización a^{2}-n}$ $norte$ $norte$ $norte$

Una evolución del método de factorización de Fermat es el método de formas cuadráticas de Shanks (también conocido como SQUFOF), basado en la aplicación de formas cuadráticas . Curiosamente, para las computadoras de 32 bits, los algoritmos basados en este método son los líderes indiscutibles entre los algoritmos de factorización para números de a [19] . $10^{{10}}$ $10^{18}$

Aplicación

El algoritmo de factorización de Fermat se puede aplicar al criptoanálisis RSA . Si los números aleatorios cuyo producto es igual a son cercanos entre sí, entonces se pueden encontrar mediante el método de factorización de Fermat. Luego puede encontrar el exponente secreto , descifrando así RSA [20] [21] . En el momento de la publicación del algoritmo RSA, solo se conocía un pequeño número de algoritmos de factorización, el más famoso de los cuales era el método de Fermat. $pag q$ $norte$ $d$

Datos interesantes

El conocido economista y logista inglés W. S. Jevons hizo la siguiente suposición en su libro The Principles of Science ( 1874 ) [22] :

Dados dos números, puedes encontrar su producto de una manera simple y confiable, pero es otra cosa cuando necesitas encontrar sus factores para un número grande. ¿Puedes decir qué dos números se multiplican para hacer 8616460799 ? No creo que nadie más que yo lo sepa.

Curiosamente, el número indicado por Jevons se puede descomponer manualmente por el método de Fermat utilizando el método de criba en unos 10 minutos. De hecho, . Usando el método del tamiz, uno puede llegar rápidamente a la relación $\left\lceil {\sqrt {n}}\right\rceil =92\,825$

92\,880^{2}-n=10\,233\,601=3199^{2}.

Así, la descomposición en factores primos tiene la forma . $8\,616\,460\,799=89\,681\cdot 96\,079$

La idea principal de Jevons sobre la complejidad de descomponer números en factores primos en comparación con su multiplicación es válida, pero solo cuando se trata del producto de números que no son tan cercanos entre sí [23] .

Véase también

Notas

↑ Fletcher, Colin R. Una reconstrucción de la correspondencia Frenicle-Fermat de 1640 // Historia Mathematica : diario. - 1991. - vol. 18 , núm. 4 . - P. 311-410 . (enlace no disponible)
↑ Pierre de Fermat; Curtiduría Paul; Carlos Enrique; Apolonio, de Perge.; Jacques de Billy. 2 // Obras de Fermat . - París: Gauthier-Villars et fils, 1894.
↑ Koblitz, 2001 , pág. 161.
↑ David Bishop. Introducción a la Criptografía con Java Applets . - Jones and Bartlett Inc., 2003. - P. 224. - 384 p. — ISBN 0-7637-2207-3 .
↑ 1 2 3 Ishmukhametov, 2011 , pág. 54.
↑ 12 McKee , James . Acelerando el método de factorización de Fermat (1991).
↑ Lehman, R. Sherman. Factorización de enteros grandes // Matemáticas de computación. - 1974. - T. 28 , N º 126 . - S. 637-646 . -doi : 10.2307/ 2005940 .
↑ Lehman, R. Sherman. Factorización de enteros grandes (indefinidos) // Matemáticas de computación. - 1974. - T. 28 , N º 126 . - S. 637-646 . -doi : 10.2307/ 2005940 .
↑ Nesterenko, 2011 , pág. 140.
↑ Ishmukhametov, 2011 , pág. 115.
↑ Nesterenko, 2011 , pág. 164.
↑ Carl Pomerance. Historia de dos tamices // Avisos Amer. Matemáticas. soc. - 1996. - vol. 43 , núm. 12 _ - P. 1473-1485 .
↑ Dixon, J.D.Factorización asintóticamente rápida de enteros // Math . compensación : diario. - 1981. - vol. 36 , núm. 153 . - P. 255-260 . -doi : 10.1090/ S0025-5718-1981-0595059-1 . — .
↑ Ishmukhametov, 2011 , pág. 117.
↑ Cheremushkin, 2002 , pág. 75-77.
↑ Vasilenko, 2003 , pág. 57-60.
↑ Cheremushkin, 2002 , pág. 79-80.
↑ Pomerancé, Carl . A Tale of Two Sieves (diciembre de 1996), págs. 1473–1485. Archivado el 11 de noviembre de 2020. Consultado el 18 de noviembre de 2012.
↑ Yike Guo, 2002 , Minería de datos de alto rendimiento: algoritmos, aplicaciones y sistemas de escala.
↑ Benne de Weger. Revisión de la factorización de Fermat para el módulo RSA // Appl . Álgebra Ing. común computar : diario. - 2002. - T. 13 , N º 1 . - S. 17-28 . -doi : 10.1007/ s002000100088 .
↑ Sounak Gupta, Goutam Paul. Revisión de la factorización de Fermat para el módulo RSA (inglés) // CoRR: revista. - 2009. - T. abs / 0910.4179 .
↑ Principios de la ciencia , Macmillan & Co., 1874, p. 141.
↑ Knuth, 2007 , pág. 435.

Literatura

en ruso

Vasilenko O. N. Algoritmos teóricos de números en criptografía . - M. : MTSNMO , 2003. - 328 p. — ISBN 5-94057-103-4 . Archivado el 27 de enero de 2007 en Wayback Machine .
Ishmukhametov Sh. T. Métodos de factorización para números naturales: un tutorial . - Kazán: Kazán. un., 2011. - 190 p.
Koblitz N. Un curso de teoría de números y criptografía . - 2do. - M. : Editorial científica TVP, 2001. - 254 p. — ISBN 5-94057-103-4 .
Nesterenko A. Introducción a la criptografía moderna.Algoritmos teóricos de números . - 2011. - 190 págs.
Cheremushkin AV Conferencias sobre algoritmos aritméticos en criptografía . - M. : MTSNMO , 2002. - 104 p. — ISBN 5-94057-060-7 . Archivado el 31 de mayo de 2013 en Wayback Machine .
Donald Knuth . El arte de la programación informática, volumen 2. Métodos derivados = El arte de la programación informática, vol.2. Algoritmos Semiméricos. - 3ra ed. - M. : "Williams" , 2007. - 832 p. — ISBN 5-8459-0081-6 .

en inglés

Pruebas de primalidad y factorización de DM de Bressoud . - Nueva York: Springer-Verlag, 1989. - 260 p. - ISBN 0-387-97040-1 . (enlace no disponible)

Mahoney MS La carrera matemática de Pierre de Fermat . - 2. - París: Universidad de Princeton. Prensa, 1994. - S. 324-332. — 438 pág. - ISBN 0-691-03666-7 .

Yike Guo, R. L. Grossman. Minería de datos de alto rendimiento: algoritmos de escalado, aplicaciones y sistemas . - 2. - 2002. - 112 págs. — ISBN 978-0792377450 .

en francés

Kraitchik M. Factorización y prueba de primalidad . - París: Gauthier-Villars, 1926. - T. 2. - S. 195-208. — 251 págs. - ISBN 0-387-97040-1 .

Enlaces

Calculadora en línea basada en el método de factorización de Fermat

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin