multapps revision available

A new (and, I hope, final) version of my survey paper ``Fast
multiplication and its applications,'' to appear in the book
``Cornerstones of algorithmic number theory'' by Buhler and Stevenhagen,
is available from http://cr.yp.to/papers.html#multapps. Some speedups
not mentioned in the previous version:

   * product trees with FFT doubling (Kramer), 1.5+o(1) times faster
     than the usual product-tree algorithm;

   * scaled remainder trees (Bostan, Lecerf, Schost, Bernstein),
     2.6+o(1) times faster than the best unscaled remainder trees;

   * smooth parts (Franke, Kleinjung, Morain, Wirth, Bernstein), time
     only n (lg n)^{2+o(1)} rather than n (lg n)^{3+o(1)}.

There are also some new descriptions of algorithms that save programmer
time: Schoenhage's reciprocal algorithm, for example, and the
Stehle-Zimmermann 2-adic gcd algorithm.

The paper is still limited to two complexity measures: total algebraic
complexity and multitape Turing-machine time. Several people have asked
me about other measures---space, online (``relaxed'') multiplication
time, pointer-machine time, logarithmic-size-word RAM time, etc.---but I
want to keep this paper reasonably simple. Of course, what I'm really
interested in are Pentium time, Athlon time, etc., and (thinking ahead
to the design of future computers) price-performance ratio for circuits.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago