A Unified View of the Complexity of Evaluation and Interpolation

Four problems are considered: 1) from an n-precision integer compute its residues modulo n single precision primes; 2) from an n-degree polynomial compute its values at n points; 3) from n residues compute the unique n-precision integer congruent to the residues; 4) from n points compute the unique interpolating polynomial through those points. If $M(n)$ is the time for n-precision integer multiplication, then the time for problems 1 and 2 is shown to be $M(n) \log n$ and for problems 3 and 4 to be $M(n)(\log n)^{2}$. Moreover, it is shown that each of the four algorithms are really all instances of the same general algorithm. Finally, it is shown how preconditioning or a change of domain will reduce the time for problems 3 and 4 to $M(n)(\log n)$