Faster multiplication in GF(2)[x]

Richard P. Brent; Pierrick Gaudry; Emmanuel Thomé; Paul Zimmermann

doi:10.1007/978-3-540-79456-1_10

Faster multiplication in GF(2)[x]

Richard P. Brent
, Pierrick Gaudry
, Emmanuel Thomé
, Paul Zimmermann

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

49 Citations (Scopus)

Abstract

In this paper, we discuss an implementation of various algorithms for multiplying polynomials in : 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.

Original language	English
Title of host publication	Algorithmic Number Theory - 8th International Symposium, ANTS-VIII, Proceedings
Pages	153-166
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-540-79456-1_10
Publication status	Published - 2008
Event	8th International Symposium on Algorithmic Number Theory, ANTS-VIII - Banff, Canada Duration: 17 May 2008 → 22 May 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5011 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Symposium on Algorithmic Number Theory, ANTS-VIII
Country/Territory	Canada
City	Banff
Period	17/05/08 → 22/05/08

Access to Document

10.1007/978-3-540-79456-1_10

Cite this

Brent, R. P., Gaudry, P., Thomé, E., & Zimmermann, P. (2008). Faster multiplication in GF(2)[x]. In Algorithmic Number Theory - 8th International Symposium, ANTS-VIII, Proceedings (pp. 153-166). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5011 LNCS). https://doi.org/10.1007/978-3-540-79456-1_10

@inproceedings{e76fdc8883774121a82a90ffdca6fa37,

title = "Faster multiplication in GF(2)[x]",

abstract = "In this paper, we discuss an implementation of various algorithms for multiplying polynomials in : variants of the window methods, Karatsuba's, Toom-Cook's, Sch{\"o}nhage's and Cantor's algorithms. For most of them, we propose improvements that lead to practical speedups.",

author = "Brent, \{Richard P.\} and Pierrick Gaudry and Emmanuel Thom{\'e} and Paul Zimmermann",

year = "2008",

doi = "10.1007/978-3-540-79456-1\_10",

language = "English",

isbn = "3540794557",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "153--166",

booktitle = "Algorithmic Number Theory - 8th International Symposium, ANTS-VIII, Proceedings",

note = "8th International Symposium on Algorithmic Number Theory, ANTS-VIII ; Conference date: 17-05-2008 Through 22-05-2008",

}

Brent, RP, Gaudry, P, Thomé, E & Zimmermann, P 2008, Faster multiplication in GF(2)[x]. in Algorithmic Number Theory - 8th International Symposium, ANTS-VIII, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5011 LNCS, pp. 153-166, 8th International Symposium on Algorithmic Number Theory, ANTS-VIII, Banff, Canada, 17/05/08. https://doi.org/10.1007/978-3-540-79456-1_10

Faster multiplication in GF(2)[x]. / Brent, Richard P.; Gaudry, Pierrick; Thomé, Emmanuel et al.
Algorithmic Number Theory - 8th International Symposium, ANTS-VIII, Proceedings. 2008. p. 153-166 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5011 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

TY - GEN

T1 - Faster multiplication in GF(2)[x]

AU - Brent, Richard P.

AU - Gaudry, Pierrick

AU - Thomé, Emmanuel

AU - Zimmermann, Paul

PY - 2008

Y1 - 2008

N2 - In this paper, we discuss an implementation of various algorithms for multiplying polynomials in : 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.

AB - In this paper, we discuss an implementation of various algorithms for multiplying polynomials in : 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.

UR - https://www.scopus.com/pages/publications/44649181260

U2 - 10.1007/978-3-540-79456-1_10

DO - 10.1007/978-3-540-79456-1_10

M3 - Conference Paper

SN - 3540794557

SN - 9783540794554

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 153

EP - 166

BT - Algorithmic Number Theory - 8th International Symposium, ANTS-VIII, Proceedings

T2 - 8th International Symposium on Algorithmic Number Theory, ANTS-VIII

Y2 - 17 May 2008 through 22 May 2008

ER -

Faster multiplication in GF(2)[x]

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this