Fatoração de inteiros

Problema de ciência da computação em aberto:

A fatoração de inteiros pode ser resolvida em tempo polinomial em um computador clássico?

(mais problemas em aberto da ciência da computação)

Na matemática, a fatoração de inteiros (ou fatorização de inteiros) é a decomposição de um inteiro positivo em um produto de inteiros. Todo inteiro positivo maior que 1 ou é o produto de dois ou mais inteiros (fatores) maiores que 1, caso em que é um número composto, ou não é, caso em que é um número primo. Por exemplo, $15$ é um número composto porque $15 = 3 \cdot 5$ , mas $7$ é um número primo porque não pode ser decomposto desta maneira. Se um dos fatores for composto, ele pode, por sua vez, ser escrito como um produto de fatores menores; por exemplo, $60 = 3 \cdot 20 = 3 \cdot (5 \cdot 4)$ . Continuar esse processo até que todos os fatores sejam primos é chamado de fatoração em primos (ou decomposição em fatores primos); o resultado é sempre único, exceto pela ordem dos fatores, pelo teorema fundamental da aritmética.

Para fatorar um inteiro pequeno $n$ usando aritmética mental ou papel e caneta, o método mais simples é a divisão por tentativa: verificar se o número é divisível por números primos $2$ , $3$ , $5$ , e assim por diante, até a raiz quadrada de $n$ . Para números maiores, especialmente ao usar um computador, vários algoritmos de fatoração mais sofisticados são mais eficientes. Um algoritmo de fatoração em primos normalmente envolve testar se cada fator é primo cada vez que um fator é encontrado.

Quando os números são suficientemente grandes, nenhum algoritmo eficiente de fatoração de inteiros não-quântico é conhecido. No entanto, não foi provado que tal algoritmo não exista. A suposta dificuldade deste problema é importante para os algoritmos usados em criptografia, como a criptografia de chave pública RSA e a assinatura digital RSA [en].^[1] Muitas áreas da matemática e da ciência da computação foram aplicadas a este problema, incluindo curvas elípticas, teoria algébrica dos números e computação quântica.

Nem todos os números de um determinado comprimento são igualmente difíceis de fatorar. As instâncias mais difíceis desses problemas (para as técnicas atualmente conhecidas) são os semiprimos, o produto de dois números primos. Quando ambos são grandes, por exemplo, com mais de dois mil bits de comprimento, escolhidos aleatoriamente e aproximadamente do mesmo tamanho (mas não muito próximos, por exemplo, para evitar a fatoração eficiente pelo Método de fatoração de Fermat), mesmo os algoritmos de fatoração em primos mais rápidos nos computadores clássicos mais velozes podem levar tempo suficiente para tornar a busca impraticável; isto é, à medida que o número de dígitos do inteiro a ser fatorado aumenta, o número de operações necessárias para realizar a fatoração em qualquer computador clássico aumenta drasticamente.

Muitos protocolos criptográficos baseiam-se na suposta dificuldade de fatorar grandes inteiros compostos ou em um problema relacionado – por exemplo, o problema RSA. Um algoritmo que fatore eficientemente um inteiro arbitrário tornaria insegura a criptografia de chave pública baseada em RSA.

Decomposição em primos

Pelo teorema fundamental da aritmética, todo inteiro positivo tem uma única fatoração prima. (Por convenção, 1 é o produto vazio.) Testar se o inteiro é primo pode ser feito em tempo polinomial, por exemplo, pelo teste de primalidade AKS. Se for composto, no entanto, os testes de tempo polinomial não dão nenhuma pista sobre como obter os fatores.

