TY - GEN
T1 - Fast polynomial multiplication over F260
AU - Harvey, David
AU - Van Der Hoeven, Joris
AU - Lecerf, Grégoire
N1 - Publisher Copyright:
© 2016 Copyright held by the owner/author(s).
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 -