Mathematiques assistees par ordinateur Chapitre Arithmetique des polynomes

Michael Eisermann

Description

Mathematiques assistees par ordinateur Chapitre 3 : Arithmetique des polynomes Michael Eisermann Mat249, DLST L2S4, Annee 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours _ mao Document mis a jour le 6 juillet 2009 1/55

• arithmetique des polynomes


• mathematiques assistees par ordinateur chapitre


• localisation des racines complexes


• unique corps de cardinal pk


• decomposition des polynomes et des fractions rationnelles


• corps

Sujets

• Arithmétique des polynômes
• multiplication
• cours

Informations

• Publié par: pefav
• Nombre de lectures: 41
• Langue: Français

Extrait

Math ´ ematiquesassist ´ eesparordinateur Chapitre3:Arithme ´ tiquedespolyn ˆ omes

Michael Eisermann

Mat249, DLST L2S4, Anne´  e 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours # mao Document mis a` jour le 6 juillet 2009

1/55

Objectifs de ce chapitre

Nousallonsdiscuteretapprofondirl’arithm ´ etiquedespolyn ˆ omessur un corps, notamment a`  coefficients  rationnels, re´  els, complexes.

Afin de proce´  der  syste´  matiquement et efficacement, nous introduisons d’abord le vocabulaire ade´  quat (corps et anneaux).

Ensuite on e´  tablira quelques outils fondamentaux, notamment la division euclidienne :S=P Q+Rou`degR <degP, l’algorithme d’Euclide pour calculerpgcd(A, B), l’algorithme d’Euclide-Be´  zout :pgcd(A, B) =AU+BV.

Les applications sont nombreuses ! D ´ mpositiondespolyn ˆ omesetdesfractionsrationnelles. eco Localisationdesracinesr ´ eellesd’unpolyno ˆ mere ´ el(Sturm). Localisation des racines complexes d’un polynoˆ  me complexe.

/255

Sommaire

1

2

3

Arithm ´ etiquedespolyn ˆ omessuruncorps,Euclide,Be ´ zout Polynomes sur un corps ˆ La division euclidienne Les algorithmes d’Euclide et de Be´  zout

´ Evaluation,racines,de ´ compositionenfacteursirr ´ eductibles Fonctionspolynomiales,m ´ ethodedeHorner,Horner–Taylor Multiplicit ´ ed’uneracine,r ´ eductionauxracinessimples D ´ ecompositiondepolyn ˆ omesenfacteursirre ´ ductibles

Fractionsrationnelles,e ´ l ´ ementssimples,int ´ egrationsymbolique Le corps des fractions rationnelles D ´ ecompositiond’unefractionenfractionssimples Primitive d’une fraction rationnelle

/355

§1.

Corps Les nombres rationnels(Q,+,∙) , les nombres re´  els(R,+,∙), et les nombres complexes(C,+,∙) ´ iusetn:juosisentdespropri ´ et es s va

1

(A1 : associativite´  ) (A2:commutativit ´ e) (A3: ´ ele ´ mentneutre) (A4 : e´ le´ ment  oppose) ´

(M1 : associativite´  ) (M2 : commutativite´  ) (M3: ´ el ´ entneutre) em (M4: ´ ele ´ mentinverse)

(D:distributivit ´ e)

D ´ efinition(corps)

Uncorps(K,+,∙)es

∀a, b, c: (a+b) +c=a+ (b+

∀a, b, c: (a+b) +c=a+ (b+c) ∀a, b:a+b=b+a ∃0∀a +: 0a=a ∀a∃b:a+b= 0

∀a, b, c: (a∙b)∙c=a∙(b∙c) ∀a, b:a∙b=b∙a ∃16= 0∀a: 1∙a=a ∀a6= 0∃b:a∙b= 1

∀a, b, c:a∙(b+c) = (a∙b) + (a∙c)

Uncorps(K,+,∙)est un ensembleK muni de deux ope´  rations, appele´ es  addition+ :K×K→Ket multiplication∙:K×K→K, verifiant tous les axiomes (A1-4), (M1-4), (D) ci-dessus. ´

/455

Corps finis Outre les corpsQ,R,Cil existe beaucoup d’autres exemples ! Sur l’ensembleF 2 ={0,1}ueclohxia’uqu’sn:da ` ntmennsox ´ eu ´ eel + 0 1∙0 1 0 0 1 et 0 0 0 . 1 1 0 1 0 1 Proposition(lecorpsadeux ´ el ´ ements) ` (F 2 ,+,∙)est un corps. De´ monstration. fiine ´ vreseesixmoLesa.sacselsutontra ´ eumenn ´ te Alternative : Si l’on interprete0et1comme«vrai»et«faux»alors la ` multiplication∙est la conjonction«et»tandis que l’addition+est la disjonction«ou exclusif»usSottce.vasu ´ dzerofeovemblilaej ` a ´ eta v ´ eracit ´ edesaxiomeslorsdevotreintroductiona ` lalogique. Alternative:OnpeutreconnaˆıtreF 2 comme le quotientZ/2Z. Remarque Lescorpsfinissontfortementutilise ´ senal ` ebreetencryptographie. g Tout corps fini est de cardinalp k pour un premierpne,tuqmeiproR ´ ec. §1.1 pour tout premierpetk≥1il existe un unique corps de cardinalp k . 5/55