Factorización de enteros

Problema sin resolver en informática

¿Es posible resolver la factorización de enteros en tiempo polinomial en una computadora clásica?

Más problemas sin resolver en informática

En matemáticas , la factorización de enteros es la descomposición de un entero positivo en un producto de enteros. Todo entero positivo mayor que 1 es producto de dos o más factores enteros mayores que 1, en cuyo caso es un número compuesto , o no lo es, en cuyo caso es un número primo . Por ejemplo, $15$ es un número compuesto porque $15 = 3 \cdot 5$ , pero $7$ es un número primo porque no se puede descomponer de esta manera. Si uno de los factores es compuesto, se puede escribir a su vez como producto de factores más pequeños, por ejemplo, $60 = 3 \cdot 20 = 3 \cdot (5 \cdot 4)$ . Continuar este proceso hasta que cada factor sea primo se llama factorización prima ; el resultado siempre es único hasta el orden de los factores según el teorema de la factorización prima .

Para factorizar un número entero pequeño $n$ mediante cálculos mentales o manuales, el método más sencillo es la división por tanteo : comprobar si el número es divisible por los números primos $2$ , $3$ , $5$ , etc., hasta la raíz cuadrada de $n$ . Para números mayores, especialmente al usar un ordenador, existen algoritmos de factorización más sofisticados y eficientes. Un algoritmo de factorización prima suele consistir en comprobar si cada factor es primo cada vez que se encuentra uno.

Cuando los números son suficientemente grandes, no se conoce ningún algoritmo eficiente de factorización de enteros no cuántico . Sin embargo, no se ha demostrado que tal algoritmo no exista. La supuesta dificultad de este problema es importante para los algoritmos utilizados en criptografía, como el cifrado de clave pública RSA y la firma digital RSA . ^[¹^] Se han aplicado diversas áreas de las matemáticas y la informática a este problema, incluyendo curvas elípticas , teoría algebraica de números y computación cuántica.

No todos los números de una longitud dada son igual de difíciles de factorizar. Los casos más difíciles de estos problemas (para las técnicas conocidas actualmente) son los semiprimos , el producto de dos números primos. Cuando ambos son grandes, por ejemplo, de más de dos mil bits de longitud, elegidos al azar y de tamaño similar (pero no demasiado parecidos, por ejemplo, como para evitar una factorización eficiente mediante el método de Fermat ), incluso los algoritmos de factorización de primos más rápidos en las computadoras clásicas más veloces pueden tardar tanto tiempo que la búsqueda se vuelve impracticable; es decir, a medida que aumenta el número de dígitos del entero que se está factorizando, el número de operaciones necesarias para realizar la factorización en cualquier computadora clásica aumenta drásticamente.

Muchos protocolos criptográficos se basan en la supuesta dificultad de factorizar números enteros compuestos grandes o en un problema relacionado , como por ejemplo, el problema RSA . Un algoritmo que factorizara eficientemente un número entero arbitrario haría que la criptografía de clave pública basada en RSA fuera insegura.

Descomposición prima

Según el teorema fundamental de la aritmética , todo entero positivo tiene una factorización prima única . (Por convención, 1 es el producto vacío ). Comprobar si un entero es primo se puede hacer en tiempo polinomial , por ejemplo, mediante la prueba de primalidad AKS . Sin embargo, si es compuesto, las pruebas en tiempo polinomial no proporcionan información sobre cómo obtener los factores.

Dado un algoritmo general para la factorización de enteros, cualquier entero puede factorizarse en sus factores primos constituyentes mediante la aplicación repetida de este algoritmo. La situación se complica con algoritmos de factorización específicos, cuyos beneficios pueden no ser tan buenos, o incluso no serlo en absoluto, con los factores producidos durante la descomposición. Por ejemplo, si $n = 171 \times p \times q,$ donde $p < q$ son primos muy grandes, la división por tanteo producirá rápidamente los factores 3 y 19, pero se necesitarán $p$ divisiones para encontrar el siguiente factor. Como ejemplo contrastante, si $n$ es el producto de los primos $13729$ , $1372933$ y $18848997161$ , donde $13729 \times 1372933 = 18848997157$ , el método de factorización de Fermat comenzará con $⌈ \sqrt n ⌉ = 18848997159$ , lo que inmediatamente produce $b = \sqrt a 2 - n = \sqrt 4 = 2$ y, por lo tanto, los factores $a - b = 18848997157$ y $a + b = 18848997161$ . Si bien estos se reconocen fácilmente como compuestos y primos respectivamente, el método de Fermat tardará mucho más en factorizar el número compuesto porque el valor inicial de $⌈ \sqrt 18848997157 ⌉ = 137292$ para $a$ es un factor de 10 de $1372933$ .

