produit de polynomes a coeff dans Z/pZ par FFT

parisse
Messages : 5044
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

produit de polynomes a coeff dans Z/pZ par FFT

Message par parisse » mer. sept. 25, 2019 11:47 am


parisse
Messages : 5044
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: produit de polynomes a coeff dans Z/pZ par FFT

Message par parisse » mar. janv. 14, 2020 9:29 am

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.

Répondre