Faster Multiplication in GF(2)[x] (original) (raw)

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

Domains

Connect in order to contact the contributor

https://inria.hal.science/inria-00188261

Submitted on : Friday, November 7, 2008-8:33:25 AM

Last modification on : Wednesday, March 18, 2026-11:52:02 AM

Long-term archiving on : Friday, September 24, 2010-11:15:27 AM

Dates and versions

inria-00188261 , version 1 (16-11-2007)

inria-00188261 , version 2 (19-11-2007)

inria-00188261 , version 3 (19-11-2007)

inria-00188261 , version 4 (07-11-2008)

Licence

Identifiers

• HAL Id : inria-00188261 , version 4
• DOI : 10.1007/978-3-540-79456-1

Cite

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⟩

Altmetric