GT PequanRSS

Ajouter à votre agenda

The Frobenius FFT and application to the multiplication of binary polynomials


25/10/2018
Horaire : 10h30
Intervenant(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.salle 26-00/101, 4 place Jussieu - 75005 Paris
Plus d'informations ici
Marc.Mezzarobba (at) nulllip6.fr
 Mentions légales
Carte du site |