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).
Abstract
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.
Comments
For related papers see
[230,
233,
235].
For software, see the gf2x
package.
Go to next publication
Return to Richard Brent's index page