Fast multiplication and its applications
Daniel J. Bernstein · 2008
This survey explains how some useful arithmetic operations can be sped up from quadratic time to essentially linear time. This paper presents fast algorithms for several useful arithmetic operations on polynomials, power series, integers, real numbers, and 2-adic numbers. Each section focuses on one algorithm for one operation, and describes seven features of the algorithm: • Input: What numbers are provided to the algorithm? Sections 2, 3, 4, and 5 explain how various mathematical objects are represented as inputs. • Output: What numbers are computed by the algorithm? • Speed: How many coefficient operations does the algorithm use to perform a polynomial operation? The answer is at most n 1+ o (1) , where n is the problem size; each section states a more precise upper bound, often using the function μ defined in Section 4. • How it works: What is the algorithm? The algorithm may use previous algorithms as subroutines, as shown in (the transitive closure of) Figure 1. • The integer case (except in Section 2): The inputs were polynomials (or power series); what about the analogous operations on integers (or real numbers)? What difficulties arise in adapting the algorithm to integers? How much time does the adapted algorithm take?