GT Pequan
The Frobenius FFT and application to the multiplication of binary polynomials
10/25/2018Speaker(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.
More details here
Marc.Mezzarobba (at)
nulllip6.fr
