S�minaire du 4 novembre 02, Alin Bostan, GAGE, �cole polytechnique

Algorithmes rapides pour certains calculs avec deux nombres alg�briques

�tant donn�s deux polyn�mes $f$ et $g$ en une variable sur un corps $k$, on d�finit leur somme compos�e $f \oplus g$ et leur produit compos� $f\otimes g$, par les formules $$ f\oplus g = \prod _{\alpha, \beta} \big(T-(\alpha+\beta)\big) \;\;\;\; \text{et}\;\;\;\; f\otimes g = \prod _{\alpha, \beta}(T-\alpha\beta),$$ o� les produits sont pris sur toutes les racines $\alpha$ de $f$ et $\beta$ de $g$, compt�es avec multiplicit�s.

Ces op�rations se retrouvent de mani�re naturelle dans diverses branches des math�matiques concr�tes, comme la th�orie alg�brique des nombres, la th�orie de Galois effective, la sommation symbolique, ainsi que dans l'�tude des polyn�mes sur des corps finis et dans la th�orie des suites r�currentes lin�aires.

Classiquement, les polyn�mes $f \oplus g$ et $f \otimes g$ sont obtenus via un calcul de r�sultants bivari�s. Nous montrons comment acc�l�rer leur calcul, de mani�re � obtenir des algorithmes de complexit� lin�aire en le degr� de la sortie, � des facteurs logarithmiques pr�s. Ce travail a �t� men� en collaboration avec P. Flajolet, B. Salvy et � . Schost.