Fast polynomial multiplication over F260

David Harvey; Joris Van Der Hoeven; Grégoire Lecerf

doi:10.1145/2930889.2930920

Fast polynomial multiplication over F₂⁶⁰

University of New South Wales

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

Abstract

Can post-Schönhage Strassen multiplication algorithms be competitive in practice for large input sizes? So far, the GMP library still outperforms all implementations of the recent, asymptotically more e cient algorithms for integer multiplication by Förer, De Kurur Saha Saptharishi, and ourselves. In this paper, we show how central ideas of our recent asymptotically fast algorithms turn out to be of practical interest for multiplication of polynomials over nite fields of characteristic two. Our Mathemagix implementation is based on the automatic generation of assembly codelets. It outperforms existing implementations in large degree, especially for polynomial matrix multiplication over finite fields.

Original language	English
Title of host publication	ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation
Editors	Markus Rosenkranz
Publisher	Association for Computing Machinery
Pages	255-262
Number of pages	8
ISBN (Electronic)	9781450343800
DOIs	https://doi.org/10.1145/2930889.2930920
Publication status	Published - 20 Jul 2016
Event	41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016 - Waterloo, Canada Duration: 20 Jul 2016 → 22 Jul 2016

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
Volume	20-22-July-2016

Conference

Conference	41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016
Country/Territory	Canada
City	Waterloo
Period	20/07/16 → 22/07/16

Keywords

Finite fields
Mathemagix
Polynomial multiplication

Access to Document

10.1145/2930889.2930920

Cite this

Harvey, D., Van Der Hoeven, J., & Lecerf, G. (2016). Fast polynomial multiplication over F₂⁶⁰. In M. Rosenkranz (Ed.), ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation (pp. 255-262). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. 20-22-July-2016). Association for Computing Machinery. https://doi.org/10.1145/2930889.2930920

Harvey, David ; Van Der Hoeven, Joris ; Lecerf, Grégoire. / Fast polynomial multiplication over F₂⁶⁰. ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation. editor / Markus Rosenkranz. Association for Computing Machinery, 2016. pp. 255-262 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

@inproceedings{c15272bbf00d4db48d30ec1e3350b1f7,

title = "Fast polynomial multiplication over F260",

abstract = "Can post-Sch{\"o}nhage Strassen multiplication algorithms be competitive in practice for large input sizes? So far, the GMP library still outperforms all implementations of the recent, asymptotically more e cient algorithms for integer multiplication by F{\"o}rer, De Kurur Saha Saptharishi, and ourselves. In this paper, we show how central ideas of our recent asymptotically fast algorithms turn out to be of practical interest for multiplication of polynomials over nite fields of characteristic two. Our Mathemagix implementation is based on the automatic generation of assembly codelets. It outperforms existing implementations in large degree, especially for polynomial matrix multiplication over finite fields.",

keywords = "Finite fields, Mathemagix, Polynomial multiplication",

author = "David Harvey and \{Van Der Hoeven\}, Joris and Gr{\'e}goire Lecerf",

note = "Publisher Copyright: {\textcopyright} 2016 Copyright held by the owner/author(s).; 41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016 ; Conference date: 20-07-2016 Through 22-07-2016",

year = "2016",

month = jul,

day = "20",

doi = "10.1145/2930889.2930920",

language = "English",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

publisher = "Association for Computing Machinery",

pages = "255--262",

editor = "Markus Rosenkranz",

booktitle = "ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation",

}

Harvey, D, Van Der Hoeven, J & Lecerf, G 2016, Fast polynomial multiplication over F₂⁶⁰. in M Rosenkranz (ed.), ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, vol. 20-22-July-2016, Association for Computing Machinery, pp. 255-262, 41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016, Waterloo, Canada, 20/07/16. https://doi.org/10.1145/2930889.2930920

Fast polynomial multiplication over F₂⁶⁰. / Harvey, David; Van Der Hoeven, Joris ; Lecerf, Grégoire.
ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation. ed. / Markus Rosenkranz. Association for Computing Machinery, 2016. p. 255-262 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC; Vol. 20-22-July-2016).

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

TY - GEN

T1 - Fast polynomial multiplication over F260

AU - Harvey, David

AU - Van Der Hoeven, Joris

AU - Lecerf, Grégoire

PY - 2016/7/20

Y1 - 2016/7/20

N2 - Can post-Schönhage Strassen multiplication algorithms be competitive in practice for large input sizes? So far, the GMP library still outperforms all implementations of the recent, asymptotically more e cient algorithms for integer multiplication by Förer, De Kurur Saha Saptharishi, and ourselves. In this paper, we show how central ideas of our recent asymptotically fast algorithms turn out to be of practical interest for multiplication of polynomials over nite fields of characteristic two. Our Mathemagix implementation is based on the automatic generation of assembly codelets. It outperforms existing implementations in large degree, especially for polynomial matrix multiplication over finite fields.

AB - Can post-Schönhage Strassen multiplication algorithms be competitive in practice for large input sizes? So far, the GMP library still outperforms all implementations of the recent, asymptotically more e cient algorithms for integer multiplication by Förer, De Kurur Saha Saptharishi, and ourselves. In this paper, we show how central ideas of our recent asymptotically fast algorithms turn out to be of practical interest for multiplication of polynomials over nite fields of characteristic two. Our Mathemagix implementation is based on the automatic generation of assembly codelets. It outperforms existing implementations in large degree, especially for polynomial matrix multiplication over finite fields.

KW - Finite fields

KW - Mathemagix

KW - Polynomial multiplication

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

U2 - 10.1145/2930889.2930920

DO - 10.1145/2930889.2930920

M3 - Conference contribution

AN - SCOPUS:84984638462

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 255

EP - 262

BT - ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation

A2 - Rosenkranz, Markus

PB - Association for Computing Machinery

T2 - 41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016

Y2 - 20 July 2016 through 22 July 2016

ER -

Harvey D, Van Der Hoeven J , Lecerf G. Fast polynomial multiplication over F₂⁶⁰. In Rosenkranz M, editor, ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation. Association for Computing Machinery. 2016. p. 255-262. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). doi: 10.1145/2930889.2930920