Dado um algoritmo geral para fatoração de inteiros, qualquer inteiro pode ser fatorado em seus fatores primos constituintes pela aplicação repetida deste algoritmo. A situação é mais complicada com algoritmos de fatoração de propósito específico, cujos benefícios podem não ser percebidos tão bem ou de forma alguma com os fatores produzidos durante a decomposição. Por exemplo, se $n = 171 \times p \times q$ onde $p < q$ são primos muito grandes, a divisão por tentativa produzirá rapidamente os fatores 3 e 19, mas levará $p$ divisões para encontrar o próximo fator. Como exemplo contrastante, se $n$ é o produto dos primos $13729$ , $1372933$ , e $18848997161$ , onde $13729 \times 1372933 = 18848997157$ , o método de fatoração de Fermat começará com $⌈ \sqrt n ⌉ = 18848997159$ o que imediatamente produz $b = \sqrt a 2 - n = \sqrt 4 = 2$ e, portanto, os fatores $a - b = 18848997157$ e $a + b = 18848997161$ . Embora estes sejam facilmente reconhecidos como composto e primo, respectivamente, o método de Fermat levará muito mais tempo para fatorar o número composto porque o valor inicial de $⌈ \sqrt 18848997157 ⌉ = 137292$ para $a$ está a um fator de 10 de $1372933$ .

Estado da arte atual

Entre os números de $b$ -bits, os mais difíceis de fatorar na prática usando algoritmos existentes são aqueles semiprimos cujos fatores são de tamanho similar. Por esta razão, estes são os inteiros usados em aplicações criptográficas.

Em 2019, um número de 240 dígitos (795 bits) (RSA-240 [en]) foi fatorado por uma equipe de pesquisadores incluindo Paul Zimmermann [en], utilizando aproximadamente 900 núcleos-ano (core-years) de poder computacional.^[2] Esses pesquisadores estimaram que um módulo RSA de 1024 bits levaria cerca de 500 vezes mais tempo.^[3]

O maior semiprimo já fatorado foi o RSA-250 [en], um número de 829 bits com 250 dígitos decimais, em fevereiro de 2020. O tempo total de computação foi de aproximadamente 2700 núcleos-ano de computação usando Intel Xeon Gold 6130 a 2.1 GHz. Como todos os recordes recentes de fatoração, esta fatoração foi completada com uma implementação altamente otimizada do crivo geral de corpo de números (GNFS) executado em centenas de máquinas.

Complexidade de tempo

Nenhum algoritmo foi publicado que possa fatorar todos os inteiros em tempo polinomial, isto é, que possa fatorar um número $n$ de $b$ -bits em tempo $O (b k)$ para alguma constante $k$ . Nem a existência nem a não-existência de tais algoritmos foi provada, mas geralmente suspeita-se que eles não existam.^[4]^[5]

Existem algoritmos publicados que são mais rápidos que $O((1 + ε) b)$ para todo positivo $ε$ , isto é, subexponencial. Desde 2022, o algoritmo com o melhor tempo de execução assintótico teórico é o crivo geral de corpo de números (GNFS), publicado pela primeira vez em 1993,^[6] rodando em um número $n$ de $b$ -bits em tempo:

\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 computadores atuais, o GNFS é o melhor algoritmo publicado para grandes $n$ (mais de cerca de 400 bits). Para um computador quântico, no entanto, Peter Shor descobriu um algoritmo em 1994 que o resolve em tempo polinomial. O Algoritmo de Shor leva apenas tempo $O(b 3)$ e espaço $O(b)$ em entradas de números de $b$ -bits. Em 2001, o algoritmo de Shor foi implementado pela primeira vez, usando técnicas de RMN em moléculas que fornecem sete qubits.^[7]

Para falar sobre classes de complexidade como P, NP e co-NP, o problema tem que ser declarado como um problema de decisão.

Problema de decisão (Fatoração de inteiros) — Para quaisquer números naturais $n$ e $k$ , $n$ tem um fator menor que $k$ além de 1?

