Por que a complexidade computacional da fatoração de números inteiros é exp(raiz(N))?

Fatorar um número inteiro significa encontrar os fatores primos deste.

Exemplos: 15 = 3*5, ou 187 = 11*17

A fatoração tem duas características: é difícil de fazer, mas é fácil de checar se uma solução é válida.

Exemplo: Quais os fatores primos de 3127?

Um método possível para encontrar os fatores do número N é testar todas as alternativas até raiz(N). Ou seja, dividir 3127 por 2, 3, 5, 7, 9, até raiz(3127) ~= 55.

Com isso, chegamos que 3127 = 53*59. E é fácil checar que 59 é um dos fatores de 3127, basta fazer a divisão.

A fatoração de números inteiros (ou melhor, a dificuldade em fazê-lo) é a base de toda a criptografia moderna.

O número grande (digamos 3127) é a minha chave pública com a qual o emissor da informação faz a codificação. Para decodificar, preciso da chave privada (53 e 59). E a segurança baseia-se na dificuldade de fatorar grandes números.

Olhando na literatura, nota-se que a complexidade computacional da fatoração é da ordem de exp(N^1/3), para uma técnica chamada crivo numérico.

Por outro lado, não basta checar todas as divisões possíveis até raiz(N), conforme descrito acima? Por que a complexidade não é raiz(N), e sim, uma exponencial?

A resposta simples é que temos que considerar o tamanho do bit de entrada para calcular a complexidade. Para representar N em binário, precisamos de log2(N) bits, ou seja, N = exp(n).

Exemplo: 64 = 2^4, ou seja, precisamos de 4 bits para representar 64 em binário.

Assim, raiz(N) = raiz(2^n) = 2^n/2

Mas por que diabos temos que considerar o tamanho do número de entrada na conta da complexidade?

A resposta completa: porque temos que armazenar esse número, sem arredondamento.

Um computador convencional utiliza a técnica de ponto flutuante para armazenar um número grande. Digamos, 3.456.789 vira 3,4 * 10^6. Isso essencialmente arredonda o número, jogando fora os dígitos menos significativos. É um esquema inteligente, porque normalmente não é necessária tanta precisão assim.

Entretanto, na fatoração, não podemos arredondar, porque a conta tem que ser exata, até o último dígito.

Fazendo um exemplo extremo, se eu arredondasse a resposta para um dígito significativo, acharia:

3127 = 50*60 (o que está aproximadamente certo, mas não resolve o problema)

O caso da fatoração é pseudopolinomial: parece ser polinomial, porém, não é, porque para resolver o problema de verdade, o tamanho do input tem que entrar na conta.

O protocolo RSA-2048 utiliza 2048 bits. Exemplo a seguir.


Imagine fatorar o número abaixo em dois primos:

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

Vamos fazer uma conta. 2048 bits = preciso de 256 bytes só para armazenar o número.

Agora, tenho que testar todas as divisões até raiz(N).
A raiz do número monstro acima, da ordem 2^2048, é da ordem 2^1024 (ou seja, continua sendo um número monstruoso).

Para cada divisão, tenho que manipular um número de 256 bytes e outro de 128 bytes. O algoritmo da divisão é da ordem de n^2, o que é tranquilo para números pequenos, ou para números arredondados como o caso do ponto flutuante, mas extremamente pesado para um tamanho de número enorme como o citado.

Para finalizar, tenho que testar cada divisão 2^1024 vezes!

Uma alternativa pode vir de uma direção completamente nova. Em computação quântica, o algoritmo de Shor apresenta uma complexidade computacional da ordem de n^3, o que ainda é muito grande, porém é polinomial, não é exponencial. Computadores quânticos ainda não conseguiram escala e confiabilidade para desafios deste tamanho – talvez consigam um dia, talvez nunca consigam. Ainda é uma promessa.

A conclusão é de que o tamanho do dígito de entrada importa, em fatoração, e que este é um problema difícil (por enquanto). Ainda bem, as nossas contas bancárias e transações eletrônicas agradecem!

Algumas fontes:


https://math.stackexchange.com/questions/1624390/why-isnt-integer-factorization-in-complexity-p-when-you-can-factorize-n-in-o%E2%88%9A

https://stackoverflow.com/questions/6005873/determining-complexity-of-an-integer-factorization-algorithm

https://en.wikipedia.org/wiki/RSA_numbers#RSA-2048

https://pt.wikipedia.org/wiki/Complexidade_computacional_de_opera%C3%A7%C3%B5es_matem%C3%A1ticas

2 comentários sobre “Por que a complexidade computacional da fatoração de números inteiros é exp(raiz(N))?

  1. Pingback: Exemplo de complexidade polinomial – Computação e Informação Quântica

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s