Fatoração inteira

Na teoria dos números, a fatoração inteira é a decomposição, quando possível, de um inteiro positivo em um produto de inteiros menores. Se os fatores forem ainda mais restritos a números primos, o processo é chamado de fatoração de primos e inclui o teste se o inteiro dado é primo (neste caso, tem-se um "produto" de um único fator).

Quando os números são suficientemente grandes, nenhum algoritmo eficiente de fatoração inteira não quântica é conhecido. No entanto, não foi provado que tal algoritmo não existe. A suposta dificuldade desse problema é importante para os algoritmos usados em criptografia, como a criptografia de chave pública RSA e a assinatura digital RSA. Muitas áreas da matemática e da ciência da computação foram trazidas para resolver o problema, incluindo curvas elípticas, teoria algébrica dos números e 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) (RSA-240) utilizando aproximadamente 900 anos principais de poder de computação. Os pesquisadores estimaram que um módulo RSA de 1024 bits levaria cerca de 500 vezes mais tempo.

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 o primo mais rápido algoritmos de fatoração nos computadores mais rápidos podem levar tempo suficiente para tornar a pesquisa impraticável; ou seja, à medida que aumenta o número de dígitos do inteiro sendo fatorado, 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 inteiros compostos grandes ou um problema relacionado—por exemplo, o problema RSA. Um algoritmo que fatora eficientemente um número inteiro arbitrário tornaria a criptografia de chave pública baseada em RSA insegura.

Decomposição primária

Primeira decomposição de n = 864 2⁵ × 3³

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

Dado um algoritmo geral para a fatoração do inteiro, qualquer inteiro pode ser fatorado em seus fatores principais 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 realizados também ou mesmo com os fatores produzidos durante a decomposição. Por exemplo, se n = 171 × p × q Onde? p < q são primos muito grandes, a divisão experimental produzirá rapidamente os fatores 3 e 19, mas tomará p divisões para encontrar o próximo fator. Como exemplo contrastante, se n é o produto dos primos 13729, 1372933, e 18848997161, onde 13729 × 1372933 = 18848997157, método de fatoração de Fermat começará com ⌈n⌉= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =18848997159{displaystyle leftlceil {sqrt {n}}rightrceil =18848997159} que imediatamente cede b)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =um2- Sim. - Sim. n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =4= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2b)- Sim. {a^{2}-n}}={sqrt {4}}=2b} e daí os fatores um - Sim. b) = 18848997157 e um + b) = 18848997161. Embora estes sejam facilmente reconhecidos como compostos e primos, respectivamente, o método de Fermat levará muito mais tempo para fatorar o número composto porque o valor inicial de ⌈18848997157⌉= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =137292{textstyle leftlceil {sqrt {18848997157}},rightrceil =137292} para um não está perto de 1372933.

Estado atual da arte

Entre os números de b bits, os mais difíceis de fatorar na prática usando 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 desses semiprime já fatorado foi 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, essa fatoração foi concluída com uma implementação altamente otimizada da peneira de campos numéricos geral executada em centenas de máquinas.

Dificuldade e complexidade

Não foi publicado nenhum algoritmo que possa fatorar todos os inteiros em tempo polinomial, ou seja, que possa fatorar um número de b bits n no tempo O( b^k) 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 existam e, portanto, que o problema não esteja na classe P. O problema está claramente na classe NP, mas geralmente se suspeita que seja não é NP-completo, embora isso não tenha sido comprovado.

Existem algoritmos publicados que são mais rápidos que O((1 + ε)^b) para todos os ε, ou seja, subexponencial. A partir de 2022, o algoritmo com melhor tempo de execução assintótica teórica é o general number field sieve (GNFS), publicado pela primeira vez em 1993, rodando em um número b-bit n em tempo:

exp⁡ ⁡ ((6493+o(1))(I⁡ ⁡ n)13(I⁡ ⁡ I⁡ ⁡ n)23).{displaystyle exp left(left({sqrt[{3}]{frac {64}{9}}}+o(1)right)(ln n)^{frac {1}{3}}(ln ln n)^{frac {2}{3}}right). ?

Para os 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. 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 O(b³) e espaço O(b) em b entradas de número de bits. Em 2001, o algoritmo de Shor foi implementado pela primeira vez, usando técnicas de RMN em moléculas que fornecem 7 qubits.

Não se sabe exatamente quais classes de complexidade contêm a versão de decisão do problema de fatoração inteira (isto é: n tem um fator menor que k?). Sabe-se que está em NP e co-NP, o que significa que ambos "sim" e "não" respostas podem ser verificadas em tempo polinomial. Uma resposta de "sim" pode ser certificado exibindo uma fatoração n = d(n/d) com d ≤ k. Uma resposta de "não" pode ser certificado 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 depois multiplicá-los para obter n. O teorema fundamental da aritmética garante que há apenas uma sequência possível de primos crescentes que será aceita, o que mostra que o problema está tanto em UP quanto em co-UP. É conhecido por estar no BQP por causa do algoritmo de Shor.

Suspeita-se que o problema esteja fora de todas as três classes de complexidade P, NP-completo e co-NP-completo. É, portanto, um candidato para a classe de complexidade NP-intermediária. 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 dessas duas classes.

Em contraste, o problema de decisão "É n um número composto?" (ou equivalentemente: "É 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 extremamente 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

Para fins especiais

O tempo de execução de um algoritmo de fatoração 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 importante subclasse 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 inteiro de forma desconhecida, esses métodos geralmente são aplicados antes dos métodos de uso geral para remover pequenos fatores. Por exemplo, a divisão de tentativa ingênua é um algoritmo de categoria 1.

• Divisão de avaliação
• Factorização da roda
• O algoritmo de Rho de Pollard, que tem dois sabores comuns para identificar ciclos de grupo: um por Floyd e um por Brent.
• Algoritmos de fatoração de grupo algébraico, entre os quais estão o algoritmo p − 1 de Pollard, o algoritmo p + 1 de Williams e a fatoração da curva elíptica de Lenstra
• Método de fatoração de Fermat
• Método de fatoração de Euler
• Número especial de sieve

Uso geral

Um algoritmo de fatoração de uso geral, também conhecido como algoritmo de Categoria 2, Segunda categoria ou Kraitchik família, tem um tempo de execução que depende apenas do tamanho do inteiro a ser fatorado. Este é o tipo de algoritmo usado para fatorar números RSA. A maioria dos algoritmos de fatoração de uso geral são baseados no método da congruência dos quadrados.

• O algoritmo de Dixon
• Fatorização contínua da fração (CFRAC)
• Peneira quadrada
• Maneira racional
• Número geral de campo sieve
• Fatorizaçã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 inteira que heuristicamente têm tempo de execução esperado

LnNão.12,1+o(1)]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =e(1+o(1))(log⁡ ⁡ n)(log⁡ ⁡ log⁡ ⁡ n)Não. L_{n}left[{tfrac {1}{2}},1+o(1)right]=e^{(1+o(1)){sqrt {(log n)(log log nn)}}}}

