Fatoração de inteiros
De Wikipedia, a enciclopédia encyclopedia
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 fatores forem ainda mais restritos aos números primos, o processo é denominado fatoração prima.
A fatoração de inteiros pode ser resolvida em tempo polinomial em um computador clássico?
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.[1]
Quando os números são suficientemente grandes, nenhum algoritmo de fatoração de números inteiros não quântico 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 o 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 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-núcleo de poder de computação.[2] Os pesquisadores estimaram que um módulo RSA de 1024 bits levaria cerca de 500 vezes mais tempo.[3]
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 semiprimos, o produto de dois números primos. Quando ambos são grandes (mais de dois mil bits 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 insegura.