Sabe-se que está em ambos NP e co-NP, o que significa que tanto respostas "sim" quanto "não" podem ser verificadas em tempo polinomial. Uma resposta "sim" pode ser certificada exibindo uma fatoração $n = d( /* start https://pt.wikipedia.org/ */ .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} /* end https://pt.wikipedia.org/ */ ⁠n/d⁠)$ com $d \leq k$ . Uma resposta "não" pode ser certificada exibindo a fatoração de $n$ em primos distintos, todos maiores que $k$ ; pode-se verificar sua primalidade usando o teste de primalidade AKS e, então, multiplicá-los para obter $n$ . O teorema fundamental da aritmética garante que existe apenas uma sequência possível de primos crescentes que será aceita, o que mostra que o problema está em ambos UP e co-UP.^[8] Sabe-se que está em BQP devido ao algoritmo de Shor.

Suspeita-se que o problema esteja fora de todas as três classes de complexidade P, NP-completo,^[9] e co-NP-completo. É, portanto, um candidato para a classe de complexidade NP-intermediário.

Em contraste, o problema de decisão "O número $n$ é um número composto?" (ou equivalentemente: "O número $n$ é um número primo?") parece ser muito mais fácil do que o problema de especificar fatores de $n$ . O problema composto/primo pode ser resolvido em tempo polinomial (no número $b$ de dígitos de $n$ ) com o teste de primalidade AKS. Além disso, existem vários algoritmos probabilísticos que podem testar a primalidade muito rapidamente na prática se alguém estiver disposto a aceitar uma possibilidade de erro infinitesimalmente pequena. A facilidade do teste de primalidade é uma parte crucial do algoritmo RSA, pois é necessário encontrar grandes números primos para começar.

Algoritmos de fatoração

Propósito específico

O tempo de execução de um algoritmo de fatoração de propósito específico depende das propriedades do número a ser fatorado ou de um de seus fatores desconhecidos: tamanho, forma especial, etc. Os parâmetros que determinam o tempo de execução variam entre os algoritmos.

Uma subclasse importante de algoritmos de fatoração de propósito específico são os algoritmos de Categoria 1 ou Primeira Categoria, cujo tempo de execução depende do tamanho do menor fator primo. Dado um inteiro de forma desconhecida, esses métodos são geralmente aplicados antes dos métodos de propósito geral para remover fatores pequenos.^[10] Por exemplo, a divisão por tentativa ingênua é um algoritmo de Categoria 1.

Divisão por tentativa
Fatoração por roda [en]
Algoritmo rho de Pollard [en], que tem duas variantes comuns para identificar ciclos de grupo [en]: uma por Floyd e uma por Brent.
Algoritmos de fatoração de grupo algébrico [en], entre os quais estão o algoritmo $p - 1$ de Pollard [en], algoritmo $p + 1$ de Williams, e a fatoração de curva elíptica de Lenstra [en]
Método de fatoração de Fermat
Método de fatoração de Euler [en]
Crivo especial de corpo de números [en]
Diferença de dois quadrados [en]

Propósito geral

Um algoritmo de fatoração de propósito geral, também conhecido como um algoritmo de Categoria 2, Segunda Categoria, ou da família de Kraitchik,^[10] tem um tempo de execução que depende unicamente do tamanho do inteiro a ser fatorado. Este é o tipo de algoritmo usado para fatorar números RSA [en]. A maioria dos algoritmos de fatoração de propósito geral é baseada no método de congruência de quadrados [en].

Método de fatoração de Dixon [en]
Fatoração por frações contínuas [en] (CFRAC)
Crivo quadrático [en]
Crivo racional [en]
Crivo geral de corpo de números
Fatoração de formas quadradas de Shanks [en] (SQUFOF)

Outros algoritmos notáveis

Algoritmo de Shor, para computadores quânticos

Tempo de execução heurístico

Na teoria dos números, existem muitos algoritmos de fatoração de inteiros que heuristicamente têm tempo de execução esperado

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

em o-pequeno e Notação L. Alguns exemplos desses algoritmos são o método da curva elíptica [en] e o Crivo quadrático [en]. Outro algoritmo desse tipo é o método de relações de grupo de classes proposto por Schnorr,^[11] Seysen,^[12] e Lenstra,^[13] que eles provaram apenas assumindo a não provada Hipótese de Riemann generalizada.

