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.