Algèbre, confidentialité et intégrité en multimédia

-

Livres
307 pages
Lire un extrait
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Cet ouvrage est consacré à l'algèbre (éléments d'algèbre, algèbre linéaire et multilinéaire) et à ses applications en cryptographie et codes correcteurs d'erreurs.
Il étudie de façon approfondie les structures algébriques finies que sont les groupes de permutations, les anneaux et les corps finis. Il décrit aussi les circuits électroniques réalisant des calculs dans les corps finis puis la complexité de certains algorithmes.
La confidentialité des données (cryptographie) et leur intégrité (codes correcteurs) en multimédia sont ensuite présentées en détails. De nombreux exemples d'applications réelles sont enfin développés (CD, DVD, disques optiques, sondes lointaines, télévision numérique terrestre, etc.).
Ce livre, conçu de façon pédagogique, est accessible aux étudiants mais aussi à toutes personnes intéressées par l'algèbre et la sécurité. Il comporte deux cents exercices et problèmes classés par ordre de difficulté croissante, avec leurs corrigés complets.
Introduction. Chapitre 1. Éléments d'algèbre. Chapitre 2. Algèbre linéaire et multilinéaire. Chapitre 3. Groupes et corps finis. Chapitre 4. Anneaux finis. Chapitre 5. Cryptographie symétrique. Chapitre 6. Cryptographie à clé publique. Chapitre 7. Codes correcteurs. Chapitre 8. Exercices et problèmes. Énoncés. Solutions. Bibliographie. Index.

Sujets

Informations

Publié par
Date de parution 07 octobre 2009
Nombre de visites sur la page 30
EAN13 9782746240674
Langue Français

Informations légales : prix de location à la page 0,0615 €. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Signaler un problème




















AlgŁbre, confidentialitØ et intØgritØ en multimØdia



































' LAVOISIER, 2009
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-2460-5
ISSN 1242-7691


Le Code de la propriØtØ intellectuelle n’autorisant, aux termes de l’article L. 122-5, d’une part,
que les "copies ou reproductions strictement rØservØes l’usage privØ du copiste et non
destinØes une utilisation collective" et, d’autre part, que les analyses et les courtes citations
dans un but d’exemple et d’illustration, "toute reprØsentation ou reproduction intØgrale, ou
partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette reprØsentation ou reproduction, par quelque procØdØ que ce
soit, constituerait donc une contrefa on sanctio nnØe par les articles L. 335-2 et suivants du
Code de la propriØtØ intellectuelle.
Tous les noms de sociØtØs ou de produits citØs dans cet ouvrage sont utilisØs des fins
d identification et sont des marque s de leurs dØtenteurs respectifs.


Printed and bound in England by Antony Rowe Ltd, Chippenham, October 2009.





AlgŁbre, confidentialitØ

et intØgritØ en multimØdia










Alain Poli

Philippe Guillot














Collection dirigØe par Jean-Charles Pomerol





