Introduction a la Cryptologie Chapitre Anneaux euclidiens principaux factoriels

Introduction a` la Cryptologie
Chapitre 10 : Anneaux euclidiens, principaux, factoriels
Michael Eisermann (Institut Fourier, UJF Grenoble)
Annee´ 2008-2009
IF / IMAG, Master 1, S1-S2
document mis a` jour le 7 juillet 2009
INSTITUTi f FOURIER
www-fourier.ujf-grenoble.fr/~eiserm/cours#cryptoSommaire
1 Anneaux euclidiens, principaux, factoriels
2 Polynomesˆ sur un corps
3 ExercicesSommaire
1 Anneaux euclidiens, principaux, factoriels
Divisibilite´ et pgcd dans un anneau integ` re
Anneaux euclidiens, algorithmes d’Euclide et de Bez´ out principaux, lemmes de Gauss et d’Euclide
`Anneaux factoriels, problemes algorithmiques
2 Polynomesˆ sur un corps
3 ExercicesOn dit queb divisea dansA, ou quea
est un multiple deb dansA, note´ bja, s’il existec2A tel quea =bc.
Remarque
La divisibilite´ se reformule de maniere` el´ egante´ dans le langage des ideaux´ :
bja , a =bc , a2 (b) , (a) (b):
Remarque
La divisibilite´ definit´ une relation de pre-ordre´ surA :
refle´ xivite´ : on a toujoursaja.
transitivite´ :ajb etbjc entraˆınentajc.
´antisymetrie :ajb etbja entraˆınent (a) = (b).
De plus, pour touta;b;c2A nous avons :
1ja etaj 0.
Siajb, alorsajbc.
Siajb etajc, alorsajb +c.
Divisibilite´ dans un anneau integ` re
Definition´
`SoitA un anneau integre eta;b2A.Remarque
La divisibilite´ se reformule de maniere` el´ egante´ dans le langage des ideaux´ :
bja , a =bc , a2 (b) , (a) (b):
Remarque
La divisibilite´ definit´ une relation de pre-ordre´ surA :
refle´ xivite´ : on a toujoursaja.
transitivite´ :ajb etbjc entraˆınentajc.
´antisymetrie :ajb etbja entraˆınent (a) = (b).
De plus, pour touta;b;c2A nous avons :
1ja etaj 0.
Siajb, alorsajbc.
Siajb etajc, alorsajb +c.
Divisibilite´ dans un anneau integ` re
Definition´
`SoitA un anneau integre eta;b2A. On dit queb divisea dansA, ou quea
est un multiple deb dansA, note´ bja, s’il existec2A tel quea =bc.Remarque
La divisibilite´ definit´ une relation de pre-ordre´ surA :
refle´ xivite´ : on a toujoursaja.
transitivite´ :ajb etbjc entraˆınentajc.
´antisymetrie :ajb etbja entraˆınent (a) = (b).
De plus, pour touta;b;c2A nous avons :
1ja etaj 0.
Siajb, alorsajbc.
Siajb etajc, alorsajb +c.
Divisibilite´ dans un anneau integ` re
Definition´
`SoitA un anneau integre eta;b2A. On dit queb divisea dansA, ou quea
est un multiple deb dansA, note´ bja, s’il existec2A tel quea =bc.
Remarque
La divisibilite´ se reformule de maniere` el´ egante´ dans le langage des ideaux´ :
bja , a =bc , a2 (b) , (a) (b):refle´ xivite´ : on a toujoursaja.
transitivite´ :ajb etbjc entraˆınentajc.
´antisymetrie :ajb etbja entraˆınent (a) = (b).
De plus, pour touta;b;c2A nous avons :
1ja etaj 0.
Siajb, alorsajbc.
Siajb etajc, alorsajb +c.
Divisibilite´ dans un anneau integ` re
Definition´
`SoitA un anneau integre eta;b2A. On dit queb divisea dansA, ou quea
est un multiple deb dansA, note´ bja, s’il existec2A tel quea =bc.
Remarque
La divisibilite´ se reformule de maniere` el´ egante´ dans le langage des ideaux´ :
bja , a =bc , a2 (b) , (a) (b):
Remarque
La divisibilite´ definit´ une relation de pre-ordre´ surA :transitivite´ :ajb etbjc entraˆınentajc.
´antisymetrie :ajb etbja entraˆınent (a) = (b).
De plus, pour touta;b;c2A nous avons :
1ja etaj 0.
Siajb, alorsajbc.
Siajb etajc, alorsajb +c.
Divisibilite´ dans un anneau integ` re
Definition´
`SoitA un anneau integre eta;b2A. On dit queb divisea dansA, ou quea
est un multiple deb dansA, note´ bja, s’il existec2A tel quea =bc.
Remarque
La divisibilite´ se reformule de maniere` el´ egante´ dans le langage des ideaux´ :
bja , a =bc , a2 (b) , (a) (b):
Remarque
La divisibilite´ definit´ une relation de pre-ordre´ surA :
refle´ xivite´ : on a toujoursaja.´antisymetrie :ajb etbja entraˆınent (a) = (b).
De plus, pour touta;b;c2A nous avons :
1ja etaj 0.
Siajb, alorsajbc.
Siajb etajc, alorsajb +c.
Divisibilite´ dans un anneau integ` re
Definition´
`SoitA un anneau integre eta;b2A. On dit queb divisea dansA, ou quea
est un multiple deb dansA, note´ bja, s’il existec2A tel quea =bc.
Remarque
La divisibilite´ se reformule de maniere` el´ egante´ dans le langage des ideaux´ :
bja , a =bc , a2 (b) , (a) (b):
Remarque
La divisibilite´ definit´ une relation de pre-ordre´ surA :
refle´ xivite´ : on a toujoursaja.
transitivite´ :ajb etbjc entraˆınentajc.De plus, pour touta;b;c2A nous avons :
1ja etaj 0.
Siajb, alorsajbc.
Siajb etajc, alorsajb +c.
Divisibilite´ dans un anneau integ` re
Definition´
`SoitA un anneau integre eta;b2A. On dit queb divisea dansA, ou quea
est un multiple deb dansA, note´ bja, s’il existec2A tel quea =bc.
Remarque
La divisibilite´ se reformule de maniere` el´ egante´ dans le langage des ideaux´ :
bja , a =bc , a2 (b) , (a) (b):
Remarque
La divisibilite´ definit´ une relation de pre-ordre´ surA :
refle´ xivite´ : on a toujoursaja.
transitivite´ :ajb etbjc entraˆınentajc.
antisymetr´ ie :ajb etbja entraˆınent (a) = (b).