Estado actual de la técnica

Entre los números de $b$ bits, los más difíciles de factorizar en la práctica con los algoritmos existentes son los semiprimos cuyos factores son de tamaño similar. Por esta razón, estos son los enteros que se utilizan en aplicaciones criptográficas.

En 2019, un equipo de investigadores, entre ellos Paul Zimmermann , factorizó un número de 240 dígitos (795 bits) ( RSA-240 ) , utilizando aproximadamente 900 años-núcleo de potencia de cálculo. ^[²^] Estos investigadores estimaron que un módulo RSA de 1024 bits tardaría aproximadamente 500 veces más. ^[³^]

El semiprimo más grande factorizado hasta la fecha fue RSA-250 , un número de 829 bits con 250 dígitos decimales, en febrero de 2020. El tiempo total de cálculo fue de aproximadamente 2700 años-núcleo de computación utilizando un procesador Intel Xeon Gold 6130 a 2,1 GHz. Al igual que todos los récords recientes de factorización, esta se completó con una implementación altamente optimizada del algoritmo de criba de campos numéricos general, ejecutada en cientos de máquinas.

complejidad temporal

No se ha publicado ningún algoritmo capaz de factorizar todos los enteros en tiempo polinomial , es decir, que pueda factorizar un número $n$ $de b$ bits en tiempo $O$ $($ $b$ $k$ $)$ para alguna constante $k$ . No se ha demostrado ni la existencia ni la inexistencia de tales algoritmos, pero generalmente se sospecha que no existen. ^[⁴^]^[⁵^]

Existen algoritmos publicados que son más rápidos que $O((1 + ε) b) para todo$ $ε$ positivo , es decir, subexponenciales . A partir de 2022, el algoritmo con el mejor tiempo de ejecución asintótico teórico es el cribado general de campos numéricos (GNFS), publicado por primera vez en 1993, ^{[ 6 ]} que se ejecuta en un número $n$ $de b$ bits en tiempo:

\exp \left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).

Para las computadoras actuales, GNFS es el mejor algoritmo publicado para $n$ grande (más de unos 400 bits). Sin embargo, para una computadora cuántica , Peter Shor descubrió en 1994 un algoritmo que lo resuelve en tiempo polinomial. El algoritmo de Shor solo requiere $O(b³)$ de tiempo y $O(b)$ de espacio para entradas numéricas $de$ $b$ bits. En 2001, el algoritmo de Shor se implementó por primera vez, utilizando técnicas de RMN en moléculas que proporcionan siete cúbits. ^{[ 7 ]}

Para hablar de clases de complejidad como P, NP y co-NP, el problema debe plantearse como un problema de decisión .

Problema de decisión (factorización entera) — Para cada número natural $n$ y $k$ ¿ Tiene $n$ algún factor menor que $k$ aparte de 1?

Se sabe que está en NP y co-NP , lo que significa que tanto las respuestas "sí" como "no" pueden verificarse en tiempo polinomial. Una respuesta de "sí" puede certificarse mostrando una factorización $n = d (⁠ n / d ⁠)$ con $d \leq k$ . Una respuesta de "no" puede certificarse mostrando la factorización de $n$ en primos distintos, todos mayores que $k$ ; se puede verificar su primalidad usando la prueba de primalidad AKS , y luego multiplicarlos para obtener $n$ . El teorema fundamental de la aritmética garantiza que solo hay una cadena posible de primos crecientes que será aceptada, lo que muestra que el problema está en UP y co-UP. ^{[ 8 ]} Se sabe que está en BQP debido al algoritmo de Shor.