BANATRE Michel et al. Informatique diffuse, 2007.
BARTHELEMY Pierre, ROLLAND Robert et VERON Pascal Cryptographie, 2005.
CARDON Alain La complexitØ organisØe : systŁmes adaptatifs, 2004.
CHRISMENT Claude et al. Bases de donnØes relationnelles, 2008.
FAURE Alain Classification et commande par rØseaux de neurones, 2006.
FOURNIER Jean-Claude ThØorie des graphes et applications, 2005.
PARIS StØphane Le multimØdia et la compression, 2009.
PARIS StØphane Le multimØdia, 2009.
PIERSON Jacky La biomØtrie, 2007.
POLI Alain et GUILLOT Philippe AlgŁbre et protection de linformation , 2005.
ROSENTHAL-SABROUX Camille et CARVALHO Americo Management et
gouvernance des SI, 2009.
VARRETTE SØbastien et BERNARD Nicolas Programmation avancØe en C
avec exercices corrigØs, 2006.
VERDRET Philippe De Perl Java : programmation des expressions rØguliŁres ,
2004.
Tabledesmatières
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chapitre1.Elémentsd’algèbre . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1. Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.1. Ensemblesfinisouinfinis . . . . . . . . . . . . . . . . . . . . . 18
1.1.2. Partiesd’unensemble,ensembledespartiesd’unensemble . . 18
1.1.3. Constructiond’ensemblesàpartird’ensembles,
departiesàpartirdeparties . . . . . . . . . . . . . . . . . . . 19
1.1.3.1. Constructiond’ensemblesàpartird’ensembles . . . . . . 19
1.1.3.2. Constructionsdepartiesàpartirdeparties . . . . . . . . 19
1.1.3.3. Recouvrementetpartition . . . . . . . . . . . . . . . . . . 20
1.2. Ordreetéquivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.1. Relationd’ordre . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.2. Relationd’équivalence . . . . . . . . . . . . . . . . . . . . . . . 21
1.3. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1. Partiesetapplications . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.2. Composéed’applications . . . . . . . . . . . . . . . . . . . . . 22
1.3.3. Propriétéspossiblespouruneapplication . . . . . . . . . . . . 22
1.3.3.1. Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3.2. Applicationsimportantes . . . . . . . . . . . . . . . . . . 22
1.4. Enrichissement desensembles:loisdecomposition . . . . . . . . . 23
1.4.1. Lesloisdecomposition . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1.1. Loidecompositioninterne . . . . . . . . . . . . . . . . . 24
1.4.1.2. Loidecompositionexterne . . . . . . . . . . . . . . . . . 24
1.4.2. Propriétéspossiblespourlesloisinternes . . . . . . . . . . . . 24
1.4.2.1. Loiproduit . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.3. Tablecartésienned’uneloiinterne . . . . . . . . . . . . . . . . 25
1.5. Enrichissement desapplications:lesmorphismes . . . . . . . . . . 25
1.5.1. Propriétésd’unmorphisme . . . . . . . . . . . . . . . . . . . . 25
1.6. Ensemblesstructurés . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
56 Algèbre,confidencialitéetintégritéenmultimédia
1.6.1. Groupes,sous­groupes,morphismesdegroupes . . . . . . . . 26
1.6.1.1. Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.6.1.2. Sous­groupes . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.6.1.3. Morphismes . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.6.2. Anneaux,sous­anneaux,idéaux,morphismesd’anneaux . . . 28
1.6.2.1. Anneaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6.2.2. Sous­anneaux,idéaux . . . . . . . . . . . . . . . . . . . . 28
1.6.2.3. Morphismes . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3. Corps,sous­corps,morphismesdecorps . . . . . . . . . . . . 29
1.6.3.1. Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3.2. Sous­corps . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.3.3. Morphismes . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.4. Espacesvectoriels,sous­espacesvectoriels,
applicationslinéaires . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.4.1. Espacesvectoriels . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.4.2. Sous­espacevectoriel . . . . . . . . . . . . . . . . . . . . . 31
1.6.4.3. Applicationslinéaires . . . . . . . . . . . . . . . . . . . . 31
1.6.5. Classeslatéralesd’unesous­structure . . . . . . . . . . . . . . 32
1.6.5.1. Sous­structuresetclasseslatérales . . . . . . . . . . . . . 32
1.6.5.2. Classeslatéralesdunoyaudef etrésolutiond’équations 32
1.6.5.3. Classeslatéralesetstructuresquotients . . . . . . . . . . 33
1.7. Anneauxetcorpsimportants . . . . . . . . . . . . . . . . . . . . . . 33
1.7.1. Anneauximportants:ZetK[X] . . . . . . . . . . . . . . . . . 33
1.7.1.1. Divisioneuclidienne . . . . . . . . . . . . . . . . . . . . . 34
1.7.1.2. Divisionlongue . . . . . . . . . . . . . . . . . . . . . . . . 34
1.7.1.3. Ladivisionlongueetledéveloppementdefractions.. . . 35
1.7.1.4. Lesdeuxordres,PGCDetPPCM . . . . . . . . . . . . . 35
1.7.1.5. Nombrespremiers,polynômesirréductibles . . . . . . . 36
1.7.1.6. L’indicateurd’Euler:ϕ(n) . . . . . . . . . . . . . . . . . 36
1.7.1.7. Une«bonne»application . . . . . . . . . . . . . . . . . . 36
1.7.1.8. Egalitéd’Euclide . . . . . . . . . . . . . . . . . . . . . . . 37
1.7.1.9. Anneauprincipal . . . . . . . . . . . . . . . . . . . . . . . 37
1.7.1.10.EgalitédeBezout . . . . . . . . . . . . . . . . . . . . . . . 37
1.7.1.11.Ladécompositionprimaire . . . . . . . . . . . . . . . . . 38
1.7.1.12.CalculsdePGCD . . . . . . . . . . . . . . . . . . . . . . . 38
1.7.2. Corpsimportants . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.7.2.1. Racinesdepolynômes . . . . . . . . . . . . . . . . . . . . 40
1.7.2.2. IrréductiblessurRousuruncorpsfiniF . . . . . . . . 40q
Chapitre2.Algèbrelinéaire etmultilinéaire . . . . . . . . . . . . . . . . . . . 41
2.1. Quelquespropriétésdebase . . . . . . . . . . . . . . . . . . . . . . . 41
2.1.1. Indépendancelinéaireetdépendancelinéaireder vecteurs . . 41
2.1.2. Systèmesdegénérateurs . . . . . . . . . . . . . . . . . . . . . . 42
2.1.3. Systèmeminimaldegénérateurs . . . . . . . . . . . . . . . . . 42
2.1.4. BasedeE,dimensiondeE . . . . . . . . . . . . . . . . . . . . 42Tabledesmatières 7
2.1.5. Compléterunebased’unsous­espacevectoriel . . . . . . . . . 43
2.1.6. Sommedesous­espacesvectoriels . . . . . . . . . . . . . . . . 44
2.1.7. Sommedirectedesous­espacesvectoriels,supplémentaire . . 44
2.1.8. Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.1.8.1. Représentationd’unvecteur. . . . . . . . . . . . . . . . . 45
2.1.8.2. Représentationd’uneapplicationlinéaire,
etreprésentationdel’imaged’unvecteur . . . . . . . . . 46
2.1.8.3. Représentationd’unesommededeuxapplications
linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.1.8.4. Représentationd’unecomposéededeuxapplications
linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.1.9. Changementdereprésentation . . . . . . . . . . . . . . . . . . 49
2.1.9.1. VecteurdeE . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.1.9.2. Applicationlinéairef deE dansF . . . . . . . . . . . . . 49
2.1.10.Anneauximportantsenalgèbrelinéaire . . . . . . . . . . . . . 50
2.1.10.1.End(E). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.1.10.2.K[h] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.1.10.3.M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51n
2.1.10.4.M [X] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51n
2.1.11.Calculmatriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.1.11.1.Manipulationsélémentaires . . . . . . . . . . . . . . . . . 51
2.1.11.2.Expressionsmatricielles desmanipulationsélémentaires 51
2.1.11.3.AlgorithmedeGauss . . . . . . . . . . . . . . . . . . . . . 52
2.1.11.4.Recherchedel’inversed’unematriceM carrée,d’ordren 53
2.1.11.5.Recherchedenoyau . . . . . . . . . . . . . . . . . . . . . 54
2.1.11.6.Résolutiondesystèmeslinéaires . . . . . . . . . . . . . . 55
2.2. PlusloinenAlgèbreLinéaire . . . . . . . . . . . . . . . . . . . . . . 56
2.2.1. Déterminant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2.1.1. Autresdéveloppementsd’undéterminant . . . . . . . . . 58
2.2.1.2. Propriétésd’undéterminant. . . . . . . . . . . . . . . . . 58
2.2.1.3. DéterminantetalgorithmedeGauss. . . . . . . . . . . . 60
2.2.1.4. Leproduitd’unematriceetdesonadjointe
(verslethéorèmedeCayley­Hamilton) . . . . . . . . . . 61
2.2.1.5. Ledéterminantd’unproduitdedeuxmatricescarrées. . 62
2.2.2. Vecteursetvaleurspropres . . . . . . . . . . . . . . . . . . . . 64
2.2.2.1. Recherchedeλetd’unebasedeF . . . . . . . . . . . . 64λ
2.2.2.2. Propriétésdessous­espacespropres . . . . . . . . . . . . 65
2.2.3. Polynômesremarquablesassociésàunendomorphisme. . . . 65
2.2.3.1. Unepropriétégénérale . . . . . . . . . . . . . . . . . . . . 65
2.2.3.2. Polynômecaractéristique . . . . . . . . . . . . . . . . . . 66
2.2.3.3. Polynômecaractéristiqued’unematricecompagne . . . 67
2.2.3.4. Polynômeminimum . . . . . . . . . . . . . . . . . . . . . 68
2.2.3.5. Polynômeminimumd’unematricecompagne . . . . . . 68
2.2.3.6. Polynômeminimumd’unélémentxdeE . . . . . . . . . 69
2.2.3.7. CalculdePMIN (X),pmin (X)etPCAR (X) . . . . . 69h hx8 Algèbre,confidencialitéetintégritéenmultimédia
2.2.4. Première décompositiondeE ensommedirecte . . . . . . . . 69
k2.2.4.1. LecasparticulierdeKer(p (h)) . . . . . . . . . . . . . . 69
2.2.4.2. Lecasgénéral . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.2.5. RaYnementdeladécompositionensommedirecte . . . . . . 76
2.2.5.1. ConstructionduraYnementdeladécomposition
ensommedirecte . . . . . . . . . . . . . . . . . . . . . . . 78
2.2.6. Lefindufin:ladiagonalisationdeA . . . . . . . . . . . . . . 79
Chapitre3.Groupesetcorpsfinis . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.1. Groupesfinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.1.1. ThéorèmedeLagrange. . . . . . . . . . . . . . . . . . . . . . . 81
3.1.2. Sous­grouped’ungroupecycliquefini . . . . . . . . . . . . . . 81
3.1.3. Groupedespermutations . . . . . . . . . . . . . . . . . . . . . 82
3.1.3.1. Propriétésgénéralesdespermutations . . . . . . . . . . . 82
3.1.3.2. Lasignature . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.2. Corpsfinis:Z/(p)etF [X]/(p(X)) . . . . . . . . . . . . . . . . . . 862
3.2.1. Lesloisdecompositioninternes . . . . . . . . . . . . . . . . . 86
3.2.1.1. LesloisdansZ/(p) . . . . . . . . . . . . . . . . . . . . . . 86
3.2.1.2. LesloisdansF [X]/(p(X)) . . . . . . . . . . . . . . . . . 872
3.2.1.3. Inversesetopposés . . . . . . . . . . . . . . . . . . . . . . 88
3.2.2. Z/(p)etF [X]/(p(X))sontdescorps . . . . . . . . . . . . . . 882
3.2.3. Ordred’unélément,primitifs,nombredeprimitifs. . . . . . . 89
3.2.3.1. Ordred’unélément . . . . . . . . . . . . . . . . . . . . . . 89
3.2.3.2. Primitifs,nombredeprimitifs . . . . . . . . . . . . . . . . 90
3.2.3.3. Primitifsetlogarithmesdiscrets. . . . . . . . . . . . . . . 91
3.2.4. TabledeZechdansZ/(p) . . . . . . . . . . . . . . . . . . . . . 91
3.2.4.1. L’algorithme«petitspas­grandspas» . . . . . . . . . . 92
3.2.4.2. Principe etinterêtd’unetabledeZech . . . . . . . . . . . 92
3.2.4.3. Quelquesexemplesintroductifs . . . . . . . . . . . . . . . 93
3.2.4.4. SimplificationdelaconstructiondestablesdeZech . . . 94
r3.2.5. TabledeZechdansF ,q = 2 . . . . . . . . . . . . . . . . . . . 94q
3.2.5.1. Principe etinterêtd’unetelletable. . . . . . . . . . . . . . 94
3.2.5.2. Quelquesexemplesintroductifs . . . . . . . . . . . . . . . 95
3.2.5.3. SimplificationdelaconstrutiondestablesdeZech . . . . 95
3.2.6. Circuitsélectroniques etcalculspolynomiaux . . . . . . . . . 96
3.2.6.1. Elémentsdebase . . . . . . . . . . . . . . . . . . . . . . . 96
3.2.6.2. Indexationdesbasculesetdesfils. . . . . . . . . . . . . . 97
3.2.6.3. Fonctionnementgénéral . . . . . . . . . . . . . . . . . . . 98
3.2.6.4. CircuitmultiplicateurparX . . . . . . . . . . . . . . . . 99
3.2.6.5. Circuitdiviseur . . . . . . . . . . . . . . . . . . . . . . . . 100
3.2.6.6. Circuitmultiplicateur . . . . . . . . . . . . . . . . . . . . 100
3.2.6.7. Circuitmultiplicateur­diviseur . . . . . . . . . . . . . . . 101
3.2.6.8. Codeurd’uncodecyclique . . . . . . . . . . . . . . . . . 102
3.2.7. Legroupedesracinesn­ièmesdel’unité . . . . . . . . . . . . . 102
3.2.8. ClassescyclotomiquesdansF [X]/(p(X)) . . . . . . . . . . . 1022Tabledesmatières 9
3.2.8.1. Lesclassescyclotomiques . . . . . . . . . . . . . . . . . . 103
3.2.8.2. Polynômeminimumd’unélément . . . . . . . . . . . . . 104
3.2.9. Valeursetracinesdepolynômes . . . . . . . . . . . . . . . . . 105
′ r3.2.9.1. Valeurd’unpolynômeàcoeYcientsdansF ′,q =2 . . 105q
′ r3.2.9.2. Racinesd’unpolynômeàcoeYcientsdansF ′,q = 2 . 106q
3.2.9.3. QuelquespolynômesirréductiblessurF etsurF . . . . 1082 3
Chapitre4.Anneauxfinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.1. Lesloisdecompositioninternes . . . . . . . . . . . . . . . . . . . . 109
4.2. Ordreetinverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3. RésoudreuneéquationaX +b =0dansZ/(n) . . . . . . . . . . . 111
4.4. LestroisproblèmesenArithmétique . . . . . . . . . . . . . . . . . . 111
4.4.1. Enoncésdecesproblèmes . . . . . . . . . . . . . . . . . . . . . 111
4.4.2. Résolutiondecesproblèmes . . . . . . . . . . . . . . . . . . . 111
4.4.3. TransforméesdiscrètedeFourier
(DiscreteFourierTransform,ouDFT) . . . . . . . . . . . . . 114
4.4.3.1. Quelquesdéfinitions . . . . . . . . . . . . . . . . . . . . . 114
4.4.3.2. Propriétésgénérales. . . . . . . . . . . . . . . . . . . . . . 115
4.4.3.3. UnsecondproduitdansA. . . . . . . . . . . . . . . . . . 115
4.4.4. Lesidéaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.5. DécompositiondeZ/(n)etdeF [X]/(a(X)) . . . . . . . . . . . . 1172
4.5.1. Décompositionenproduitdirect . . . . . . . . . . . . . . . . . 117
4.5.1.1. CasdeZ/(n) . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.5.1.2. CasdeF [X]/(a(X)) . . . . . . . . . . . . . . . . . . . . 1182
4.5.2. Décompositionensommedirecte . . . . . . . . . . . . . . . . 119
4.5.2.1. CasdeZ/(n) . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.5.2.2. CasdeF [X]/(a(X)) . . . . . . . . . . . . . . . . . . . . 1202
4.5.3. Lesidempotentsprimitifs . . . . . . . . . . . . . . . . . . . . . 121
4.5.3.1. CasdeZ/(n) . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.5.3.2. CasdeF [X]/(a(X)) . . . . . . . . . . . . . . . . . . . . 1212
4.5.4. Lesdeuxdécompositionssontisomorphes . . . . . . . . . . . 123
4.5.4.1. Unisomorphismeparticulier . . . . . . . . . . . . . . . . 123
4.5.4.2. L’isomorphisme duproduitcartésiensurZ/(n) . . . . . 123
4.5.4.3. L’isomorphisme duproduitcartésiensurF [X]/(a(X)) 1232
4.6. Factorisationdepolynômes . . . . . . . . . . . . . . . . . . . . . . . 124
4.6.1. AlgorithmedefactorisationdeE.Berlekamp . . . . . . . . . . 124
i4.6.2. Commentobtenirp(X)àpartirdep (X) . . . . . . . . . . . . 126
4.7. Quelquescomplexitésd’algorithmes . . . . . . . . . . . . . . . . . . 126
4.7.1. Calculd’unPGCD(Euclide) . . . . . . . . . . . . . . . . . . . 126
4.7.2. Expressiond’unPGCD(Bezout) . . . . . . . . . . . . . . . . . 127
m4.7.3. Calculdex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.7.4. Inversedexmodulon(quandilexiste) . . . . . . . . . . . . . 128
4.7.5. Inversed’unematricecarréed’ordren . . . . . . . . . . . . . . 128
4.7.6. Recherchedunoyaud’unem×nmatrice(m<n) . . . . . . 12810 Algèbre,confidencialitéetintégritéenmultimédia
4.7.7. MéthodedeE.Berlekamp:
factoriserf(X)souslaformef (X)f (X) . . . . . . . . . . . 1291 2
4.7.8. Calculd’undéterminant . . . . . . . . . . . . . . . . . . . . . . 129
4.7.9. CalculdePMIN (X) . . . . . . . . . . . . . . . . . . . . . . . 129h
4.7.10.CalculdePCAR (X) . . . . . . . . . . . . . . . . . . . . . . . 129h
4.7.11.Calculdepmin (X) . . . . . . . . . . . . . . . . . . . . . . . . 129x
4.8. Fractionscontinues. . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.8.1. Del’algorithmed’Euclide àcertainesfractions . . . . . . . . . 130
4.8.2. Desfractionsparticulières . . . . . . . . . . . . . . . . . . . . . 130
4.8.3. Fractioncontinueassociéeàunréelpositif . . . . . . . . . . . 131
4.8.4. Réduited’unefractioncontinue . . . . . . . . . . . . . . . . . 132
4.8.5. Approximationd’unréelpositifparuneréduite . . . . . . . . 133
4.8.5.1. Casd’unirrationnel . . . . . . . . . . . . . . . . . . . . . 133
4.8.5.2. Casd’unrationnel . . . . . . . . . . . . . . . . . . . . . . 133
4.8.5.3. Fractioncontinueetcryptographie . . . . . . . . . . . . . 134
Chapitre5.Cryptographiesymétrique . . . . . . . . . . . . . . . . . . . . . . 135
5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.1.1. Systèmecryptographique . . . . . . . . . . . . . . . . . . . . . 136
5.1.2. Sécuritéinconditionnelle . . . . . . . . . . . . . . . . . . . . . 137
5.1.3. Cryptographiesymétrique . . . . . . . . . . . . . . . . . . . . . 137
5.1.4. Cryptographieasymétrique . . . . . . . . . . . . . . . . . . . . 137
5.1.5. Modèlesd’attaque . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.1.6. Servicesdesécurité . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2. ChiVrementstraditionnels . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.1. Transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.1.1. LaScytale(Sparte,400avantJ.C.) . . . . . . . . . . . . . 140
5.2.1.2. Lagrilletournante . . . . . . . . . . . . . . . . . . . . . . 140
5.2.2. Substitutionsimple . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.2.2.1. ChiVredeCésar . . . . . . . . . . . . . . . . . . . . . . . . 140
5.2.2.2. Rot13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5.2.2.3. ChiVredeWolseley . . . . . . . . . . . . . . . . . . . . . . 141
5.2.2.4. Cryptanalysedessubstitutionssimples . . . . . . . . . . 141
5.2.3. Substitutionspolygrammiques . . . . . . . . . . . . . . . . . . 141
5.2.3.1. ChiVredePlayfair. . . . . . . . . . . . . . . . . . . . . . . 141
5.2.3.2. ChiVredeHill(1929). . . . . . . . . . . . . . . . . . . . . 142
5.2.4. LecarrédeVigenère(1586) . . . . . . . . . . . . . . . . . . . . 143
5.3. ChiVrementsymétriquemoderne . . . . . . . . . . . . . . . . . . . . 144
5.3.1. LechiVrementàflot(streamcipher) . . . . . . . . . . . . . . 144
5.3.1.1. Lemasquejetable(Vernam,1917) . . . . . . . . . . . . . 145
5.3.1.2. Générateurpseudo­aléatoire . . . . . . . . . . . . . . . . 145
5.3.1.3. Leregistrefiltré. . . . . . . . . . . . . . . . . . . . . . . . 146
5.3.1.4. Attaqueparcorrélation . . . . . . . . . . . . . . . . . . . 147
5.3.1.5. Attaquealgébrique . . . . . . . . . . . . . . . . . . . . . . 148
5.3.2. LechiVrementparblocs . . . . . . . . . . . . . . . . . . . . . . 149Tabledesmatières 11
5.3.2.1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
5.3.2.2. Architectured’uncalculparbloc . . . . . . . . . . . . . . 150
5.3.2.3. SchémadeFeistel(1973) . . . . . . . . . . . . . . . . . . 150
5.3.2.4. Réseauxsubstitutions­permutations . . . . . . . . . . . . 151
5.3.3. LeDES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.3.3.1. ArchitecturegénéraleduDES . . . . . . . . . . . . . . . 152
5.3.3.2. Générationdessous­clés . . . . . . . . . . . . . . . . . . . 152
5.3.3.3. DéchiVrement . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.3.3.4. Clésfaibles. . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.3.3.5. LetripleDES . . . . . . . . . . . . . . . . . . . . . . . . . 154
5.3.3.6. LacryptanalysediVérentielle duDES . . . . . . . . . . . 154
5.3.3.7. LacryptanalyselinéaireduDES . . . . . . . . . . . . . . 155
5.3.4. L’AES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
5.3.4.1. LecorpsF . . . . . . . . . . . . . . . . . . . . . . . . . 156256
5.3.4.2. LafonctiondediVusion . . . . . . . . . . . . . . . . . . . 156
5.3.4.3. Laboîte­S . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.3.4.4. Lafonctiondetour . . . . . . . . . . . . . . . . . . . . . . 157
5.3.4.5. Lagénérationdessous­clés . . . . . . . . . . . . . . . . . 158
5.3.4.6. LedéchiVrement . . . . . . . . . . . . . . . . . . . . . . . 158
5.3.4.7. Unexempled’application:
l’accèsconditionnelauxservicesaudiovisuels . . . . . . 158
Chapitre6.Cryptographieàclépublique . . . . . . . . . . . . . . . . . . . . . 161
6.1. LeprotocoleDiYe­Hellman . . . . . . . . . . . . . . . . . . . . . . 161
6.1.1. Fonctionsàsensunique . . . . . . . . . . . . . . . . . . . . . . 161
6.1.2. LanégociationdecléDiYe­Hellman (1976) . . . . . . . . . . 162
6.1.3. L’exponentiationetlelogarithmediscret . . . . . . . . . . . . 163
6.1.4. L’attaquedel’hommeaumilieu . . . . . . . . . . . . . . . . . . 163
6.1.5. LechiVrementElGamal . . . . . . . . . . . . . . . . . . . . . . 163
6.1.6. ChiVrementàdeuxcadenas . . . . . . . . . . . . . . . . . . . . 164
6.1.7. Algorithmesdecalculdulogarithmediscret . . . . . . . . . . 165
6.2. LecryptosystèmedeRabin . . . . . . . . . . . . . . . . . . . . . . . 168
6.2.1. Calculdelaracinecarréemodulon . . . . . . . . . . . . . . . 169
6.2.2. Fonctionàsensuniqueavecportedérobée(trapdoor) . . . . . 170
6.2.3. DéfinitiondusystèmedeRabin . . . . . . . . . . . . . . . . . . 170
6.2.4. SécuritédusystèmedeRabin . . . . . . . . . . . . . . . . . . . 171
6.2.5. Factoriserlesgrandsentiers. . . . . . . . . . . . . . . . . . . . 171
6.3. LeRSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
6.3.1. DescriptiondusystèmeRSA . . . . . . . . . . . . . . . . . . . 173
6.3.2. LasécuritéduRSA. . . . . . . . . . . . . . . . . . . . . . . . . 175
6.4. Signaturenumérique . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
6.4.1. Définitiond’unschémadesignature . . . . . . . . . . . . . . . 177
6.4.2. Fonctionsdehachage . . . . . . . . . . . . . . . . . . . . . . . 17712 Algèbre,confidencialitéetintégritéenmultimédia
6.4.3. LasignatureRSA. . . . . . . . . . . . . . . . . . . . . . . . . . 178
6.4.4. LasignatureElGamal(1985) . . . . . . . . . . . . . . . . . . . 179
Chapitre7.Codescorrecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.1. Unpeud’histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.2. Lebruit,leserreurs,probabilitéd’entréeetprobabilitérésiduelle . 182
7.3. Codessansstructure . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.3.1. Lesparamètresd’uncodeC . . . . . . . . . . . . . . . . . . . . 183
7.3.2. Codage,motémis,motreçu,motd’erreurs,décodage . . . . . 183
7.3.3. Schémagénéraldudécodageàmaximumdevraisemblance . 184
7.3.4. Bornesdesparamètresd’uncode . . . . . . . . . . . . . . . . . 185
7.3.5. Construireuncodesansstructure . . . . . . . . . . . . . . . . 185
7.4. Codeslinéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.4.1. Propriétésdescodeslinéaires . . . . . . . . . . . . . . . . . . . 186
7.4.1.1. Distanceminimaleetpoidsminimum . . . . . . . . . . . 186
7.4.1.2. Base,basesousformesystématique,codage. . . . . . . . 186
7.4.2. Codedual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
7.4.3. Lesclasseslatéralesd’uncodelinéaireC . . . . . . . . . . . . 187
7.4.4. Lessyndromes . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
7.4.5. Décodageetsyndromes . . . . . . . . . . . . . . . . . . . . . . 189
7.4.6. Matricedetestetpoidsminimum decode . . . . . . . . . . . 189
7.4.7. Quelquescodeslinéaires . . . . . . . . . . . . . . . . . . . . . . 190
7.4.8. Décodagedescodeslinéaires . . . . . . . . . . . . . . . . . . . 190
7.5. Codescycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.5.1. Propriétésd’uncodecyclique . . . . . . . . . . . . . . . . . . . 191
7.5.2. Based’uncodecyclique(g(X)) . . . . . . . . . . . . . . . . . . 192
7.5.3. Annulateurd’uncodecycliqueC . . . . . . . . . . . . . . . . . 193
7.5.4. Puissancedecorrectiond’uncodecyclique:lesracinesdeg(X) 193
7.5.5. ThéorèmedeBCH . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.5.6. Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.5.7. Syndromes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.5.8. Codestronqués,etcodesétendus . . . . . . . . . . . . . . . . . 195
7.5.8.1. Codestronqués . . . . . . . . . . . . . . . . . . . . . . . . 195
7.5.8.2. Codesétendus . . . . . . . . . . . . . . . . . . . . . . . . . 196
7.6. Quelquescodescycliques . . . . . . . . . . . . . . . . . . . . . . . . 196
7.6.1. CodesdeHamming . . . . . . . . . . . . . . . . . . . . . . . . 196
7.6.2. CodesBCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
7.6.3. CodesRM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
7.6.4. CodesRS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
7.6.5. CodesàdistancevraiesupérieureàleurdistanceBCH . . . . 198
7.7. Existenceetconstructiondecodescycliques . . . . . . . . . . . . . 198
7.7.1. Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
7.7.2. Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.7.2.1. UtilisationdesclassesdeZ/(n) . . . . . . . . . . . . . . . 199
n7.7.2.2. UtilisationdelafactorisationdeX −1 . . . . . . . . . 200Tabledesmatières 13
7.7.3. Cahierdescharges . . . . . . . . . . . . . . . . . . . . . . . . . 200
7.7.4. Commentchercheruncodecyclique . . . . . . . . . . . . . . . 200
7.7.5. Exempled’unetellerecherche . . . . . . . . . . . . . . . . . . . 201
7.7.6. Commentchercheruncodecycliquetronqué . . . . . . . . . . 202
7.8. Deuxdécodagesdecodescycliques . . . . . . . . . . . . . . . . . . 202
7.8.1. DécodageparlaDFT . . . . . . . . . . . . . . . . . . . . . . . 203
7.8.2. Décodageparl’algorithmedeBerlekamp­Massey . . . . . . . 205
7.8.2.1. Définitionsetpremières propriétés . . . . . . . . . . . . . 206
7.8.2.2. L’étudedeEV . . . . . . . . . . . . . . . . . . . . . . . . 206
7.8.2.3. L’équation­clé . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.8.2.4. Constructionde(A ,B ) . . . . . . . . . . . . . . . . 208i+1 i+1
7.8.2.5. IlfautA (0)= 1 . . . . . . . . . . . . . . . . . . . . . . . 209i
7.8.2.6. Optimisationdelasolution(A ,B ) . . . . . . . . . . . . 209i i
−1 −17.8.2.7. Lasolution(A +μ δa ,B +μ δb )estoptimalei i i i
aurangi+1 . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.8.2.8. Déterminationducouple(a ,b ) . . . . . . . . . . . 212i+1 i+1
7.8.2.9. Initialisationdelarécurrence . . . . . . . . . . . . . . . . 212
ˆ7.8.2.10.L’obtentiondeLetdeEV. . . . . . . . . . . . . . . . . . 213
7.8.3. AlgorithmedeBerlekamp­Massey . . . . . . . . . . . . . . . . 213
7.9. Applicationsdescodes . . . . . . . . . . . . . . . . . . . . . . . . . . 214
7.10. Codesetcryptographie . . . . . . . . . . . . . . . . . . . . . . . . . 216
7.10.1.Utilisationd’uncodecorrecteurencryptographie . . . . . . . 216
7.10.2.Unepremière attaque . . . . . . . . . . . . . . . . . . . . . . . 216
7.10.3.Unepremière contre­attaque . . . . . . . . . . . . . . . . . . . 217
7.10.4.Unesecondeattaque . . . . . . . . . . . . . . . . . . . . . . . . 217
7.10.5.Laparade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Chapitre8.Exercices etproblèmes . . . . . . . . . . . . . . . . . . . . . . . . 219
Enoncés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.1. Chapitres1et2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.1.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 219
8.1.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 221
8.1.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
8.2. Chapitres3et4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
8.2.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 226
8.2.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 228
8.2.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.3. Chapitres5et6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
8.3.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 235
8.3.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 236
8.3.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
8.4. Chapitre7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.4.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 243
8.4.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 245
8.4.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24614 Algèbre,confidencialitéetintégritéenmultimédia
Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
8.5. Chapitres1et2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
8.5.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 250
8.5.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 252
8.5.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.6. Chapitres3et4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
8.6.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 260
8.6.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 265
8.6.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
8.7. Chapitre5et6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
8.7.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 277
8.7.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 279
8.7.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
8.8. Chapitre7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8.8.1. Exercices decompréhension. . . . . . . . . . . . . . . . . . . . 285
8.8.2. Exercices deréflexion . . . . . . . . . . . . . . . . . . . . . . . 287
8.8.3. Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297Introduction
Cet ouvrage contient 8 chapitres, le dernier étant consacré à 200 exercices et
problèmes accompagnés de leurs corrigés complets. Les exercices sont classés en
deuxniveauxdediYcultéscroissantes:compréhension(C)etréflexion(R).
Leschapitres1,2,3,4et7ontétéécritsparA.Poli,etleschapitres5et6par
P.Guillot.
Dans le chapitre 1, nous donnons les connaissances de base en algèbre, puis
nous montrons comment on combine les notions élémentaires d’éléments, d’en­
sembles et d’applications, pour les enrichir et créer ainsi les ensembles structurés
etlesmorphismes.Cettepartieestaccessiblesanspré­requis.
Le chapitre 2 est consacré à l’algèbre linéaire et multilinéaire (déterminants,
résolution de systèmes linéaires, traitement de matrices, décomposition d’un es­
pace vectoriel en somme directe, diagonalisation de matrices). Cette partie est
accessibledirectementouaprèslecturedupremierchapitre.
Leschapitres3et4sontdédiésauxstructuresalgébriquesfinies.Cesstructures
finiessontdevenuesindispensablesaudéveloppementdutraitementdel’informa­
tion depuis la numérisation des données. Nous y étudions, de manière poussée,
les groupes finis (permutations,etc.), les anneauxfinis, les corps finis. Des exem­
ples constructifs précèdent les propositions délicates. Un passage est consacré à
certainscircuits électroniques réalisantdescalculs dansles corpsfinis,unautreà
l’analysedela«complexité».
Ces deux chapitres préparent l’étude de la cryptographie et des codes correc­
teurs.Ilspeuventêtrelusdirectement,maissontd’unniveauplusélevé.
Les chapitres 5 et 6 sont consacrés à la cryptologie qui est l’art de garantir la
protection de l’informationen confidentialité, en intégrité. Les notionsgénérales
sont introduites dans le chapitre 5 qui traite également des systèmes de crypto­
graphie traditionnels et symétriques modernes, dans lesquels les correspondants
partagentunedonnéesecrèteconnued’euxseuls.Lacryptographieàclépublique,
1516 Algèbre,confidencialitéetintégritéenmultimédia
qui s’aVranchit du besoin de procéder à l’échange préalable de cette donnée se­
crète, et quipermet ausside développer un équivalent numérique de la signature
desdocuments,estprésentéeauchapitre6.
Le chapitre 7 traite des codes correcteurs, qui permettent la correction d’er­
reursentransmissionouenenregistrementdedonnéesenmultimédia.
Ce chapitre contient de nombreuses constructions détaillées et des exemples
deréalisationsréelles passéesdanslaviecourantedepuislongtemps.
Cet ouvrage s’adresse aux étudiants de DUT, Deug ou Licence. L’exposé de
ce livre se suYsant à lui­même, l’ouvrage s’adresse également aux autodidactes
curieuxdesliensentrethéorieetapplications,etauxingénieursdésirantcompléter
leursconnaissancesdansledomainedel’algèbreappliquéeaumultimedia.
Alain Poli
Professeur,universitéP aul Sabatier,Toulouse
P hilippe Guillot
Maîtredeconférences,UniversitéParisVIII
Remerciements
Noustenonsàremercier particulièrement:
YvesSoulet, Professeur honoraire,poursalecture soigneuse dumanuscrit, et
poursonremarquabletravaildemiseenforme.
PourleursprécieusesinformationssurlesapplicationsdesCodesCorrecteurs:
Max Ferréol et François Lasserre, ingénieurs CNES, Toulouse (Centre Natio­
nald’Études Spatiales),ainsi que Philippe Piret, ancien ingénieur chez Philips et
Canon.Chapitre1
Elémentsd’algèbre
Deuxnotionssontfondamentales:celle d’ensemble,etcelle d’application.
Après les avoir traitées, dans leur généralité, nous montrons comment elles
permettent d’enrichir les ensembles (on obtient des ensembles structurés) et les
applications(onobtientdesmorphismes).Pourchaquetyped’ensemblestructuré
(groupe,anneau,corps,espacevectoriel),nousprésentons,systématiquement,les
structures,lessous­structures,etlesmorphismes.
Enfin,cechapitrefaitunebonnepartàl’algèbrelinéaire,dontlesapplications
sont multiples. Déterminants et décompositions en somme directe d’un espace
vectorielsontdéveloppésendétails,defaçonconstructive,jusqu’àladiagonalisa­
tion.
1.1. Ensembles
Nous admettronsque les notionsd’ensemble, d’élément d’un ensemble, d’ap­
partenance à un ensemble, sont des notions «primitives», c’est­à­dire acquises
parchacun,deparsonexpérience.
Exemples 1.1.– L’ensemble des papillons d’une collection, des chaises d’une
salledecours,l’ensembleE desentierspairs.
Pour exprimer que l’entier 14 appartient àE, on note 14∈ E. Pour dire que
13n’estpasdansE,onnote13∈/ E.
Si E a pour éléments 1, 2 et 3, on écrit E ={1,2,3}. L’ordre dans lequel
apparaissentleséléments n’apasd’importance,onpourraitécrireE ={3,2,1}.
Nous admettrons également comme étant primitive la notion de correspon­
dance d’un ensembleE vers un ensembleF : àchaque élément deE on faitcor­
respondreunouplusieursélémentsdeF.
1718 Algèbre,confidencialitéetintégritéenmultimédia
Exemple 1.2.– SoientE ={1,2,3}etF ={a,b,c}.Définissonsf parf(1)=a,
f(1)=c,f(2)=b,f(3)=a.f estunecorrespondancedeE versF.
1.1.1. Ensemblesfinisouinfinis
Dfinition 1.1.– Un ensembleE sera dit fini s’il a un nombre fini d’éléments.
CenombreestappelélecardinaldeE.IlestnotéCard(E)ou|E|.
Exemples 1.3
1)SoitE ={a,b,c,d,e}.Ona|E| =5.
2){0,1}auncardinalégalà2,et{0,1,2}auncardinalégalà3.
Unensemblenecontenantqu’unélémentestditunsingleton.S’iln’encontient
aucunilestappeléensemblevide,etestnoté∅.
Dfinition 1.2.– UnensembleE seraditinfinis’iln’estpasfini.
Exemples 1.4.– L’ensemble N des entiers naturels{0,1,2,3,...}, l’ensemble Z
desentiersrelatifs{...,−2,−1,0,1,2,...},l’ensembleQdesfractionsrationnelles,
l’ensembleRdesnombresréels,l’ensemble desvecteursduplan,d’origineO.
Dfinition 1.3.– On dit qu’un ensembleF est inclus dansun ensembleE si et
seulement si toutélément deF est un élément deE. On note alorsF⊆ E. Pour
exprimer,enplus,queF estdiVérentdeE onnoteF⊂E.
1.1.2. Partiesd’unensemble,ensembledespartiesd’unensemble
Dfinition 1.4.– UnepartieF d’unensembleE estunensembled’élémentsde
E.OnditaussiqueF estunsous­ensembledeE.
Exemples 1.5
1)PosonsE ={a,b,c,d,e}.Alors,{a,c,d}estunepartiedeE.
2)L’ensemble desentiersimpairsestunepartiedeN.
E est une partie de E, appelée partie pleine. La partie vide est la partie de
E qui ne contient aucun élément. Elle est notée∅. Une partie de cardinal 1 est
appeléeunsingleton.
Pour démontrer l’égalité de deux partiesA etB, il est souvent plus facile de
prouverB⊆AetA⊆B.
Dfinition 1.5.– L’ensemble despartiesdeE estnotéP(E).
Exemples 1.6
1)SoitE ={a,b}.OnaP(E)={∅,{a},{b},E},et|P(E)|= 4.
2)SoitE =∅.OnaP(E)={∅,{∅}}6
6
Elémentsd’algèbre 19
Proposition 1.1
n1)SiE estfini,decardinaln,alors|P(E)| =2 .
2)SiE estinfini,alorsP(E)estinfini.
Dmonstration
1)ParrécurrencesurlecardinalndeE.
Pourn =1,P(E)={∅,E},et|P(E)| =2.
nPourn≥2,posonsE ={e ,e ,..,e },etsupposons|E|= 2 .1 2 n
′ ′ nConsidéronsE ={e ,e ,..,e ,e }.DansP(E )ilya2 partiessanse ,1 2 n n+1 n+1
n ′ n net2 partiesavece .DansE ilyadonc2 +2 parties.n+1
2)Parmilesparties,ilyalessingletons,quisontennombreinfini.
1.1.3. Constructiond’ensemblesàpartird’ensembles,departiesàpartirdeparties
1.1.3.1. Constructiond’ensemblesàpartird’ensembles
Dfinition 1.6.– Le produit cartésien de deux ensemblesE etF, notéE×F,
estdéfinipar:E×F ={(x,y)/x∈E,y∈F}(i.e. l’ensemble descouples(x,y)
telsquexsoitdansE,ety dansF).
On peut faire le produit cartésien d’un nombren quelconque d’ensembles. Si
ntouslesensemblessontégauxàE leurproduitsenoteE .
Onnoteraqu’uncouple(x,y)estordonné.SiE =F alorsE×F =F×E.
Lorsque|E|=net|F|=m,ona|E×F|=nm
Proposition 1.2.– Dans un produit cartésien d’ensembles, il y a des parties qui
nesontpaségalesàunproduitcartésiendeparties.
Dmonstration.– SoientE ={1,2},F ={a,b,c}.
OnaE×F ={(1,a),(1,b),(1,c),(2,a)(2,b),(2,c)}.
P ={(1,a),(2,b)}ne peutêtre le produitcartésien dela formeA×B,sinon
1et2seraientdansA,aetbseraientdansB,etdonc(1,b)seraitdansP.
1.1.3.2. Constructionsdepartiesàpartirdeparties
SoitE unensemble,AetBdeuxpartiesdeE.Pardesconnecteursparticuliers
ondéfinitd’autresparties:
• Intersection de A et de B : c’est l’ensemble des éléments de E qui appar­
tiennentàlafoisàAetàB.
OnnoteA∩B,etonécritA∩B ={x∈E/x∈Aetx∈B}.
• UniondeAetB :c’estl’ensembledesélémentsdeE quiappartiennentsoit
àAsoitàB,éventuellementauxdeux.
OnnoteA∪B,etonécritA∪B ={x∈E/x∈Aoux∈B}.
• DiVérence symétriqueentreAetB :c’est l’ensemble deséléments deE qui
appartiennent soit àA soit àB, mais pas aux deux. On noteA△B, et on pose
A△B ={x∈E/x∈A∪B etx∈/ A∩B}.20 Algèbre,confidencialitéetintégritéenmultimédia
• Complémentaire de A : c’est l’ensemble des éléments de E qui n’appar­
tiennentpasàA.Onnote:A={x∈E/x∈/ A}.
• DiVérence entre A et B : c’est l’ensemble des éléments de E qui appar­
tiennentàAmaispasàB.
OnnoteA\B,etonposeA\B ={x∈E/x∈Aetx∈/ B}.
1.1.3.3. Recouvrementetpartition
Dfinition 1.7.– Un recouvrement d’un ensembleE est une famille de parties
non vides deE, dont la réunion est égale àE. Une partition deE est un recou­
vrementdontlespartiessontdisjointes2à2.
Exemples 1.7
1){A,A}estunepartitiondeE,pourtoutepartieAdeE,
2) Soit E ={1,2,3,4,5,6}.Posons F ={1,4},F ={2,3,5},F ={6}.1 2 3
Alors{F ,F ,F}estunepartitiondeE.1 2 3
3)SoitE ={a,b,c,d,e}.SoientF ={a,c,d},F ={b,c,a},F ={e,d}.La1 2 3
famille{F ,F ,F}estunrecouvrementdeE,maispasunepartition.1 2 3
1.2. Ordreetéquivalence
SoitE unensemble. Considéronsunephrase,«R(x,y)»,contenantdeuxpa­
ramètresx ety parcourantE. R(x,y) peut être vraie ou fausse,selon les valeurs
prises par x et y. R(x,y) est appelée une relation binaire sur E. Pour dire que
R(x,y)estvraieonnoterasimplementR(x,y).
Ilyadeuxrelationsbinairesimportantes,quenousdécrivonsmaintenant.
1.2.1. Relationd’ordre
Dfinition 1.8.– R(x,y) est une relation d’ordre (ou un ordre) si et seulement
silesaxiomessuivantssontvérifiés:
1)R(x,x)(réflexivité),
2)(R(x,y)etR(y,z))⇒R(x,z)(transitivité),
3)(R(x,y)etR(y,x))⇒x=y (antisymétrie).
Exemples 1.8
1) SoitE = Z. SoitR(x,y) = « x−y estdivisiblepar2».R(x,y) n’est pas
unordre,carl’axiome3)n’estpassatisfait.
2)SoitE =N.SoitR(x,y)= « xdivisey»(onnoteaussix|y).R(x,y)estun
ordre.LorsqueR(x,y)estvraieonécritxy.Onditalorsquexestunminorant
(ouundiviseur)dey,etquey estunmajorant(ouunmultiple)dex.
Cetordres’appellel’ordrededivisibilité.
3)DansP(E),l’inclusion est un ordre partiel, toutà faitanalogue àla divisi­
bilité.
Dfinition 1.9.– R(x,y)estditunordretotallorsqueR(x,y)faux ⇒R(y,x),
ilestditunordrepartielsinon.Elémentsd’algèbre 21
1.2.2. Relationd’équivalence
Dfinition 1.10.– R(x,y) est une relation d’équivalence (ou une équivalence)
sietseulementsilesaxiomessuivantssontvérifiés:
1)R(x,x),
2)(R(x,y)etR(y,z))⇒R(x,z),
3)R(x,y)⇒R(y,x)(symétrie).
Dfinition 1.11.– On appelle classe d’équivalence de a la partie de E, notée
C ,définieainsi:C ={b∈E/R(a,b)}.a a
Proposition 1.3.– L’ensembledesclassesd’équivalenceestunepartitiondeE.
Dmonstration.– SansdiYculté.
Exemple 1.9.– SoitE =Z.SoitR(x,y) = « x−y estdivisiblepar2».R(x,y)
estuneéquivalence.Ilyadeuxclassesd’équivalence,C etC .0 1
1.3. Applications
SoientE etF deuxensembles,etf unecorrespondancedeE versF.
Dfinition 1.12.– f estuneapplicationdeE dansF sietseulementsiàchaque
élémentxdeE elle faitcorrespondreunetunseulélémenty deF,notéf(x).
Exemple 1.10.– SoientE ={1,2,3,4}etF ={a,b,c}deux ensembles. Soitf
unecorrespondancedeE versF.
Sif(1) = a, f(3) = b,f(2) = a,f(2) = c,f(4) = b, alorsf n’est pas une
application.
Sif(1)=a,f(2)=b,f(3)=c,f(4)=c,alorsf estuneapplication.
Lorsquey =f(x),onditqueyestl’imagedex,etquexestl’antécédentdey.
Dfinition 1.13.– SoientE etF deuxensembles,etdeuxapplicationsf etgde
E dansF.
Onditquef =g sietseulementsif(x) =g(x)pourtoutxdeE.
1.3.1. Partiesetapplications
SoientE etF deux ensembles,A une partie deE, etf une application deE
dansF.
Dfinition 1.14.– L’ensemble B des images des éléments deA est notéf(A).
On ditquef(A) est l’image deA.L’ensemble des antécédents deséléments deB
−1estnotéf (B).Onécrit:B ={y∈F/∃x∈A,y =f(x)}.
−1OnnotesouventIm(f)àlaplacedef(E).Siy∈/ Im(f)onaf (y) =∅.6
22 Algèbre,confidencialitéetintégritéenmultimédia
−1Onremarqueraquef (B)⊇A.Ilpeutnepasyavoirégalité.
−1On observera quef n’est pas, en général, une application, mais seulement
unecorrespondance.
Exemple 1.11.– E = {1,2,3,4,5},F = {a,b,c},A = {1,2,5},f(1) = a,
f(2)=c,f(3)=a,f(4)=b,f(5)=c.
−1Onaf(A)={a,c},f (f(A)) ={1,2,3,5}=A.
1.3.2. Composéed’applications
Soient E, F et G trois ensembles, f une application de E dans F, et g une
applicationdeF dansG.
Dfinition 1.15.– ∀x ∈ E posons y = f(x), et z = g(y). A cet x on peut
associerl’élémentz.CetteasssociationestuneapplicationdeEdansG,appeléela
composéedef etdeg.Onlanoteg◦f,etonécrit(g◦f)(x) =g(f(x)) =g(y)=z.
Onpeutcomposerplusdedeuxapplications.
DanslecasoùE =F,etoùf estuneapplicationdeE dansE,onpeutdéfinir
n 0lacomposéedenfoisl’applicationf.Onlanotef .Parconventionf = id.
Exemple 1.12.– SoientE ={1,2,3,4},f(1) = 2,f(2) = 4,f(3) = 2,f(4) =
3 3 3 31.Onaf (1) =1,f (2)= 2,f (3)= 1,f (4)=4.
1.3.3. Propriétéspossiblespouruneapplication
SoientE etF deuxensembles,etf uneapplicationdeE dansF.L’application
f peutavoircertainespropriétés.
1.3.3.1. Propriétés
• Injectivité : si et seulement sif(x) = f(y) implique x = y (une image n’a
qu’unantécédent).
• Surjectivité:sietseulementsitouty deF aaumoinsunantécédent,cequi
senote:∀y∈F,∃x∈E/y =f(x).
• Bijectivité :sietseulementsiinjectivitéetsurjectivité.
Proposition 1.4.– Soit f une application injective deE dansF. Si|E| =|F|,
alorsf estbijective.
Dmonstration.– |f(E)|=|F|.ToutélémentdeF adoncunantécédent.
1.3.3.2. Applicationsimportantes
• Application identique deE : elle est notée id ou id s’il n’y a pas d’ambi­E
guité, et elle est définie par : id (x) = x,∀x∈ E. On rappelle que, par conven­E
0tion,f = idpourtouteapplicationf.Elémentsd’algèbre 23
• Application inverse ou réciproque : soient E et F deux ensembles, f une
applicationdeE dansF,etg uneapplicationdeF dansE,avecg◦f = id .OnE
−1ditqueg estl’applicationinversedef,etonlanotef .
Exemple 1.13.– SoientE ={1,2,3}etF ={a,b,c}.Soitf uneapplicationde
−1E dansF, définie parf(1) = b,f(2) = a,f(3) = c. L’application inverse,f ,
−1 −1 −1estdéfinieparf (b)= 1,f (a) =2,f (c) =3.
• Permutations:soitE unensemble,f uneapplicationdeE dansE.Sif est
bijectiveonditquef estunepermutationdeE.
Exemples 1.14
SoitE ={1,2,3,4}.
a)Unepermutationσ est,parexemple,définieparσ(1) =3,σ(2)= 4,σ(3)=
1,σ(4)= 2.
b) Une transpositionτ est une permutationquin’échange que deuxéléments
entreeux.Parexemple,τ(1) = 2,τ(2)= 1,τ(3)=3,τ(4) =4.
Ondémontre(voirchapitre3)quetoutepermutationσsedécomposeencom­
position de transpositions. On prouve aussi que, si une permutation est obtenue
pardeuxcompositionsrespectivementderetstranspositions(σ =τ ◦···◦τ =1 r
′ ′τ ◦···◦τ )alorslesentiersr etsontmêmeparité.1 s
• Suites:soitE unensembleetf uneapplicationdeNdansE,quiàchaquen
deNassocieunélémentdeE,notéu (aulieudef(n)).Lapartie{u ,u ,u ,...}n 0 1 2
deE estditeunesuitesurE.Unesuiteestordonnée,onlanote(u ,u ,u ,...).0 1 2
• Matrices:soientI ={1,2,...,n},etJ ={1,2,...,m},pournetmfixés.Soit
E unensembleetf uneapplicationqui,àchaquecouple(i,j)deI×J associeun
élémentdeE,notéu (aulieudef(i,j)).Onreprésentel’ensembledecesimagesi,j
paruntableauU (unematrice),ànlignes etm colonnes,et le terme en lignei et
colonnej estu .Onditquec’estunematricen×m.i,j
Sin =monditqu’onaunematricecarréed’ordren.
tDfinition 1.16.– Onappelle transposéedeU,lamatricenotéeU ,àmlignes
etncolonnes,dontletermeenligneietcolonnej estu .j,i
Exemple 1.15.– n= 2,m =3.  
u u1,1 2,1
u u u1,1 1,2 1,3 t  PourU = ,onaU = u u .1,2 2,2u u u2,1 2,2 2,3
u u1,3 2,3
1.4. Enrichissementdesensembles:loisdecomposition
Apartird’ensemblesetd’applications,onvaobtenirdesensemblesplusriches,
etdesapplicationsnonbanales.24 Algèbre,confidencialitéetintégritéenmultimédia
1.4.1. Lesloisdecomposition
1.4.1.1. Loidecompositioninterne
2Soit E un ensemble, et une application f deE dansE. On notez = x∗y
plutôt quef(x,y) = z,et on dit que∗ est une loi de composition interne (ou loi
interne)définiesurE.
1.4.1.2. Loidecompositionexterne
Soient E et F deux ensembles, et f une application deF×E dansE. Pour
a ∈ F et x ∈ E, plutôt que d’écrire z = f(a,x) on note z = a·x ou, plus
simplement, z = ax. On dit que «·» est une loi de composition externe (ou loi
externe)définiesurE.
1.4.2. Propriétéspossiblespourlesloisinternes
• Associativité : une loi∗ est dite associative si et seulement sia∗ (b∗c) =
(a∗b)∗c.
• Existenced’unélément neutreetelquee∗x =x∗e =x,pourtoutx.Sila
loiestnotée+leneutreestnoté0,silaloiestnotée×,ilestnoté1.
′ ′
• Existenced’unsymétrique:pourtoutxdeE ilexisteunx telquex∗x =
′ ′x∗x =e.Onditquex estlesymétriquedex.Silaloiestnotée+lesymétrique
est dit l’opposé, on le note−x. Si la loi est notée× il est dit l’inverse, on le note
−1x (ou1/x).
• Distributivité : une loi∗ est dite distributive par rapport à une loi ⊺ si et
seulementsia∗(b⊺c)= (a∗b)⊺(a∗c)et(b⊺c)∗a = (b∗a)⊺(c∗a),pourtous
a,b,c.
• Commutativité:uneloi∗estditecommutativesietseulementsix∗y =y∗x,
pourtousxety.
Proposition 1.5.– SoitE un ensemble muni d’une loi interne et associative, no­
tée∗.
1)S’ilexisteunneutre,alorsilestunique.
2)Siunélément aunsymétrique,alorscesymétriqueestunique.
Dmonstration
1)Soiente ete deuxneutres.Onae ∗e =e =e .1 2 1 2 1 2
′ ′′ ′ ′′2) Soient x et x deux symétriques de x. On a x∗x = x ∗x = e, puis
′ ′ ′′ ′ ′′ ′′x =e∗x =x ∗x∗x =x ∗e =x .
1.4.2.1. Loiproduit
SoientE etF deuxensembles,munidesloisrespectives∗et⊺.DansE×F on
′ ′ ′ ′définitsouventuneloiinterne(loiproduit),«·»,par(x,y)·(x,y )= (x∗x,y⊺y ).Elémentsd’algèbre 25
1.4.3. Tablecartésienned’uneloiinterne
QuandE estfini,onpeutreprésenteruneloiinterneparuntableau.
Exemples 1.16
• OnpeutmunirF ={0,1}dedeuxloisnotées+et×,donnéesparlestables2
cartésiennessuivantes:
+ 0 1 × 0 1
0 0 1 0 0 0
1 1 0 1 0 1
• OnpeutmunirF ={0,1,2}dedeuxloisnotées+et×:3
+ 0 1 2 × 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1
• OnpeutmunirE ={0,1,2,3}dedeuxloisnotées+et×:4
+ 0 1 2 3 × 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1
1.5. Enrichissementdesapplications:lesmorphismes
Quand on considère deux ensembles structurés (E,∗) et (F,⊺), certaines ap­
plicationsdeE dansF possèdentdespropriétésriches:cesontdesmorphismes.
Dfinition 1.17.– Onditqu’uneapplicationf,deE dansF,estunmorphisme
de(E,∗)dans(F,⊺)sietseulement sionaf(x∗y) =f(x)⊺f(y),pourtousxet
y deE.
Un morphisme f est un endomorphisme deE si et seulement siF = E, un
monomorphismesietseulementsiilestinjectif,unépimorphismesietseulement
si il est surjectif, un isomorphisme si et seulement si il est bijectif, un automor­
phismesietseulementsiilestunendomorphismebijectif.
1.5.1. Propriétésd’unmorphisme
Soitf unmorphisme de(E,∗)dans(F,⊺). SupposonsqueE possèdeunélé­
′ment neutree, et queF ait un neutree . Supposons aussiqu’il existe unx deE,
′ayantunsymétriquex .26 Algèbre,confidencialitéetintégritéenmultimédia
Proposition 1.6
′1)f(e)=e .
′ ′2)f(x) =(f(x)) .
Dmonstration
1)Dex=e∗x =x∗evientf(x) =f(e∗x) =f(e)⊺f(x)=f(x)⊺f(e)),et
′f(e)=e.
′ ′ ′ ′ ′2)Onae =x∗x (=x∗x),d’où:e =f(e)=f(x)⊺f(x)(=f(x )⊺f(x)),
′cequiprouvequef(x )estlesymétyriquedef(x).
′Dfinition 1.18.– L’ensemble des x deE tels quef(x) = e est noté Ker(f),
onditquec’estlenoyaudef.
Etudions, maintenant, ce que deviennent les ensembles avec des lois internes
ouexternes,puiscequel’onpeutdiredesmorphismes.
1.6. Ensemblesstructurés
Muni d’une ou de plusieurs lois de composition, un ensemble devient assez
richepourqu’onpuisseydémontrerdesthéorèmes.Onditqu’untelensembleest
structuré.Certainespartiespeuventl’êtreaussi.Cesontdessous­structures.
OnprouveraqueKer(f)etIm(f)sontdetellessous­structures.
1.6.1. Groupes,sous­groupes,morphismesdegroupes
1.6.1.1. Groupes
Cette structure provient de l’étude des permutations d’éléments d’ensembles
finis.
Dfinition 1.19.– Un ensemble G, muni d’une loi∗, est dit un groupe si et
seulementsilesaxiomessuivantssontvérifiés:
1)∗estinterne,
2)∗estassociative,
3)∗possèdeunneutree,
′4)pourtoutxdeGilexisteunsymétriquex dansG.
Danslecasoù∗est,enplus,commutative,onditquelegroupeestcommutatif
ouabélien.Onnoteungroupepar(G,∗)ousimplementG,silaloiestimplicite.
Exemples 1.17
• F (voir§4.3)estungroupepourlaloi+(onditquec’estungroupeadditif).2
L’opposéde1est1,autrementdit−1= 1.