Tempo de execução rigoroso

O algoritmo probabilístico Schnorr–Seysen–Lenstra foi rigorosamente provado por Lenstra e Pomerance^[14] ter um tempo de execução esperado de $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ substituindo a suposição da GRH (Hipótese de Riemann Generalizada) pelo uso de multiplicadores. O algoritmo usa o grupo de classes de formas quadráticas binárias positivas de discriminante [en] $Δ$ denotado por $G Δ$ . $G Δ$ é o conjunto de triplas de inteiros $(a, b, c)$ nas quais esses inteiros são primos relativos.

Algoritmo Schnorr–Seysen–Lenstra

Dado um inteiro $n$ que será fatorado, onde $n$ é um inteiro positivo ímpar maior que uma certa constante. Neste algoritmo de fatoração, o discriminante $Δ$ é escolhido como um múltiplo de $n$ , $Δ = - dn$ , onde $d$ é algum multiplicador positivo. O algoritmo espera que para um $d$ existam formas suaves [en] suficientes em $G Δ$ . Lenstra e Pomerance mostram que a escolha de $d$ pode ser restrita a um pequeno conjunto para garantir o resultado de suavidade.

Denote por $P Δ$ o conjunto de todos os primos $q$ com símbolo de Kronecker $(⁠ Δ / q ⁠) = 1$ . Construindo um conjunto de geradores de $G Δ$ e formas primas $f q$ de $G Δ$ com $q$ em $P Δ$ , uma sequência de relações entre o conjunto de geradores e $f q$ é produzida. O tamanho de $q$ pode ser limitado por $c 0 (log| Δ |) 2$ para alguma constante $c 0$ .

A relação que será usada é uma relação entre o produto de potências que é igual ao elemento neutro de $G Δ$ . Essas relações serão usadas para construir uma chamada forma ambígua de $G Δ$ , que é um elemento de $G Δ$ de ordem dividindo 2. Calculando a fatoração correspondente de $Δ$ e tomando um mdc, esta forma ambígua fornece a fatoração prima completa de $n$ . Este algoritmo tem estas etapas principais:

Seja $n$ o número a ser fatorado.

Seja $Δ$ um inteiro negativo com $Δ = - dn$ , onde $d$ é um multiplicador e $Δ$ é o discriminante negativo de alguma forma quadrática.
Tome os $t$ primeiros primos $p 1 = 2, p 2 = 3, p 3 = 5, ..., p t$ , para algum $t \in N$ .
Seja $f q$ uma forma prima aleatória de $G Δ$ com $(⁠ Δ / q ⁠) = 1$ .
Encontre um conjunto gerador $X$ de $G Δ$ .
Colete uma sequência de relações entre o conjunto $X$ e ${f q : q \in P Δ}$ satisfazendo:
$\left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.$
Construa uma forma ambígua $(a, b, c)$ que é um elemento $f \in G Δ$ de ordem dividindo 2 para obter uma fatoração coprima do maior divisor ímpar de $Δ$ na qual $Δ = -4 ac$ ou $Δ = a (a - 4 c)$ ou $Δ = (b - 2 a)(b + 2 a)$ .
Se a forma ambígua fornecer uma fatoração de $n$ então pare, caso contrário, encontre outra forma ambígua até que a fatoração de $n$ seja encontrada. Para evitar que formas ambíguas inúteis sejam geradas, construa o 2-subgrupo de Sylow $Sll 2 (Δ)$ de $G (Δ)$ .

Para obter um algoritmo para fatorar qualquer inteiro positivo, é necessário adicionar algumas etapas a este algoritmo, como divisão por tentativa e o teste de soma de Jacobi [en].

Tempo de execução esperado

