Mathematiques assistees par ordinateur Chapitre Arithmetique des polynomes

pages

Français

Documents

Écrit par
Michael Eisermann

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

Français

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

Voir

Publié par

pefav

Nombre de lectures

Langue

Français

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` coefﬁcients rationnels, re´ els, complexes.

Aﬁn de proce´ der syste´ matiquement et efﬁcacement, 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

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

(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´eﬁnition(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 ensembleKmuni de deux ope´ rations, appele´ es addition+ :K×K→Ket multiplication∙:K×K→K, veriﬁant tous les axiomes (A1-4), (M1-4), (D) ci-dessus. ´

/455

Corps ﬁnis Outre les corpsQ,R,Cil existe beaucoup d’autres exemples ! Sur l’ensembleF2={0,1}ueclohxia’uqu’sn:da`ntmennsox´eu´eel + 0 1∙0 1 0 0 1et0 0 0. 1 1 0 1 0 1 Proposition(lecorpsadeux´el´ements) ` (F2,+,∙)est un corps. De´ monstration.ﬁine´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ˆıtreF2comme le quotientZ/2Z. Remarque Lescorpsﬁnissontfortementutilise´senal`ebreetencryptographie. g Tout corps ﬁni est de cardinalpkpour un premierpne,tuqmeiproR´ec. §1.1pour tout premierpetk≥1il existe un unique corps de cardinalpk.5/55

Voir