Séminaire du LIF
Jeudi 6 juin à 14h - Luminy, Amphi 12
Robert Rolland
IML, Univ. Aix-Marseille 2
Complexité bilineaire de la multiplication
de deux polynomes a coefficients dans un corps fini
Soit F_q le corps fini à q éléments (par exemple si q=2^8=256) les éléments de F_q sont des octets). Soit n un entier > 1. On considère une extension de degré n de F_q. On obtient le corps fini F_{q^n} qui a q^n éléments. Multiplier deux éléments dans cette extension revient à multiplier 2 polynomes de degré n-1 à coefficients dans F_q (et ensuite à prendre le reste modulo un polynome irréductible de degré n). Nous étudions la complexité bilineaire de ce produit (on compte les opérations bilineaires). Si q >= 2n-1 Vinograd a montré que cette complexité est 2n-1. Les Travaux récents des frères Chudnovski, de Shparlinski - Tsfasman - Vladut, de Shokrolahi, de Ballet puis de Ballet-Rolland ont amelioré successivement les bornes de cette complexité. Nous nous proposons de faire un survol des résultats et des méthodes employées.
Email : rolland@iml.univ-mrs.fr