Se sospecha que el problema está fuera de las tres clases de complejidad P, NP-completo, ^{[ 9 ]} y co-NP-completo . Por lo tanto, es un candidato para la clase de complejidad NP-intermedia .

En contraste, el problema de decisión "¿Es $n$ un número compuesto?" (o equivalentemente: "¿Es $n$ un número primo?") parece ser mucho más sencillo que el problema de especificar los factores de $n$ . El problema de la composición/primo se puede resolver en tiempo polinomial (en el número $b$ de dígitos de $n$ ) con la prueba de primalidad AKS . Además, existen varios algoritmos probabilísticos que pueden probar la primalidad muy rápidamente en la práctica si se acepta una probabilidad de error mínima. La facilidad de la prueba de primalidad es una parte crucial del algoritmo RSA , ya que es necesario encontrar números primos grandes para empezar.

Algoritmos de factorización

Uso especial

El tiempo de ejecución de un algoritmo de factorización específico depende de las propiedades del número que se va a factorizar o de alguno de sus factores desconocidos: tamaño, forma especial, etc. Los parámetros que determinan el tiempo de ejecución varían según el algoritmo.

Una subclase importante de algoritmos de factorización de propósito especial son los algoritmos de Categoría 1 o Primera Categoría , cuyo tiempo de ejecución depende del tamaño del factor primo más pequeño. Dado un entero de forma desconocida, estos métodos se suelen aplicar antes que los métodos de propósito general para eliminar factores pequeños. ^{[ 10 ]} Por ejemplo, la división por tanteo ingenua es un algoritmo de Categoría 1.

División de juicios
factorización de ruedas
El algoritmo rho de Pollard , que tiene dos variantes comunes para identificar ciclos de grupo : una de Floyd y otra de Brent.
Algoritmos de factorización de grupos algebraicos , entre los que se encuentran el algoritmo $p$ $- 1$ de Pollard , el algoritmo $p$ $+ 1$ de Williams y la factorización de curvas elípticas de Lenstra.
Método de factorización de Fermat
Método de factorización de Euler
tamiz de campo de número especial
Diferencia de dos cuadrados

De uso general

Un algoritmo de factorización de propósito general, también conocido como algoritmo de categoría 2 , segunda categoría o de la familia Kraitchik , ^[¹⁰^] tiene un tiempo de ejecución que depende únicamente del tamaño del entero a factorizar. Este es el tipo de algoritmo que se utiliza para factorizar números RSA . La mayoría de los algoritmos de factorización de propósito general se basan en el método de congruencia de cuadrados .

Otros algoritmos destacables

El algoritmo de Shor para computadoras cuánticas

Tiempo de ejecución heurístico

En teoría de números, existen muchos algoritmos de factorización de enteros que tienen un tiempo de ejecución esperado heurísticamente determinado.

L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}

en notación L y o minúscula . Algunos ejemplos de estos algoritmos son el método de la curva elíptica y la criba cuadrática . Otro algoritmo de este tipo es el método de relaciones de grupos de clases propuesto por Schnorr, ^[¹¹^] Seysen, ^[¹²^] y Lenstra, ^[¹³^] que demostraron asumiendo la hipótesis generalizada de Riemann no demostrada .

Tiempo de ejecución riguroso

El algoritmo probabilístico de Schnorr-Seysen-Lenstra ha sido rigurosamente probado por Lenstra y Pomerance ^{[ 14 ]} para tener un tiempo de ejecución esperado $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ reemplazando la suposición GRH con el uso de multiplicadores. El algoritmo utiliza el grupo de clases de formas cuadráticas binarias positivas del discriminante $Δ$ denotado por $G Δ$ . $G Δ$ es el conjunto de tríos de enteros $(a, b, c)$ en los que esos enteros son primos relativos.

Algoritmo de Schnorr-Seysen-Lenstra

Dado un entero $n$ que se va a factorizar, donde $n$ es un entero positivo impar mayor que una constante determinada. En este algoritmo de factorización, el discriminante $Δ$ se elige como un múltiplo de $n$ , $Δ = - dn$ , donde $d$ es un multiplicador positivo. El algoritmo espera que para un valor $de d$ existan suficientes formas suaves en $G Δ$ . Lenstra y Pomerance demuestran que la elección de $d$ puede restringirse a un conjunto pequeño para garantizar la suavidad del resultado.

