Algoritmos para multiplicação rápida de dois números com mais de 1.000 dígitos cada

Abstract

Multiplicação de números grandes possui um papel fundamental na performance de aplicações importantes, como a criptografia. A proposta deste trabalho é apresentar diferentes algoritmos para multiplicação rápida de números inteiros e analisar suas respectivas vantagens e desvantagens. Será visto que é possível encontrar algoritmos mais eficientes do que o método tradicional ensinado em escola, como a Transformada Numérica Teórica (NTT), a qual utiliza conceitos como Transformada Discreta de Fourier, Transformada Rápida de Fourier, Corpos Finitos e Aritmética Modular.