Calcul formel - Cours 7 Calcul modulo un polynôme

Guénaël Renault

Description

Calcul formel - Cours 7ˆCalcul modulo un polynomeGuena´ el¨ RenaultSPIRAL - LIP6/Universite´ Paris 622 mars 2007Part IIntroduction - MotiviationUPMC-MasterSTL-CalculFormel-2006/07 2/20Calcul moduloC’est le moyen de representer´les structures mathematiques´en informatique et de faire ducacul exact : Calcul Formel !⇒ Resolution´ de problemes` geom´ etr´ iques (geo´ . - alg.)⇒ Utilisation des groupes en combinatoire⇒ Theor´ ie algorithmique des nombres, cryptologie⇒ ...UPMC-MasterSTL-CalculFormel-2006/07 3/20Calcul modulo un polynomeˆ en une variable⇒ Il faut bien commencer par une variable !Pourquoi?Representation´ symbolique de solutionsRepr´ de structures mathematiques´ (applications).Exemples importants :⇒ Representation´ des corps finis (theor´ ie de l’information).⇒ Repr´ des solutions issues de la geom´ etr´ ie.⇒ Representation´ des corps de nombres et de fonctions.UPMC-MasterSTL-CalculFormel-2006/07 4/20Part IIEuclide et l’arithmetique´UPMC-MasterSTL-CalculFormel-2006/07 5/20Arithmetique´ : quelques definitions´ importantesSoit A un anneau (commutatif avec unite).´ L’arithmetique´ dans A c’est´ ´etudier la notion de divisibilite dans cet anneau.Definitions´`anneau integreideal´ (exemple : akb⇒ aA⊂ bA)´ ´ ´ ´ ´element inversible (elements associes)el´ ement´ irreductib´ leel´ ement´ premiera,b∈ A, pgcd(a,b)UPMC-MasterSTL-CalculFormel-2006/07 6/20Decomposition´ d’Euclide en gen´ er´ alUn anneau A factoriel siA integ` re∀a∈ A ...

Informations

• Publié par: Eddo
• Nombre de lectures: 67
• Langue: Français

Extrait

Calcul formel - Cours 7

Calcul modulo un polynome ˆ

Gue´ nae¨ l  Renault

SPIRAL - LIP6/Universite´ Paris 6

22 mars 2007

UPMC-aMtsreTSL-CalculFor

Par

Introduction

eml-2006/07

t

-

I

Motiviation

/202

Calcul modulo

C’est le moyen de  ´  t represen er lesstructuresmathe ´ matiques en informatique et de faire du cacul exact : Calcul Formel !

UPMC

⇒ Re ´ solutiondeproble ` mesg ´ eom ´ etriques(ge ´ o.-alg.) ⇒ Utilisation des groupes en combinatoire ⇒ Th ´ eoriealgorithmiquedesnombres,cryptologie ⇒ ...

-aMsterSTL-ClaculoFrmel-2006/073/20

Calcul modulo un pol  ˆ  ariable ynome en une v

⇒ Il faut bien commencer par une variable ! Pourquoi ?

Repre´ sentation symbolique de solutions Repre´ sentation de structures mathe´  matiques (applications).

Exemples importants :

UPMC

⇒ Repre´ sentation  des corps finis (th ´ eoriedel’information). ⇒ Repre´ sentation  des solutions issues de la g ´ eome ´ trie . ⇒ Repr ´ esentationdes corps de nombres et de fonctions .

-aMtsreSTL-CalculFormel-0206/07/402

UPMC-MasterTSL-CalculoFr

Euclide

mel-02600/7

Part

et

II

l’arithme´ tique

5/20

Arithm ´ etique:quelquesd ´ efinitionsimportantes Soit A un anneau (commutatif avec unite´  ). L’arithm ´ etique dans A c’est ´ etudierlanotionde divisibilite´ dans cet anneau. D ´ finitions e anneauint ` egre ide´ al  (exemple : a k b ⇒ aA ⊂ bA ) e ´ le ´ mentinversible(e ´ l ´ ementsassocie ´ s) e ´ le ´ mentirr ´ eductible e´ lemen  pr r ´ t  emie a , b ∈ A , pgcd ( a , b ) UPMC - Master STL - Calcul Formel - 2006/07 6/20

De ´ compositiond’Euclideenge ´ n ´ eral Un anneau A factoriel si A integre ` ∀ a ∈ A non nul et non inversible, on a une de´  composition unique (association pre`  s) de la forme a = Y p i , p i irr ´ eductibles i ⇒ Arithme´ tique  de base possible ici ! Exemple : Z , Z [ X ] UPMC - Master STL - Calcul Formel - 2006/07 7/20

lFormel-TL-CalcuM-saetSrPUCM02/

A int ` egre a 1 A ⊂ a 2 A ⊂ . . . ⊂ a i A eststationnaire(Noeth ´ erien,leside ´ aux sont de type fini, donne l’existence de la de´  composition). p irre´ ductible ⇒ p premier

6002870/ tonfactoriel?Cmoemtnedivne

Comment devient on factoriel ?

Si A inte ` greilsuffitquecequisuitsoitv ´ erifie ´ a 1 A ⊂ a 2 A ⊂ . . . ⊂ a i A est stationnaire (donne l’existence de la de´ composition). p irr ´ eductible ⇒ p premier (donne  l’unicite´  )

Definitions ´ A estnoeth ´ eriensitoutesuitecroissanted’ide ´ auxeststationnaire. ⇒ Lesid ´ eauxd’unanneauNoeth ´ eriensontdetypefini(ssi). ⇒ A noeth ´ erien ⇒ A [ X ] est noethe´  rien. Contre-exemple Z [ i √ 5 ] estinte ` grenoeth ´ eriensa ˆ trefactoriel ns e . Z [ i √ 5 ] ' Z [ X ] / ( X 2 + 5 )

Attention factoriel n’implique pas noethe´  rien !

UPMC-MasterSTL-ClaculFormel-2006/07/920

B ´ ezoutetanneauprincipal

Soient a , b et c trois ´ el ´ ementsde A .IlssontenrelationdeB ´ ezoutsi

et dans ce cas nous avons

Re´ ciprocite´  ?

cA = aA + bA

c = pgcd ( a , b )

lesid ´ eauxdetypefinisontprincipauxsuffit!

Anneau principal int ` egre toutide ´ alestprincipal(monog ` ene) Contre-exemple important : Q [ X , Y ] n’est pas principal ! ⇒ A [ X ] principal ssi A est un corps.

PUMC-aMtsreTSL-ClaculFormel-2006/07012/0

0/6002-l

Anneaux euclidiens : o `u l’on commence  `a  faire des calculs !

02/117

euclidien ⇒ principal ⇒ factoriel

Comment calculer le pgcd et la relation de Be´  zout ?

a = bq + r division euclidienne

Anneau euclidien (onpeutge ´ n ´ eralisercetted ´ efinition) int ` egre Il existe une application φ : A −→ R + tq pour tout a , b 6 = 0 dans A on peut trouver q et r verifiant ´

avec φ ( r ) < φ ( b ) ⇒ Algorithmed’Euclide ´ etendu.

MC-Maste uivre! UPucFlroemSrLTC-la n?ie as⇒B euonidcl renbsa`,edseo¨rG ntfaommeCssniclluseacride