La définition de r=résultant de A et B comme le déterminant de la matrice de Sylvester donne un premier algorithme pour calculer r. Il existe une autre méthode de calcul qui utilise l'algorithme d'Euclide. On part du résultat suivant, où lcoeff(B) désigne le coefficient dominant de B
Code : Tout sélectionner
resultant(A,B)=(-1)^(degre(A)*degre(B))*lcoeff(B)^degree(A)*produit sur les racines beta_j de B des A(beta_j)
Si on effectue la division euclidienne de A par B
Code : Tout sélectionner
A=B*Q+R
Code : Tout sélectionner
resultant(A,B)=(-1)^(degre(A)*degre(B))*lcoeff(B)^(degree(A)-degree(R))*resultant(B,R)
Comparer les complexités du calcul de resultant(A,B) par le déterminant de la matrice de Sylvester et par l'algorithme d'Euclide (on suppose que le cout d'une operation sur le corps fini est en O(1)). Illustrer sur machine.