Fatoração de inteiros - Integer factorization

Problema não resolvido na ciência da computação :

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

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

Na teoria dos números , a fatoração de inteiros é a decomposição de um número composto em um produto de inteiros menores. Se esses fatores forem ainda mais restritos a números primos , o processo é chamado de fatoração de primos .

Quando os números são suficientemente grandes, nenhum algoritmo de fatoração de números inteiros não quânticos eficiente é conhecido. No entanto, não foi comprovado que não existe um algoritmo eficiente. A suposta dificuldade desse problema está no cerne de algoritmos amplamente usados em criptografia , como RSA . Muitas áreas da matemática e da ciência da computação foram utilizadas para lidar com o problema, incluindo curvas elípticas , teoria dos números algébricos 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-núcleo de poder de computação. Os pesquisadores estimaram que um módulo RSA de 1024 bits levaria cerca de 500 vezes mais.

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 semiprimes , o produto de dois números primos. Quando ambos são grandes, por exemplo, mais de dois mil bits de comprimento, escolhidos aleatoriamente e quase 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 primos mais rápidos no 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 - por exemplo, o problema RSA . Um algoritmo que fatora com eficiência um número inteiro arbitrário tornaria a criptografia de chave pública baseada em RSA insegura.

Decomposição primária

Decomposição primária de n = 864 como

25 \times 3 3

