fatoração de inteiros

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