O algoritmo como declarado é um algoritmo probabilístico pois faz escolhas aleatórias. Seu tempo de execução esperado é no máximo $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ .^[14]

Ver também

Algoritmo de Bach [en]
Fatoração
Fatoração aurifeuilliana [en]
Partição de inteiros [en]
Partição multiplicativa — maneira de escrever um número como produto de outros números
Representação canônica de um inteiro positivo [en]
Valoração $p$ -ádica [en]

Referências

↑ Lenstra, Arjen K. (2011), «Integer Factoring», in: van Tilborg, Henk C. A.; Jajodia, Sushil, Encyclopedia of Cryptography and Security, ISBN 978-1-4419-5905-8, Boston: Springer, pp. 611–618, doi:10.1007/978-1-4419-5906-5_455
↑ «[Cado-nfs-discuss] 795-bit factoring and discrete logarithms». Arquivado do original em 2 de dezembro de 2019
↑ Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alexander; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman J. J.; Timofeev, Andrey; Zimmermann, Paul (2010). «Factorization of a 768-Bit RSA Modulus» (PDF). In: Rabin, Tal. Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings. Lecture Notes in Computer Science. 6223. Springer. pp. 333–350. ISBN 978-3-642-14622-0. doi:10.1007/978-3-642-14623-7_18
↑ Krantz, Steven G. (2011), The Proof is in the Pudding: The Changing Nature of Mathematical Proof, ISBN 978-0-387-48908-7, New York: Springer, p. 203, MR 2789493, doi:10.1007/978-0-387-48744-1
↑ Arora, Sanjeev; Barak, Boaz (2009), Computational complexity, ISBN 978-0-521-42426-4, Cambridge: Cambridge University Press, p. 230, MR 2500087, doi:10.1017/CBO9780511804090
↑ Buhler, J. P.; Lenstra, H. W. Jr.; Pomerance, Carl (1993). «Factoring integers with the number field sieve». The development of the number field sieve. Col: Lecture Notes in Mathematics (em inglês). 1554. [S.l.]: Springer. pp. 50–94. ISBN 978-3-540-57013-4. doi:10.1007/BFb0091539. hdl:1887/2149. Consultado em 12 de março de 2021
↑ Vandersypen, Lieven M. K.; et al. (2001). «Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance». Nature. 414 (6866): 883–887. Bibcode:2001Natur.414..883V. PMID 11780055. arXiv:quant-ph/0112176. doi:10.1038/414883a
↑ Lance Fortnow (13 de setembro de 2002). «Computational Complexity Blog: Complexity Class of the Week: Factoring»
↑ Goldreich, Oded; Wigderson, Avi (2008), «IV.20 Computational Complexity», in: Gowers, Timothy; Barrow-Green, June; Leader, Imre, The Princeton Companion to Mathematics, ISBN 978-0-691-11880-2, Princeton, New Jersey: Princeton University Press, pp. 575–604, MR 2467561 . See in particular p. 583.
↑ ^a ^b David Bressoud e Stan Wagon (2000). A Course in Computational Number Theory. [S.l.]: Key College Publishing/Springer. pp. 168–69. ISBN 978-1-930190-10-8
↑ Schnorr, Claus P. (1982). «Refined analysis and improvements on some factoring algorithms». Journal of Algorithms. 3 (2): 101–127. MR 0657269. doi:10.1016/0196-6774(82)90012-8. Cópia arquivada em 24 de setembro de 2017
↑ Seysen, Martin (1987). «A probabilistic factorization algorithm with quadratic forms of negative discriminant». Mathematics of Computation. 48 (178): 757–780. MR 0878705. doi:10.1090/S0025-5718-1987-0878705-X
↑ Lenstra, Arjen K (1988). «Fast and rigorous factorization under the generalized Riemann hypothesis» (PDF). Indagationes Mathematicae. 50 (4): 443–454. doi:10.1016/S1385-7258(88)80022-2
↑ ^a ^b Lenstra, H. W.; Pomerance, Carl (julho de 1992). «A Rigorous Time Bound for Factoring Integers» (PDF). Journal of the American Mathematical Society. 5 (3): 483–516. MR 1137100. doi:10.1090/S0894-0347-1992-1137100-0

