Faster Multiplication in GF(2)[x]

232. Richard P. Brent, Pierrick Gaudry, Emmanuel Thomé and Paul Zimmermann, Faster multiplication in GF(2)[x], Proc. ANTS-VIII (Banff, May 17-22, 2008), edited by A. J. van der Poorten and A. Stein, Lecture Notes in Computer Science, Vol. 5011, Springer-Verlag, 2008, 153-166. Also INRIA Tech. Report RR-6359, Nov. 2007, 19 pp.

Preprint: pdf (224K).

Technical Report: pdf (288K).


In this paper, we discuss an implementation of various algorithms for multiplying polynomials in GF(2)[x]: variants of the window methods, Karatsuba's, Toom-Cook's, Schönhage's and Cantor's algorithms. For most of them, we propose improvements that lead to practical speedups.


For related papers see [230, 233, 235].

For software, see the gf2x package.

Go to next publication

Return to Richard Brent's index page