Pelo teorema fundamental da aritmética , todo número inteiro positivo tem uma única fatoração primo . (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 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 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 n = 171 × p × q onde p < q são primos muito grandes, a 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 é o produto dos primos 13729, 1372933 e 18848997161, onde 13729 × 1372933 = 18848997157 , o método de fatoração de Fermat começará com o que imediatamente resulta e, portanto, os fatores a - b = 18848997157 e a + b = 18848997161 . Embora esses 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 para a está longe de ser 1372933. ${\ displaystyle \ lceil {\ sqrt {n}} \ rceil = 18848997159}$ ${\ textstyle b = {\ sqrt {a ^ {2} -n}} = {\ sqrt {4}} = 2b}$ ${\ textstyle \ lceil {\ sqrt {18848997157}} \ rceil = 137292}$

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 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 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, esta fatoração foi concluída com uma implementação altamente otimizada da peneira de campo de número geral executada em centenas de máquinas.

Dificuldade e complexidade

Nenhum algoritmo foi publicado que pode fatorar todos os inteiros em tempo polinomial , ou seja, que pode fatorar um número b- bit n no tempo O ( b ^k ) para alguma constante k . Nem a existência nem a inexistência de tais algoritmos foi provada, mas geralmente suspeita-se que eles não existem e, portanto, que o problema não está na classe P. O problema está claramente na classe NP, mas geralmente suspeita-se que ele não é NP-completo , embora isso não tenha sido provado.

Existem algoritmos publicados que são mais rápidos que O ((1 + ε ) ^b ) para todos os ε positivos , ou seja, subexponenciais . Em 2021-03-12, o algoritmo com melhor tempo de execução assintótico teórico é a peneira de campo de número geral ( GNFS ), publicada pela primeira vez em 1993, rodando em um número b- bit n no tempo:

{\ 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, GNFS é o melhor algoritmo publicado para n grandes (mais de cerca de 400 bits). Para um computador quântico , entretanto, 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 $O (b 3)$ tempo e O ( b ) espaço nas entradas de número de b- bits. Em 2001, o algoritmo de Shor foi implementado pela primeira vez, usando técnicas de NMR 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 de inteiros (isto é: $n$ tem um fator menor que $k$ ?). Sabe-se que está tanto em 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 n = d ( n / d ) com d ≤ k . Uma resposta "não" pode ser certificada exibindo a fatoração de n em primos distintos, todos maiores do 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 há apenas uma sequência possível de números 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 à classe de complexidade intermediária NP . 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 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 cada vez menor de erro. 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 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. Por exemplo, a divisão experimental ingênua é um algoritmo de categoria 1.

Propósito geral

Um algoritmo de fatoração de propósito geral, também conhecido como algoritmo de categoria 2 , segunda categoria ou família Kraitchik , 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 números RSA . A maioria dos algoritmos de fatoração de propósito geral é baseada no método de congruência de quadrados .

Algoritmo de Dixon
Fatoração de fração contínua (CFRAC)
Peneira quadrática
Peneira racional
Crivo de campo de número geral
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 têm tempo de execução esperado heuristicamente

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

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

Tempo de execução rigoroso

O algoritmo probabilístico Schnorr-Seysen-Lenstra foi rigorosamente comprovado por Lenstra e Pomerance para ter tempo de execução esperado , substituindo a suposição GRH pelo uso de multiplicadores. O algoritmo usa o grupo de classes de formas quadráticas binárias positivas do discriminante Δ denotado por G _Δ . G _Δ é o conjunto de triplos de inteiros ( a , b , c ) em que esses inteiros são primos relativos. ${\ displaystyle L_ {n} \ left [{\ tfrac {1} {2}}, 1 + o (1) \ right]}$

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 , Δ = - 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.

Denote por P _Δ o conjunto de todos os primos q com o símbolo de Kronecker . Construindo um conjunto de geradores de G _Δ e formas primos f _q de G _Δ com q em P _Δ uma seqüência de relações entre o conjunto de geradores e f _q é produzida. O tamanho de q pode ser limitado por alguma constante . ${\ displaystyle \ left ({\ tfrac {\ Delta} {q}} \ right) = 1}$ ${\ displaystyle c_ {0} (\ log | \ Delta |) ^ {2}}$ ${\ displaystyle c_ {0}}$

A relação que se usará é uma relação entre o produto das potências 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 _Δ da ordem de divisão 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 possui estas etapas principais:

Seja n o número a ser fatorado.

Seja Δ um número inteiro negativo com Δ = - dn , onde d é um multiplicador e Δ é o discriminante negativo de alguma forma quadrática.
Tome as t primeiros números primos , para alguns . ${\ displaystyle p_ {1} = 2, p_ {2} = 3, p_ {3} = 5, \ dots, p_ {t}}$ ${\ displaystyle t \ in {\ mathbb {N}}}$
Let Ser uma forma primária aleatória de G _Δ com . ${\ displaystyle f_ {q}}$ ${\ displaystyle \ left ({\ tfrac {\ Delta} {q}} \ right) = 1}$
Encontre um conjunto gerador X de G _Δ
Colete uma sequência de relações entre o conjunto X e { f _q : q ∈ P _Δ } satisfazendo: ${\ displaystyle \ left (\ prod _ {x \ in X _ {}} x ^ {r (x)} \ right). \ left (\ prod _ {q \ in P _ {\ Delta}} f_ {q} ^ {t (q)} \ direita) = 1}$
Construa uma forma ambígua que seja um elemento f ∈ G _Δ de ordem dividindo 2 para obter uma fatoração coprime do maior divisor ímpar de Δ em que ${\ displaystyle (a, b, c)}$ ${\ displaystyle \ Delta = -4ac {\ text {ou}} a (a-4c) {\ text {ou}} (b-2a) (b + 2a)}$
Se a forma ambígua fornece 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 a geração de formas ambíguas inúteis, construa o grupo 2-Sylow Sll ₂ (Δ) 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 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 . ${\ displaystyle L_ {n} \ left [{\ tfrac {1} {2}}, 1 + o (1) \ right]}$

Veja também

O algoritmo de Bach para gerar números aleatórios com suas fatorações
Representação canônica de um número inteiro positivo
Fatoração
Partição multiplicativa
Partição (teoria dos números) - uma maneira de escrever um número como uma soma de inteiros positivos.

Notas

Referências

Richard Crandall e Carl Pomerance (2001). Números primos: uma perspectiva computacional . Springer. ISBN 0-387-94777-9.Capítulo 5: Algoritmos de fatoração exponencial, pp. 191–226. Capítulo 6: Algoritmos de fatoração subexponencial, pp. 227-284. Seção 7.4: Método da curva elíptica, pp. 301–313.
Donald Knuth . The Art of Computer Programming , Volume 2: Seminumerical Algorithms , Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Seção 4.5.4: Fatoring into Primes, pp. 379-417.
Samuel S. Wagstaff Jr. (2013). A alegria de fatorar . Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3..
Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

links externos

msieve - SIQS e NFS - ajudou a completar algumas das maiores fatorações públicas conhecidas
Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics " , 2000, pp. 3-22. Download
Manindra Agrawal , Neeraj Kayal, Nitin Saxena, "PRIMES está em P." Annals of Mathematics 160 (2): 781-793 (2004). Versão PDF de agosto de 2005
Eric W. Weisstein, “RSA-640 Factored” MathWorld Headline News , 8 de novembro de 2005

Languages

In other projects