Fontes bibliográficas

Richard Crandall e Carl Pomerance (2001). Prime Numbers: A Computational Perspective. [S.l.]: Springer. ISBN 0-387-94777-9 Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.
Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379–417.
Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3 .
Warren, Henry S. Jr. (2013). Hacker's Delight 2 ed. [S.l.]: Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8

[1] Lenstra, Arjen K. (2011), «Integer Factoring», in: van Tilborg, Henk C. A.; Jajodia, Sushil, Encyclopedia of Cryptography and Security, ISBN 978-1-4419-5905-8, Boston: Springer, pp. 611–618, doi:10.1007/978-1-4419-5906-5_455

[2] «[Cado-nfs-discuss] 795-bit factoring and discrete logarithms». Arquivado do original em 2 de dezembro de 2019

[rsa768-3] Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alexander; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman J. J.; Timofeev, Andrey; Zimmermann, Paul (2010). «Factorization of a 768-Bit RSA Modulus» (PDF). In: Rabin, Tal. Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings. Lecture Notes in Computer Science. 6223. Springer. pp. 333–350. ISBN 978-3-642-14622-0. doi:10.1007/978-3-642-14623-7_18

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

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

[6] Buhler, J. P.; Lenstra, H. W. Jr.; Pomerance, Carl (1993). «Factoring integers with the number field sieve». The development of the number field sieve. Col: Lecture Notes in Mathematics (em inglês). 1554. [S.l.]: Springer. pp. 50–94. ISBN 978-3-540-57013-4. doi:10.1007/BFb0091539. hdl:1887/2149. Consultado em 12 de março de 2021

[7] Vandersypen, Lieven M. K.; et al. (2001). «Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance». Nature. 414 (6866): 883–887. Bibcode:2001Natur.414..883V. PMID 11780055. arXiv:quant-ph/0112176. doi:10.1038/414883a

[8] Lance Fortnow (13 de setembro de 2002). «Computational Complexity Blog: Complexity Class of the Week: Factoring»

[9] Goldreich, Oded; Wigderson, Avi (2008), «IV.20 Computational Complexity», in: Gowers, Timothy; Barrow-Green, June; Leader, Imre, The Princeton Companion to Mathematics, ISBN 978-0-691-11880-2, Princeton, New Jersey: Princeton University Press, pp. 575–604, MR 2467561 . See in particular p. 583.

[Bressoud_and_Wagon-10] David Bressoud e Stan Wagon (2000). A Course in Computational Number Theory. [S.l.]: Key College Publishing/Springer. pp. 168–69. ISBN 978-1-930190-10-8

[1982-schnorr-11] Schnorr, Claus P. (1982). «Refined analysis and improvements on some factoring algorithms». Journal of Algorithms. 3 (2): 101–127. MR 0657269. doi:10.1016/0196-6774(82)90012-8. Cópia arquivada em 24 de setembro de 2017

[1987-seysen-12] Seysen, Martin (1987). «A probabilistic factorization algorithm with quadratic forms of negative discriminant». Mathematics of Computation. 48 (178): 757–780. MR 0878705. doi:10.1090/S0025-5718-1987-0878705-X

[1988-lenstra-13] Lenstra, Arjen K (1988). «Fast and rigorous factorization under the generalized Riemann hypothesis» (PDF). Indagationes Mathematicae. 50 (4): 443–454. doi:10.1016/S1385-7258(88)80022-2

[lenstra-pomerance-14] Lenstra, H. W.; Pomerance, Carl (julho de 1992). «A Rigorous Time Bound for Factoring Integers» (PDF). Journal of the American Mathematical Society. 5 (3): 483–516. MR 1137100. doi:10.1090/S0894-0347-1992-1137100-0

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]