Denotemos por $P Δ$ el conjunto de todos los números primos $q$ con símbolo de Kronecker $(⁠ Δ / q ⁠) = 1$ . Al construir un conjunto de generadores de $G Δ$ y formas primas $f q$ de $G Δ$ con $q$ en $P Δ$ se produce una secuencia de relaciones entre el conjunto de generadores y $f q$ . El tamaño de $q$ puede ser acotado por $c 0 (log | Δ |) 2$ para alguna constante $c 0$ .

La relación que se utilizará es una relación entre el producto de potencias que es igual al elemento neutro de $G Δ$ . Estas relaciones se utilizarán para construir una denominada forma ambigua de $G Δ$ , que es un elemento de $G Δ$ de orden divisor de 2. Al calcular la factorización correspondiente de $Δ$ y al tomar un mcd , esta forma ambigua proporciona la factorización prima completa de $n$ . Este algoritmo tiene los siguientes pasos principales:

Sea $n$ el número que se va a factorizar.

Sea $Δ$ un entero negativo tal que $Δ = - dn$ , donde $d$ es un multiplicador y $Δ$ es el discriminante negativo de alguna forma cuadrática.
Toma los $t$ primeros primos $p 1 = 2, p 2 = 3, p 3 = 5, ..., p t$ , para algún $t \in N$ .
Sea $f q$ una forma prima aleatoria de $G Δ$ con $(⁠ Δ / q ⁠) = 1$ .
Encuentra un conjunto generador $X$ de $G Δ$ .
Recopilar una secuencia de relaciones entre el conjunto $X$ y ${f q : q \in P Δ}$ que satisfagan:
$\left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.$
Construya una forma ambigua $(a, b, c)$ que sea un elemento $f \in G Δ$ de orden divisor de 2 para obtener una factorización coprima del mayor divisor impar de $Δ$ en la que $Δ = -4 ac$ o $Δ = a (a - 4 c)$ o $Δ = (b - 2 a)(b + 2 a)$ .
Si la forma ambigua proporciona una factorización de $n$ , entonces deténgase; de lo contrario, encuentre otra forma ambigua hasta que se encuentre la factorización de $n$ . Para evitar la generación de formas ambiguas inútiles, construya el grupo 2-Sylow $Sll 2 (Δ)$ de $G (Δ)$ .

Para obtener un algoritmo para factorizar cualquier entero positivo, es necesario agregar algunos pasos a este algoritmo, como la división por tanteo y la prueba de la suma de Jacobi .

Tiempo de ejecución previsto

El algoritmo, tal como se describe, es un $algoritmo$ probabilístico, ya que realiza elecciones aleatorias. Su tiempo de ejecución esperado es como máximo $L n [1 / 2, 1+ o (1)]$ . ^{[ 14 ]}

Véase también

factorización aurifeuilleana
Algoritmo de Bach : para la generación de números aleatorios factorizados.
Representación canónica de un número entero positivo
Factorización
Partición multiplicativa : forma de escribir un número como producto de otros números.
valoración $p -ádica$
Partición de enteros : descomposición de un entero como suma de enteros positivos.

Notas

