Forum de mathématiques - Bibm@th.net

Bonjour, dans le cadre d'une préparation à l'agregation de mathématique, plus précisément de l'option C "algèbre et calcul formel", je dois commenter un texte de mathématique, càd le présenter et faire qq démo.
Voici le texte en question : https://drive.google.com/file/d/1iwUpye … sp=sharing

Dans le premier théorème, il est dit que la complexité de l'algorithme d'euclide est en $\mathcal{O}(n^3m\delta^2log(nA))$ (je précise que $m$ est le degré du polynôme de plus bas degré, même si ça n'est pas mentionné dans le texte) opérations sur les mots. Déjà je suis pas sûr de ce que ça signifie (quels opérations sur quels mots?), mais j'ai l'impression qu'il y a quelque chose qui cloche et je sais pas si c'est moi ou le texte, donc j'aimerai votre avis:

D'abord, si je cherche à évaluer par moi même la complexité de l'algo d'euclide pour les polynômes , je trouve un $\mathcal{O}(n^2)$, je ne vais pas détailler comment je fais mais en gros je trouve qu'il n'y a pas plus de $2n$ multiplication nombre*polynôme , $2n$ soustraction de polynômes et $n$ division de polynôme par nombre, les polynômes étant au plus de degré $n$, ça fait une borne sup de $5n^2$ opérations.

$\delta$ est l'écart maximum entre deux restes consécutifs, je ne comprends pas comment cette donnée a autant d'impact sur la complexité. Par exemple, si $\delta = 10$ et $n = 1000$, le nombre de division euclidienne est entre 100 et 990... c'est pas une fourchette c'est un rateau! On est sensé avoir un facteur 100 entre le nombre de calculs lorsque $\delta = 1$ et $\delta = 10$...

Je passe sûrement à côté de quelquechose, et je me demande si c'est pas:
- la definition d'opération sur les mots que je ne comprends pas bien
- ce que c'est l'algo d'euclide