• F estungroupeadditif.F \{0}(notéaussiF )estungroupemultiplicatif.3 3 3
L’opposé de 2 est 1, autrement dit−2 = 1. L’inverse de 2 est 2, autrement dit
−12 =2.
• E est un groupe additif. E \{0} n’est pas un groupe multiplicatif, car4 4
l’élément 2n’apasd’inverse.Elémentsd’algèbre 27
1.6.1.2. Sous­groupes
Dfinition 1.20.– Un sous­groupe n’est rien d’autre qu’un groupe dans un
groupe.
Proposition 1.7.– Soit(G,∗)ungroupe.Pourprouverqu’unepartieH deGest
unsous­groupe(H,∗),ilsuffitdevérifier que:
1)H estnonvide,
2)∗estinternepourH,
′3)PourtoutxdansH,x estdansH.
Dmonstration.– Les autres axiomes sont vérifiés : d’une part, l’associativité
′estpartoutvraie,d’autrepart,ilexisteunxdansH (H estnonvide),etx∗x est
dansH (∗estinterneàH),doncleneutreeestdansH.
Il existe une façon plus concise de prouver qu’on a aVaire à un sous­groupe.
C’estcequenousprouvonsmaintenant.
Proposition 1.8.– Soit(G,∗)ungroupe.Pourprouverqu’unepartieH deGest
unsous­groupe(H,∗),ilsuffitdevérifier que:
1)H estnonvide,
′2)x∗y ∈H pourtousx,y∈H.
Dmonstration.– Supposonsquelespoints(1)et(2)soientvérifiés.
Parlepoint1),H estnonvide,ilcontientaumoinsunx.Parlepoint2),ona
′ ′ ′ ′e =x∗x ∈H.Sixety sontdansH,alorsx,y ∈H,etx∗(y ) =x∗y∈H.
Parlapropositionprécédente,H estunsous­groupe.
Laréciproqueestdirecte.
1.6.1.3. Morphismes
′Soientdeuxgroupes(G,*)et(H,⊺),deneutresrespectifseete ,etuneappli­
cationf deGdansH.
Dfinition 1.21.– Sif(x∗y)=f(x)⊺f(y),alorsf estunmorphismedegroupe.
Unmorphismeengendredeuxsous­structuresimportantes:Ker(f)etIm(f).
Proposition 1.9
1)Ker(f)estunsous­groupedeG.
2)Im(f)estunsous­groupedeH.
3)f estinjective sietseulementsiKer(f)={e}.6
6
28 Algèbre,confidencialitéetintégritéenmultimédia
Dmonstration
1)e∈Ker(f)(proposition1.6),doncKer(f)=∅.
′ ′ ′Soitx,y∈ Ker(f). Alorsf(x∗y) = f(x)⊺f(y) = e ⊺e = e . Donc∗ est
interne.
′ ′ ′ ′ ′ ′Soitx∈ Ker(f).Onaf(x∗x)=f(e)=e =f(x)⊺f(x )=e⊺f(x) =f(x ).
′Doncx estdansKer(f).
′2)e ∈Im(f),doncIm(f)=∅.
Soit y,z ∈ Im(f). Alors, pour certains a et b, on a y ⊺z = f(a)⊺f(b) =
f(a∗b)∈ Im(f).Donc⊺estinterne.
′ ′Soity =f(a)∈ Im(f).Alorsy =f(a )∈ Im(f).
′ ′3) Supposons Ker(f) ={e}. Alorsf(x) = f(y) implique f(x∗y ) = e , et
′ ′x∗y ∈Ker(f).Doncx∗y =e,etx =y.f estinjective.
′Supposons f injective. Soit f(y) = e . Alors f(y) = f(e), donc y = e, et
Ker(f)={e}.
1.6.2. Anneaux,sous­anneaux,idéaux,morphismesd’anneaux
1.6.2.1. Anneaux
Dfinition 1.22.– Un ensemble A, muni d’une loi + et d’une loi notée×, est
ditunanneausietseulementsilesaxiomessuivantssontvérifiés:
1)(A,+)estungroupecommutatif(deneutre0),
2)×estinterne,
3)×estassociative,
4)×estdistributiveparrapportàlaloi+,c’est­à­direa×(b+c) =a×b+a×c,
et(b+c)×a =b×a+c×a.
Cetanneauestnoté(A,+,×),ouAs’iln’yapasd’ambiguïtésurleslois.
Silaloi×possèdeunneutre(noté1),l’anneauestditunitaire.
Silaloi×estcommutative,l’anneauestditcommutatif.
Engénéral,onnoteabplutôtquea×b,ainsiquea−bplutôtquea+(−b).
Ilyadeuxsous­structuresimportantesquel’onexaminemaintenant.
1.6.2.2. Sous­anneaux,idéaux
Dfinition 1.23.– Unsous­anneauBdeAestsimplementunanneau(B,+,×)
dansA.
Proposition 1.10.– Pour prouver qu’une partieB est un sous­anneau(B,+,×)
deAilsuffitdevérifier :
1)(B,+)estunsous­groupede(A,+),
2)a∈B etb∈B⇒ab∈B.
Dmonstration.– Lesautresaxiomessontvérifiés.
Dfinition 1.24.– Un idéalI deA est un sous­anneau,tel que l’on ait l’impli­
cation(i∈I eta∈A)⇒ia∈I,ai∈I.