^ Lenstra, Arjen K. (2011), "Factoring de enteros", en van Tilborg, Henk CA; Jajodia, Sushil (eds.), Enciclopedia de criptografía y seguridad , Boston: Springer, págs. 611–618 , doi : 10.1007/978-1-4419-5906-5_455 , ISBN 978-1-4419-5905-8
↑ " [ Cado-nfs-discuss ] Factorización de 795 bits y logaritmos discretos" . Archivado del original el 2 de diciembre de 2019.
↑ Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alejandro; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman JJ; Timofeev, Andrey; Zimmerman, Paul (2010). "Factorización de un módulo RSA de 768 bits" (PDF) . En Rabin, Tal (ed.). Avances en criptología - CRYPTO 2010, 30ª Conferencia Anual de Criptología, Santa Bárbara, CA, EE. UU., 15 al 19 de agosto de 2010. Actas . Apuntes de conferencias sobre informática. vol. 6223. Saltador. págs. 333– 350. doi : 10.1007/978-3-642-14623-7_18 . ISBN 978-3-642-14622-0.
↑ Krantz, Steven G. (2011), The Proof is in the Pudding: The Changing Nature of Mathematical Proof , Nueva York: Springer, pág. 203, doi : 10.1007/978-0-387-48744-1 , ISBN 978-0-387-48908-7, MR 2789493
↑ Arora, Sanjeev ; Barak, Boaz (2009), Computation complexity , Cambridge: Cambridge University Press, p. 230, doi : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4, MR 2500087 , S2CID 215746906
↑ Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). "Factorización de enteros con el método de la criba de cuerpos numéricos". El desarrollo del método de la criba de cuerpos numéricos . Lecture Notes in Mathematics. Vol. 1554. Springer. pp. 50–94 . doi : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-4Consultado el 12 de marzo de 2021 .
↑ Vandersypen, Lieven MK; et al. (2001). "Realización experimental del algoritmo de factorización cuántica de Shor mediante resonancia magnética nuclear". Nature . 414 (6866): 883– 887. arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID 11780055 . S2CID 4400832 .
↑ Lance Fortnow (13 de septiembre de 2002). "Blog sobre complejidad computacional: Clase de complejidad de la semana: Factorización" .
↑ Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 Complejidad computacional", en Gowers, Timothy ; Barrow-Green, June ; Leader, Imre (eds.), The Princeton Companion to Mathematics , Princeton, Nueva Jersey: Princeton University Press, pp. 575–604 , ISBN 978-0-691-11880-2, MR 2467561 Véase en particular la página 583 .
1 2 David Bressoud y Stan Wagon (2000). Un curso de teoría computacional de números . Key College Publishing/Springer. págs. 168–69 . ISBN 978-1-930190-10-8.
↑ Schnorr, Claus P. (1982). "Análisis refinado y mejoras en algunos algoritmos de factorización" . Journal of Algorithms . 3 (2): 101– 127. doi : 10.1016/0196-6774(82)90012-8 . MR 0657269. Archivado del original el 24 de septiembre de 2017.
↑ Seysen , Martin (1987). "Un algoritmo de factorización probabilística con formas cuadráticas de discriminante negativo" . Matemáticas de la Computación . 48 (178): 757–780 . doi : 10.1090/S0025-5718-1987-0878705-X.MR 0878705 .
↑ Lenstra, Arjen K (1988). "Factorización rápida y rigurosa bajo la hipótesis generalizada de Riemann" (PDF) . Indagationes Mathematicae . 50 (4): 443– 454. doi : 10.1016/S1385-7258(88)80022-2 .
1 2 Lenstra, HW; Pomerance, Carl (julio de 1992). "Un límite de tiempo riguroso para factorizar enteros" (PDF) . Journal of the American Mathematical Society . 5 (3): 483– 516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

Referencias

Richard Crandall y Carl Pomerance (2001). Números primos: una perspectiva computacional . Springer. ISBN 0-387-94777-9.Capítulo 5: Algoritmos de factorización exponencial, págs. 191–226. Capítulo 6: Algoritmos de factorización subexponencial, págs. 227–284. Sección 7.4: Método de curva elíptica, págs. 301–313.
Donald Knuth . El arte de la programación informática , Volumen 2: Algoritmos seminuméricos , Tercera edición. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sección 4.5.4: Factorización en números primos, págs. 379–417.
Samuel S. Wagstaff Jr. (2013). El placer de factorizar . Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3..
Warren, Henry S. Jr. (2013). Hacker's Delight (2.ª ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

Enlaces externos

msieve – SIQS y NFS – ha ayudado a completar algunas de las factorizaciones públicas más grandes conocidas.
Richard P. Brent, "Avances recientes y perspectivas de los algoritmos de factorización de enteros", Computing and Combinatorics , 2000, págs. 3-22. Descargar
Manindra Agrawal , Neeraj Kayal, Nitin Saxena, "PRIMES está en P." Anales de Matemáticas 160(2): 781–793 (2004). Agosto de 2005 versión PDF
Eric W. Weisstein, “RSA-640 Factorizado” , MathWorld Headline News , 8 de noviembre de 2005
Calculadora de factorización de enteros de Dario Alpern : una aplicación web para factorizar números enteros grandes.

