References: [ Home | Author index | Key index | Search ]

Bernstein1998

D. Bernstein, "Multidigit multiplication for mathematicians," Advances in Applied Mathematics, (1998) to appear? Preprint available from http://cr.yp.to/papers.html.

Abstract: This paper surveys techniques for multiplying elements of various commutative rings. It covers Karatsuba multiplication, dual Karatsuba multiplication, Toom multiplication, dual Toom multiplication, the FFT trick, the twisted FFT trick, the split-radix FFT trick, Good's trick, the Schönhage-Strassen trick, Schönhage's trick, Nussbaumer's trick, the cyclic Schönhage-Strassen trick, and the Cantor-Kaltofen theorem. It emphasizes the underlying ring homomorphisms.

[This paper begins "The purpose of this paper is twofold: first, to present every known technique for computing the product of two large integers; second, to present every known technique for computing the product of two polynomials over a commutative ring. "]