Multiplication

Abstract

The paper provides a survey of the modern state of the theory of fast multiplication of
numbers and polynomials. We consider the development of multiplication methods from the
initial block algorithms of 1960s due to Karatsuba and Toom to the methods of 1970s based
on the Discrete Fourier transform (DFT) and further to the novel methods invented in 2007–
2009. Modern multiplication methods combine exploiting of special algebraic structures, the use
of approximate computations, special forms of Fourier transforms, namely, multidimensional
DFT, additive analogue of DFT. These and other concepts essential for the fast multiplication
algorithms are thoroughly discussed in the present survey. In particular, we provide an
introduction to the theory of DFT with derivation of facts necessary for the exposition.
The final part of the survey contains a brief discussion of results on parallel multiplication
algorithms, accurate complexity bounds of the basic methods, online multiplication algorithms,
multiplicative complexity of the multiplication of polynomials over finite fields. We mention
computational models where multiplication has either linear, or quadratic complexity.