[1] Lenstra, Arjen K. (2011), "Factoring de enteros", en van Tilborg, Henk CA; Jajodia, Sushil (eds.), Enciclopedia de criptografía y seguridad , Boston: Springer, págs. 611–618 , doi : 10.1007/978-1-4419-5906-5_455 , ISBN 978-1-4419-5905-8

[2] " [ Cado-nfs-discuss ] Factorización de 795 bits y logaritmos discretos" . Archivado del original el 2 de diciembre de 2019.

[rsa768-3] Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alejandro; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman JJ; Timofeev, Andrey; Zimmerman, Paul (2010). "Factorización de un módulo RSA de 768 bits" (PDF) . En Rabin, Tal (ed.). Avances en criptología - CRYPTO 2010, 30ª Conferencia Anual de Criptología, Santa Bárbara, CA, EE. UU., 15 al 19 de agosto de 2010. Actas . Apuntes de conferencias sobre informática. vol. 6223. Saltador. págs. 333– 350. doi : 10.1007/978-3-642-14623-7_18 . ISBN 978-3-642-14622-0.

[4] Krantz, Steven G. (2011), The Proof is in the Pudding: The Changing Nature of Mathematical Proof , Nueva York: Springer, pág. 203, doi : 10.1007/978-0-387-48744-1 , ISBN 978-0-387-48908-7, MR 2789493

[5] Arora, Sanjeev ; Barak, Boaz (2009), Computation complexity , Cambridge: Cambridge University Press, p. 230, doi : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4, MR 2500087 , S2CID 215746906

[6] Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). "Factorización de enteros con el método de la criba de cuerpos numéricos". El desarrollo del método de la criba de cuerpos numéricos . Lecture Notes in Mathematics. Vol. 1554. Springer. pp. 50–94 . doi : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-4Consultado el 12 de marzo de 2021 .

[7] Vandersypen, Lieven MK; et al. (2001). "Realización experimental del algoritmo de factorización cuántica de Shor mediante resonancia magnética nuclear". Nature . 414 (6866): 883– 887. arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID 11780055 . S2CID 4400832 .

[8] Lance Fortnow (13 de septiembre de 2002). "Blog sobre complejidad computacional: Clase de complejidad de la semana: Factorización" .

[9] Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 Complejidad computacional", en Gowers, Timothy ; Barrow-Green, June ; Leader, Imre (eds.), The Princeton Companion to Mathematics , Princeton, Nueva Jersey: Princeton University Press, pp. 575–604 , ISBN 978-0-691-11880-2, MR 2467561 Véase en particular la página 583 .

[Bressoud_and_Wagon-10] 1 2 David Bressoud y Stan Wagon (2000). Un curso de teoría computacional de números . Key College Publishing/Springer. págs. 168–69 . ISBN 978-1-930190-10-8.

[1982-schnorr-11] Schnorr, Claus P. (1982). "Análisis refinado y mejoras en algunos algoritmos de factorización" . Journal of Algorithms . 3 (2): 101– 127. doi : 10.1016/0196-6774(82)90012-8 . MR 0657269. Archivado del original el 24 de septiembre de 2017.

[1987-seysen-12] Seysen , Martin (1987). "Un algoritmo de factorización probabilística con formas cuadráticas de discriminante negativo" . Matemáticas de la Computación . 48 (178): 757–780 . doi : 10.1090/S0025-5718-1987-0878705-X.MR 0878705 .

[1988-lenstra-13] Lenstra, Arjen K (1988). "Factorización rápida y rigurosa bajo la hipótesis generalizada de Riemann" (PDF) . Indagationes Mathematicae . 50 (4): 443– 454. doi : 10.1016/S1385-7258(88)80022-2 .

[lenstra-pomerance-14] 1 2 Lenstra, HW; Pomerance, Carl (julio de 1992). "Un límite de tiempo riguroso para factorizar enteros" (PDF) . Journal of the American Mathematical Society . 5 (3): 483– 516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

[

[

[

[

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[

[

[ 14 ]