The efficient multiplication of polynomials over the finite field is a fundamental problem in computer science with several applications to geometric error correcting codes and algebraic crypto-systems. In this paper we report on a new algorithm that leads to a practical speed-up of about two over previously available implementations. Our current implementation assumes a modern AVX2 and CLMUL enabled processor.

Authors: Joris van der Hoeven, Robin Larrieu, Grégoire Lecerf

Keywords: polynomial multiplication, finite field, Frobenius FFT, implementation, high performance

View: Html, TeXmacs, Pdf, BibTeX