Multiplication

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.