Faster Multiplication in GF(2)[x]

Richard Brent 1 Pierrick Gaudry 2 Emmanuel Thomé 2 Paul Zimmermann 2
2 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Document type :
Conference papers
van der Poorten, Alfred and Stein, Andreas. ANTS-VIII, May 2008, Banff, Canada. Springer-Verlag, 5011, pp.153-166, 2008, Lecture notes in computer science; Algorithmic Number Theory, ANTS-VIII. <10.1007/978-3-540-79456-1>


https://hal.inria.fr/inria-00188261
Contributor : Pierrick Gaudry <>
Submitted on : Friday, November 7, 2008 - 8:33:25 AM
Last modification on : Thursday, May 19, 2016 - 1:09:17 AM
Document(s) archivé(s) le : Friday, September 24, 2010 - 11:15:27 AM

File

gf2x.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Richard Brent, Pierrick Gaudry, Emmanuel Thomé, Paul Zimmermann. Faster Multiplication in GF(2)[x]. van der Poorten, Alfred and Stein, Andreas. ANTS-VIII, May 2008, Banff, Canada. Springer-Verlag, 5011, pp.153-166, 2008, Lecture notes in computer science; Algorithmic Number Theory, ANTS-VIII. <10.1007/978-3-540-79456-1>. <inria-00188261v4>

Export

Share

Metrics

Record views

508

Document downloads

285