em notação o minúsculo e L. Alguns exemplos desses algoritmos são o método da curva elíptica e a peneira quadrática. Outro algoritmo desse tipo é o método de relações de grupo de classe proposto por Schnorr, Seysen e Lenstra, que eles provaram apenas assumindo a Hipótese Generalizada de Riemann (GRH) não comprovada.

Tempo de execução rigoroso

O algoritmo probabilístico de Schnorr-Seysen-Lenstra foi rigorosamente provado por Lenstra e Pomerance ter esperado tempo de execução LnNão.12,1+o(1)]Não. L_{n}left[{tfrac {1}{2}},1+o(1)right]} substituindo o pressuposto GRH pelo uso de multiplicadores. O algoritmo usa o grupo de classes de formas quadraticas binárias positivas de discriminante Δ denotado por G_?. G_? é o conjunto de triplos de inteiros (um, b), c) em que esses inteiros são primo relativo.

Algoritmo de 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 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.

Denota por P_? o conjunto de todos os primos q com símbolo de Kronecker (? ? q)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle left({tfrac) - Sim.. Construindo um conjunto de geradores de G_? e formas primo f_q de G_? com q em P_? uma sequência de relações entre o conjunto de geradores e f_q são produzidos. O tamanho de q pode ser limitado por c0(log⁡ ⁡ |? ? |)2{displaystyle c_{0}(log) |Delta |)^{2}} para alguma constante c0{displaystyle c_{0}}.

A relação que será utilizada é uma relação entre o produto de potências que é igual ao elemento neutro de G_Δ. Essas relações serão usadas para construir a 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 primária completa de n. Este algoritmo tem estas etapas principais:

Seja n o número a ser fatorado.

1. Deixe Δ ser um inteiro negativo com Δ = −Dn, onde D é um multiplicador e Δ é o discriminante negativo de alguma forma quadrática.
2. Toma. ) primeiros primos p1= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2,p2= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =3,p3= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =5,...... ,p)Não. p_{1}=2,p_{2}=3,p_{3}=5,ldotsp_{t}}, para alguns )∈ ∈ N{displaystyle tin {mathbb Não..
3. Vamos. fq{displaystyle f_{q}} ser uma forma principal aleatória de G_? com (? ? q)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{textstyle left({frac) - Sim..
4. Encontre um conjunto gerador X de G_?
5. Coletar uma sequência de relações entre o conjunto X e (f_q: ∈ P_?} satisfazendo: (? ? x∈ ∈ XxR(x)).(? ? q∈ ∈ P? ? fq)(q))= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{textstyle left(prod _{xin X_{}}x^{r(x)}right).left(prod _{qin P_{Delta }}f_{q}^{t(q)}right)=1}
6. Construir uma forma ambígua (um,b),c)(a,b,c)} que é um elemento f ∈ G_? de ordem dividindo 2 para obter uma fatoração coprime do maior divisor ímpar de Δ em que ? ? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 4umcouum(um- Sim. - Sim. 4c)ou(b)- Sim. - Sim. 2um)(b)+2um){displaystyle Delta =-4ac{text{ or }}a(a-4c){text{ or }}(b-2a)(b+2a)}
7. Se a forma ambígua fornece uma fatoração de n então parar, caso contrário encontrar outra forma ambígua até a fatoração n é encontrado. A fim de evitar formas ambíguas inúteis de gerar, construir o grupo 2-Sylow Sll₂(Δ) de G(Δ).

Para obter um algoritmo para fatorar qualquer inteiro positivo, é necessário adicionar algumas etapas a esse algoritmo, como a divisão de tentativas e o teste de soma de Jacobi.

Tempo de execução esperado

O algoritmo como afirmado é um algoritmo probabilístico como ele faz escolhas aleatórias. Seu tempo de execução esperado é no máximo LnNão.12,1+o(1)]Não. L_{n}left[{tfrac {1}{2}},1+o(1)right]}.