Faster Multiplication in GF(2)[x]

Richard P. Brent (1) , Pierrick Gaudry (2) , Emmanuel Thomé (2) , Paul Zimmermann (2)

1 MSI - Mathematical Sciences Institute
2 CACAO - Curves, Algebra, Computer Arithmetic, and so On

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, Schoenhage's and Cantor's algorithms. For most of them, we propose improvements that lead to practical speedups.

Domaines: Algorithme et structure de données [cs.DS]

Richard P. Brent, Pierrick Gaudry, Emmanuel Thomé, Paul Zimmermann. Faster Multiplication in GF(2)[x]. Algorithmic Number Theory – ANTS-VIII, May 2008, Banff, Canada. pp.153-166, ⟨10.1007/978-3-540-79456-1⟩. ⟨inria-00188261v4⟩