GT Pequan
The Frobenius FFT and application to the multiplication of binary polynomials
10/25/2018
Speaker(s) : Robin Larrieu (LIX, École polytechnique)
When computing a Discrete Fourier Transform (DFT), it often happens that the input coefficients lie in some field but the DFT is actually in an extension field. It is classical that the (complex) DFT of a real polynomial can be computed twice as fast as the DFT of a complex polynomial of the same size. We will see that a similar result holds in the case of finite fields: if the extension has degree d, then a speedup by a factor d can be achieved by exploiting the symmetries provided by the Frobenius map. This theoretical result has in particular led to a faster implementation for the multiplication of large polynomials over the binary field.
Marc.Mezzarobba (at) nulllip6.fr