Fast Integer Multiplication Using Modular Arithmetic

We give an $N\cdot \log N\cdot 2^{O(\log^*N)}$ time algorithm to multiply two $N$-bit integers that uses modular arithmetic for intermediate computations instead of arithmetic over complex numbers as in Fürer's algorithm, which also has the same and so far the best known complexity. The previous bes... View More