Mostrar código-fonte de Fatoração de inteiros

{{Má tradução|1=tente encontrar a página original|data=setembro de 2024}}
{{descrição curta|Decomposição de um inteiro em um produto}}
{{unsolved|ciência da computação|A fatoração de inteiros pode ser resolvida em tempo polinomial em um computador clássico?}}
Na [[teoria dos números]], a '''fatoração de inteiros''' é a decomposição de um [[número composto]] em um produto de números inteiros menores. Se esses [[Divisor|fatores]] forem ainda mais restritos aos [[Número primo|números primos]], o processo é denominado '''fatoração prima'''.

A fatoração de números inteiros é um assunto muito antigo, que desperta cada vez mais interesse como método de criptografia de chave pública, como também a resolução de logarítmos discretos, cuja segurança depende da ineficiência desses métodos de fatoração conhecidos.<ref>{{citar livro|url=https://lume.ufrgs.br/bitstream/handle/10183/1626/000353932.pdf|título=Métodos de fatoração de números inteiros|ultimo=Antunes|primeiro=Cristiane Medina|editora=Universidade Federal do Rio Grande do Sul (UFRGS)|ano=2002|series=Matemática Aplicada|url-resumo=https://lume.ufrgs.br/handle/10183/1626}}</ref>

Quando os números são suficientemente grandes, nenhum [[algoritmo]] de [[fatoração]] de números inteiros [[Computador quântico|não quântico]] eficiente é conhecido. No entanto, não foi comprovado que não existe um algoritmo eficiente. A suposta <!-- [[:en:Computational hardness assumption]] -->dificuldade desse problema está no cerne de algoritmos amplamente usados em [[criptografia]], como o [[RSA (sistema criptográfico)|RSA]]. Muitas áreas da [[matemática]] e da [[ciência da computação]] foram utilizadas para lidar com o problema, incluindo [[Curva elíptica|curvas elípticas]], [[teoria algébrica dos números]] e [[Computador quântico|computação quântica]].

Em 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé e Paul Zimmermann fatoraram um número de 240 dígitos (795 ''bits'') (<!-- [[:en:RSA_numbers#RSA-240]] -->RSA-240) utilizando aproximadamente 900 anos-núcleo de poder de computação.<ref>{{cite web|url=https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html|urlmorta=sim|language=en|archive-url=https://web.archive.org/web/20191202190004/http://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html|archive-date=2019-12-02|title=Logaritmos discretos e fatoração de 795 ''bits''}}</ref> Os pesquisadores estimaram que um módulo RSA de 1024 ''bits'' levaria cerca de 500 vezes mais tempo.<ref name=rsa768>{{cite journal|url=http://eprint.iacr.org/2010/006.pdf|title=Fatoração de um módulo ''RSA'' de 768 ''bits''|author=Kleinjung|publisher=<!-- [[:en:International Association for Cryptologic Research]] -->Associação internacional de pesquisa criptológica|date=2010-02-18|access-date=2010-08-09|display-authors=etal|language=en}}</ref>

Nem todos os números de um determinado comprimento são igualmente difíceis de fatorar. Os exemplos mais difíceis desses problemas (para as técnicas atualmente conhecidas) são os [[Número semiprimo|semiprimo]]s, o produto de dois números primos. Quando ambos são grandes (mais de dois mil ''[[bit]]s'' de comprimento, por exemplo), escolhidos aleatoriamente e quase do mesmo tamanho (mas não muito próximos para evitar a fatoração eficiente pelo [[método de fatoração de Fermat]], por exemplo), mesmo os algoritmos de fatoração mais rápidos nos computadores mais rápidos podem levar tempo suficiente para tornar a pesquisa impraticável. Isto é, conforme o número de dígitos dos primos sendo fatorados aumenta, o número de operações necessárias para realizar a fatoração em qualquer computador aumenta drasticamente.

Muitos protocolos criptográficos são baseados na dificuldade de fatorar grandes inteiros compostos ou um problema relacionado (o [[problema RSA]], por exemplo). Um algoritmo que fatora com eficiência um [[número inteiro]] arbitrário tornaria a [[criptografia de chave pública]] baseada em [[RSA (sistema criptográfico)|RSA]] insegura.

==Decomposição prima==
[[Image:PrimeDecompositionExample.svg|right|thumb|Decomposição prima de ''n'' = 864 como {{math|2<sup>5</sup> × 3<sup>3</sup>}}]]
Pelo [[teorema fundamental da aritmética]], todo número inteiro positivo tem uma única <!-- [[:en:Prime number#Unique factorization]] -->fatoração prima. (Por convenção, 1 é o [[produto vazio]].) [[Teste de primalidade|Testar]] se o inteiro é primo pode ser feito em [[Complexidade de Tempo#Tempo Polinomial|tempo polinomial]], por exemplo, pelo [[teste de primalidade AKS]]. Se composto, entretanto, os testes de tempo polinomial não fornecem nenhuma visão sobre como obter os fatores.

Dado um algoritmo geral para fatoração de inteiros, qualquer inteiro pode ser fatorado em seus <!-- [[:en:Prime number#Unique factorization]] -->fatores primos constituintes pela aplicação repetida deste algoritmo. A situação é mais complicada com algoritmos de fatoração de propósito especial, cujos benefícios podem não ser percebidos tão bem ou mesmo de todo com os fatores produzidos durante a decomposição. Por exemplo, se {{nowrap|1=''n'' = 171 × ''p'' × ''q''}} onde {{nowrap|''p'' < ''q''}} são primos muito grandes, a [[Divisão por tentativa|divisão experimental]] produzirá rapidamente os fatores 3 e 19, mas fará ''p '' divisões para encontrar o próximo fator. Como um exemplo de contraste, se ''n'' for o produto dos primos 13729, 1372933 e 18848997161, onde {{nowrap|1=13729 × 1372933 = 18848997157}}, o método de fatoração de Fermat começará com <math>\lceil\sqrt{n}\rceil = 18848997159 </math> que imediatamente produz <math display="inline">b = \sqrt{a^2-n} = \sqrt{4} = 2b </math> e, portanto, os fatores {{nowrap|1=''a'' − ''b'' = 18848997157}} e {{nowrap|1=''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 <math display="inline">\lceil\sqrt{18848997157}\rceil = 137292 </math> para ''a'' está longe de 1372933.

==Estado da arte atual==
<!-- {{See also|:en:integer factorization records}} -->
Entre os números de ''bit'' ''b'', os mais difíceis de fatorar na prática usando os algoritmos existentes são aqueles que são produtos de dois primos de tamanho semelhante. Por esse motivo, esses são os números inteiros usados em aplicativos criptográficos. O maior semiprimo já fatorado era <!-- [[:en:RSA numbers#RSA-250]] -->
RSA-250, um número de 829 ''bits'' com 250 dígitos decimais, em fevereiro de 2020. O tempo total de computação foi de aproximadamente 2.700 anos-núcleo de computação usando [[Intel]] [[Xeon]] Gold 6130 a 2,1 GHz. Como todos os registros de fatoração recentes, esta fatoração foi concluída com uma implementação altamente otimizada da <!-- [[:en:General number field sieve]] -->peneira de campo de número geral executada em centenas de máquinas.

===Dificuldade e complexidade===

Não foi publicado nenhum [[algoritmo]] que pode fatorar todos os inteiros em [[Complexidade de Tempo#Tempo Polinomial|tempo polinomial]], ou seja, que pode fatorar um número ''n'' de ''bits'' ''b'' no tempo [[Grande-O|O]](''b''<sup>''k''</sup>) para alguma constante ''k''. Nem a existência nem a inexistência de tais algoritmos foram provadas, mas geralmente se suspeita que eles não existem e, portanto, o problema não está na classe P.<ref>{{citation|last=Krantz|first=Steven G.|author-link=Steven George Krantz|doi=10.1007/978-0-387-48744-1|isbn=978-0-387-48908-7|location=Nova Iorque|mr=2789493|page=203|publisher=Springer|title=A prova está no pudim: a natureza mutável da prova matemática|url=https://books.google.com/books?id=mMZBtxVZiQoC&pg=PA203|year=2011|language=en}}</ref><ref>{{citation|last1=Arora |first1=Sanjeev|author1-link=Sanjeev Arora|last2=Barak|first2=Boaz|doi=10.1017/CBO9780511804090|isbn=978-0-521-42426-4|location=Cambridge|mr=2500087|page=230|publisher=Imprensa universitária de Cambridge|title=Complexidade computacional|url=https://books.google.com/books?id=nGvI7cOuOOQC&pg=PA230|year=2009|language=en}}</ref> O problema está claramente na classe NP, mas geralmente se suspeita que não seja [[NP-completo]], embora isso não tenha sido provado.<ref>{{citation|last1=Goldreich|first1=Oded|author1-link=Oded Goldreich|last2=Wigderson|first2=Avi|author2-link=Avi Wigderson|editor1-last=Gowers|editor1-first=Timothy|editor1-link=William Timothy Gowers|editor2-last=Barrow-Green|editor2-first=June|editor2-link=June Barrow-Green|editor3-last=Leader|editor3-first=Imre<!-- |editor3-link=:en:Imre Leader -->|contribution=IV.20 Complexidade computacional|isbn=978-0-691-11880-2|location=Princeton, Nova Jérsei|mr=2467561|pages=575 à 604|publisher=Imprensa universitária de Princeton|title=O companheiro de Princeton para a matemática|year=2008|language=en}}. Ver [https://books.google.com/books?id=ZOfUsvemJDMC&pg=PA583 p.&nbsp;583] em particular.</ref>

Existem algoritmos publicados que são mais rápidos que O((1 + ''ε'')<sup>''b''</sup>) para todos os ''ε'' positivos, ou seja, <!-- [[:en:Time_complexity#Sub-exponential_time]] -->subexponenciais. Em 12 de março de 2021, o algoritmo com melhor tempo de execução assintótico teórico foi o peneira de campo de número geral ([[Campo de número de peneira geral|''GNFS'']]), publicado pela primeira vez em 1993,<ref>{{cite book|last1=Buhler|first1=J. P.|last2=Lenstra|first2=H. W. Jr.|last3=Pomerance|first3=Carl|title=Fatoração de números inteiros com a peneira de campo de número|date=1993|publisher=Springer|isbn=978-3-540-57013-4|pages=50 à 94|doi=10.1007/BFb0091539|edition=Notas de aula em matemática, volume 1554 |url=https://doi.org/10.1007/BFb0091539 |access-date=12-03-2021|language=en}}</ref> rodando em um número ''n'' de ''bits'' ''b'' no tempo:

:<math>\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right).</math>

Para os computadores atuais, o ''GNFS'' é o melhor algoritmo publicado para ''n'' grandes (mais de cerca de 400 ''bits''). Entretanto, [[Peter Shor]] descobriu, em 1994, um algoritmo para um [[computador quântico]] que resolve isso em tempo polinomial. Isso terá implicações significativas para a criptografia se a computação quântica se tornar escalável. O [[algoritmo de Shor]] leva apenas tempo {{math|O(''b''<sup>3</sup>)}} e espaço O(''b'') nas entradas de número de ''bits'' ''b''. Em 2001, o algoritmo de Shor foi implementado pela primeira vez, usando técnicas de <!-- [[:en:Nuclear magnetic resonance]] -->ressonância magnética nuclear (''NMR'') em moléculas que fornecem 7 ''qubits''.<ref>{{cite journal|doi=10.1038/414883a|title=Realização experimental do algoritmo de fatoração quântica de Shor usando ressonância magnética nuclear|journal=[[Nature]]|volume=414|pages=883 à 887|year=2001|last=Vandersypen|first=Lieven M. K.|issue=6866|display-authors=etal|arxiv=quant-ph/0112176|pmid=11780055|bibcode=2001Natur.414..883V<!-- |s2cid=4400832 -->|language=en}}</ref>

Não se sabe exatamente quais [[Classe de complexidade|classes de complexidade]] contêm a [[Problema de decisão|versão de decisão]] do problema de fatoração de inteiros (isto é: {{mvar|n}} tem um fator menor que {{mvar|k}}?). Se sabe que está tanto em [[NP (complexidade)|NP]] quanto em [[co-NP]], o que significa que as respostas "sim" e "não" podem ser verificadas em tempo polinomial. Uma resposta "sim" pode ser certificada exibindo uma fatoração {{nowrap|1=''n'' = ''d''(''n''/''d'')}} com {{nowrap|''d'' ≤ ''k''}}. Uma resposta "não" pode ser certificada exibindo a fatoração de ''n'' em primos distintos, todos maiores do que ''k''. Se pode 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 há apenas uma série possível de números primos crescentes que serão aceitos, o que mostra que o problema está tanto em [[UP (complexidade)|UP]] quanto em co-UP.<ref>{{cite web|author=Lance Fortnow|title=Blogue de complexidade computacional: aula de complexidade da semana: fatoração|date=2002-09-13|url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html|language=en}}</ref> É conhecido por estar no [[BQP]] por causa do algoritmo de Shor.

Se suspeita que o problema esteja fora de todas as três classes de complexidade P, NP-completo e [[co-NP-completo]]. Portanto, é um candidato à classe de complexidade [[NP-Intermediário|NP-intermediário]]. Se pudesse ser provado ser NP-completo ou co-NP-completo, isso implicaria NP = co-NP, um resultado muito surpreendente e, portanto, a fatoração inteira é amplamente suspeita de estar fora de ambas as classes. Muitas pessoas tentaram encontrar algoritmos clássicos de tempo polinomial para ele e falharam e, portanto, é amplamente suspeito de estar fora de P.

Em contraste, o problema de decisão "''n'' é um número composto?" (ou de forma equivalente: "''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 [[Algoritmo probabilístico|algoritmos probabilísticos]] que podem testar a primalidade muito rapidamente na prática, se alguém estiver disposto a aceitar uma possibilidade cada vez menor de erro. A facilidade do [[teste de primalidade]] é uma parte crucial do algoritmo [[RSA (sistema criptográfico)|RSA]], pois é necessário encontrar grandes números primos para começar.

==Algoritmos de fatoração==
===Finalidade especial===
O tempo de execução de um algoritmo de fatoração de propósito especial 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 especial são os algoritmos de ''categoria 1'' ou ''primeira categoria'', cujo tempo de execução depende do tamanho do menor [[fator primo]]. Dado um número inteiro de forma desconhecida, esses métodos são geralmente aplicados antes dos métodos de uso geral para remover pequenos fatores.<ref name="Bressoud and Wagon">{{cite book|author=<!-- [[:en:David Bressoud]] -->David Bressoud e <!-- [[:en:Stan Wagon]] -->Stan Wagon|year=2000|title=Um curso em teoria dos números computacionais|publisher=Key College Publishing/Springer|isbn=978-1-930190-10-8|pages=[https://archive.org/details/courseincomputat0000bres/page/168 168 e 169]<!-- |url-access=registration -->|url= https://archive.org/details/courseincomputat0000bres/page/168|language=en}}</ref> Por exemplo, a [[Divisão por tentativa|divisão experimental]] ingênua é um algoritmo de categoria 1.

* [[Divisão por tentativa|divisão experimental]]
* <!-- [[:en:Wheel factorization]] -->Fatoração de roda
* <!-- [[:en:Pollard's rho algorithm]] -->Algoritmo ''rô'' de Pollard
* <!-- [[:en:Algebraic-group factorisation algorithm]] -->Algoritmos de fatoração de [[grupo algébrico]], entre os quais estão o <!-- [[:en:Pollard's p − 1 algorithm]] -->algoritmo ''p'' - 1 de Pollard, o [[Algoritmo p + 1 de Williams|algoritmo ''p'' + 1 de Williams]] e a <!-- [[:en:Lenstra elliptic-curve factorization]] -->fatoração de curva elíptica de Lenstra
* [[Método de fatoração de Fermat]]
* <!-- [[:en:Euler's factorization method]] -->Método de fatoração de Euler
* <!-- [[:en:Special number field sieve]] -->Peneira de campo de número especial

===Propósito geral===
Um algoritmo de fatoração de propósito geral, também conhecido como algoritmo de ''categoria 2'', ''segunda categoria'' ou da ''família [[Maurice Kraitchik|Kraitchik]]'',<ref name="Bressoud and Wagon"/> tem um tempo de execução que depende exclusivamente do tamanho do inteiro a ser fatorado. Este é o tipo de algoritmo usado para fatorar os <!-- [[:en:RSA numbers]] -->números RSA. A maioria dos algoritmos de fatoração de propósito geral é baseada no método de <!-- [[:en:Congruence of squares]] -->congruência de quadrados.

* <!-- [[:en:Dixon's factorization method]] -->Método de fatoração de Dixon
* <!-- [[:en:Continued fraction factorization]] -->Fatoração de [[fração contínua]] (''CFRAC'')
* <!-- [[:en:Quadratic sieve]] -->Peneira quadrática
* <!-- [[:en:Rational sieve]] -->Peneira racional
* [[Campo de número de peneira geral|Peneira de campo de número geral]]
* <!-- [[:en:Shanks's square forms factorization]] -->Fatoração de formas quadradas de Shanks (''SQUFOF'')

===Outros algoritmos notáveis===
* [[Algoritmo de Shor]], para computadores quânticos

==Tempo de execução heurística==
Na teoria dos números, existem muitos algoritmos de fatoração de inteiros que heuristicamente têm [[Complexidade de Tempo|tempo de execução]] esperado

:<math>L_n\left[\tfrac12,1+o(1)\right]=e^{(1+o(1))\sqrt{(\log n)(\log \log n)}}</math>

em [[Grande-O#Notação_o-pequeno|o-pequeno]] e <!-- [[:en:L-notation]] -->[[notação L]]. Alguns exemplos desses algoritmos são o <!-- [[:en:Lenstra elliptic-curve factorization]] -->método de curva elíptica e a <!-- [[:en:Quadratic sieve]] -->peneira quadrática. Outro algoritmo é o '''método de relações de grupo de classes''' proposto por Schnorr, <ref name=1982-schnorr>{{cite journal|last=Schnorr|first=Claus P.|year=1982|title=Análise refinada e melhorias em alguns algoritmos de fatoração|journal=Jornal de algoritmos|volume=3|pages=101 à 127|doi=10.1016/0196-6774(82)90012-8|issue=2| mr=0657269|url=http://www.dtic.mil/get-tr-doc/pdf?AD=ADA096348|language=en}}</ref> Seysen<ref name=1987-seysen>{{cite journal|last=Seysen|first=Martin|year=1987|title=Um algoritmo de fatoração probabilística com formas quadráticas de discriminante negativo|journal=Matemática da computação|volume=48|pages=757 à 780|doi=10.1090/S0025-5718-1987-0878705-X|issue=178|mr=0878705<!-- |doi-access=free -->|language=en}}</ref> e Lenstra,<ref name=1988-lenstra>{{cite journal|last=Lenstra|first=Arjen K|year=1988|title=Fatoração rápida e rigorosa sob a hipótese generalizada de Riemann|journal=Análise Matemática|volume=50|issue=4|pages=443 à 454|doi=10.1016/S1385-7258(88)80022-2|language=en}}</ref> que eles provaram apenas assumindo a [[hipótese generalizada de Riemann]] (''GRH'') não comprovada.

==Tempo de execução rigoroso==
O algoritmo probabilístico Schnorr-Seysen-Lenstra foi rigorosamente comprovado por Lenstra e Pomerance<ref name=lenstra-pomerance/> para ter tempo de execução esperado <math>L_n\left[\tfrac12,1+o(1)\right]</math> substituindo a suposição ''GRH'' pelo uso de multiplicadores. O algoritmo usa o [[Grupo de classes do ideal|grupo de classes]] de [[Forma quadrática|formas quadráticas]] binárias positivas do <!-- [[:en:Discriminant#Quadratic_forms]] -->discriminante Δ denotado por ''G''<sub>Δ</sub>. ''G''<sub>Δ</sub> é o conjunto de triplos de inteiros (''a'', ''b'', ''c'') em que esses inteiros são primos relativos.

===Algoritmo Schnorr-Seysen-Lenstra===
Dado um número inteiro ''n'' que será fatorado, onde ''n'' é um número inteiro positivo ímpar maior que uma certa constante. Neste algoritmo de fatoração, o discriminante Δ é escolhido como um múltiplo de ''n'', {{nowrap|1=Δ = −''dn''}}, onde ''d'' é algum multiplicador positivo. O algoritmo espera que para um ''d'' existam formas <!-- [[:en:Smooth number]] -->suaves suficientes em G<sub>Δ</sub>. 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''<sub>Δ</sub> o conjunto de todos os primos ''q'' com o [[símbolo de Kronecker]] <math>\left(\tfrac{\Delta}{q}\right)=1</math>. Construindo um conjunto de [[Conjunto gerador de um grupo|geradores]] de ''G''<sub>Δ</sub> e formas primas ''f''<sub>q</sub> de ''G''<sub>Δ</sub> com ''q'' em ''P''<sub>Δ</sub>, uma sequência de relações entre o conjunto de geradores e ''f''<sub>q</sub> é produzida. O tamanho de ''q'' pode ser limitado por <math>c_0(\log|\Delta|)^2</math> para alguma constante <math>c_0</math>.

A relação que se usará é uma relação entre o produto de potências que é igual ao [[Grupo (matemática)|elemento neutro]] de ''G''<sub>Δ</sub>. Essas relações serão usadas para construir a chamada forma ambígua de ''G''<sub>Δ</sub>, que é um elemento de ''G''<sub>Δ</sub> da ordem de divisão 2. Calculando a fatoração correspondente de Δ e tomando um [[Máximo divisor comum|mdc]], esta forma ambígua fornece a fatoração prima completa de ''n'' . Este algoritmo possui estas etapas principais:

Seja ''n'' o número a ser fatorado.
# Seja Δ um número inteiro negativo com {{nowrap|1=Δ = −''dn''}}, onde ''d'' é um multiplicador e Δ é o discriminante negativo de alguma forma quadrática.
# Pega os primeiros ''t'' primos <math>p_1=2,p_2=3,p_3=5, \dots ,p_t</math>, para algum <math>t\in{\mathbb N}</math>.
# Seja <math>f_q</math> uma forma primária aleatória de ''G''<sub>Δ</sub> com <math>\left(\tfrac{\Delta}{q}\right)=1</math>.
# Encontra um conjunto gerador ''X'' de ''G''<sub>Δ</sub>
# Coleta uma sequência de relações entre o conjunto ''X'' e {{nowrap|{''f<sub>q</sub> : q'' ∈ ''P''<sub>Δ</sub>}}} satisfazendo: <math>\left(\prod_{x \in X_{}} x^{r(x)}\right).\left(\prod_{q \in P_\Delta} f^{t(q)}_{q}\right) = 1</math>
# Constrói uma forma ambígua {{tmath|(a, b, c)}} que é um elemento ''f'' ∈ ''G''<sub>Δ</sub> de ordem dividindo 2 para obter uma fatoração coprima do maior divisor ímpar de Δ em que <math>\Delta = -4ac \text{ or } a(a - 4c) \text{ or } (b - 2a)(b + 2a)</math>
# Se a forma ambígua fornece uma fatoração de ''n'', então para, caso contrário, encontra outra forma ambígua até que a fatoração de ''n'' seja encontrada. Para evitar a geração de formas ambíguas inúteis, constrói o grupo <!-- [[:en:Sylow theorems]] -->2-Sylow Sll<sub>2</sub>(Δ) de ''G''(Δ).

Para obter um algoritmo de fatoração de qualquer inteiro positivo, é necessário adicionar algumas etapas a esse algoritmo, como a divisão experimental e o <!-- [[:en:Adleman–Pomerance–Rumely primality test]] -->teste de soma de Jacobi.

===Tempo de execução previsto===
O algoritmo, conforme declarado, é um [[algoritmo probabilístico]], pois faz escolhas aleatórias. Seu tempo de execução esperado é no máximo <math>L_n\left[\tfrac12,1+o(1)\right]</math>.<ref name=lenstra-pomerance>{{cite journal|first1=H. W.|last1=Lenstra|first2=Carl|last2=Pomerance|date=07-1992|title=Um limite de tempo rigoroso para números inteiros de fatoração|journal=Jornal da sociedade matemática americana|volume=5|pages=483 à 516|url=https://www.ams.org/journals/jams/1992-05-03/S0894-0347-1992-1137100-0/S0894-0347-1992-1137100-0.pdf|doi=10.1090/S0894-0347-1992-1137100-0|issue=3|mr=1137100<!-- |doi-access=free -->|language=en}}</ref>

==Ver também==
<!-- * [[:en:Bach's algorithm|Algoritmo de Bach]] para gerar números aleatórios com suas fatorações
* [[:en:Fundamental_theorem_of_arithmetic#Canonical_representation_of_a_positive_integer|Representação canônica de um número inteiro positivo]] 
* [[:en:Partition (number theory)]] -->
* [[Fatoração]]
* [[Partição multiplicativa]]
==Notas==
{{Reflist}}<!--adicionado sob o cabeçalho de referências por edição assistida por script-->

==Referências==
* {{cite book|author=[[Richard Crandall]] e [[Carl Pomerance]]|year=2001|title=Números primos: uma perspectiva computacional|publisher= Springer|isbn=0-387-94777-9|language=en}} Capítulo 5: Algoritmos de fatoração exponencial, páginas 191 à 226. Capítulo 6: Algoritmos de fatoração subexponencial, pàginas 227 à 284. Seção 7.4: Método da curva elíptica, pàginas 301 à 313.
* [[Donald Knuth]]. ''[[The Art of Computer Programming|A arte da programação de computadores]]'', Volume 2: ''Algoritmos seminuméricos'', Terceira edição. Addison-Wesley, 1997. {{ISBN|0-201-89684-2}}. Seção 4.5.4: Fatoração em primos, páginas 379 à 417.
* {{cite book|author=Samuel S. Wagstaff Jr.|title=A alegria de fatorar|publisher=Sociedade americana de matemática|location=Providence, RI|year=2013|isbn=978-1-4704-1048-3|url=https://www.ams.org/bookpages/stml-68<!-- |author-link=:en:Samuel S. Wagstaff Jr. -->|language=en}}.
* {{Cite book|title=<!-- [[:en:Hacker's Delight]] -->Deleite do ''hacker''|first=Henry S.|last=Warren Jr.|year=2013|edition=2|publisher=[[Addison Wesley]] - <!-- [[:en:Pearson Education, Inc.]] -->Pearson Education|isbn=978-0-321-84268-8|language=en}}

==Ligações externas==
*[http://sourceforge.net/projects/msieve/ msieve] - SIQS e NFS - ajudou a completar algumas das maiores fatorações públicas conhecidas (em inglês)
*Richard P. Brent, "Progressos recentes e perspectivas para algoritmos de fatoração inteira", ''computação e combinatória'', 2000, páginas 3 à 22. [http://citeseer.ist.psu.edu/327036.html ''download''] (em inglês)
* [[Manindra Agrawal]], Neeraj Kayal, Nitin Saxena, "Os primos estão em ''P''." Procedimentos da matemática 160(2): 781 à 793 (2004) ([http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PDF 2005] em inglês)
* [[:en:RSA_numbers#RSA-240|RSA-240]], na Wikipédia Anglofônica
* [[Eric W. Weisstein]], [http://mathworld.wolfram.com/news/2005-11-08/rsa-640/ “''Notícias da manchete do mundo da matemática'' “RSA-640 fatorado”, 8 de novembro de 2005 (em inglês)]

<!-- {{Computational hardness assumptions}}
{{Number theoretic algorithms|state=collapsed}}
{{Divisor classes}} -->
{{Controle de autoridade}}

[[Categoria:Algoritmos de fatorização de inteiros]]