produit de polynomes a coeff dans Z/pZ par FFT
Re: produit de polynomes a coeff dans Z/pZ par FFT
On peut utiliser l'algorithme precedent pour multiplier des polynomes en x a coeff dans une extension GF(p,n) de Z/pZ, en utilisant la substitution de Kronecker. Cela consiste a poser x=y^2n et a utiliser la representation additive dans GF(p,n) en fonction de y, on a alors des polynomes en 1 variable y a coeff dans Z/pZ, on fait le produit par FFT, et on decompose "en base y^(2n)", il reste a calculer le reste de chaque "coefficient" polynome de degre y^(2n-2) au plus par le polynome minimal definissant l'extension.