Algèbre et protection de l'information , livre ebook

Algèbre et protection de l’information© LAVOISIER, 2005
LAVOISIER
11, rue Lavoisier
75008 Paris
Serveur web : www.hermes-science.com
ISBN 2-7462-1068-1
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 marques de leurs détenteurs respectifs.
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 sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.Algèbre
et protection
de l’information
Alain Poli
Philippe GuillotCOLLECTION DIRIGÉE PAR
JEAN-CHARLES POMEROLTabledesmatières
Introduction ..................................... 15
Chapitre1.Elémentsd’algèbre .......................... 19
1.1.Ensembles ................................. 19
1.1.1. Ensemblesfinisouinfinis . . . . . . . . . . . . . . . . . . . . . . 20
1.1.2. Partiesd’unensemble, ensembledespartiesd’unensemble . . 20
1.1.3. Construction d’ensembles à partir d’ensembles, de parties à
partirdeparties............................ 21
1.1.3.1. Constructiond’ensemblesàpartird’ensembles . . . . . . 21
1.1.3.2.tionsdepartiesàpartirdeparties . . . . . . . . 21
1.1.3.3.Recouvrementetpartition .................. 22
1.2.Ordreetéquivalence............................ 22
1.2.1.Relationd’ordre ........................... 22
1.2.2.Relationd’équivalence ....................... 23
1.3.Applications ................................ 23
1.3.1.Partiesetapplications........................ 23
1.3.2.Composéed’applications ...................... 24
1.3.3. Propriétéspossiblespouruneapplication . . . . . . . . . . . . 24
1.3.3.1.Propriétés............................ 24
1.3.3.2.Applicationsimportantes................... 24
1.4. Enrichissement desensembles:loisdecomposition. . . . . . . . . . 25
1.4.1.Lesloisdecomposition....................... 25
1.4.1.1.Loidecompositioninterne.................. 25
1.4.1.2.Loidecompositionexterne.................. 26
1.4.2. Propriétéspossiblespourlesloisinternes . . . . . . . . . . . . . 26
1.4.2.1. Loiproduit . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4.3.Tablecartésienned’uneloiinterne................. 26
1.5. Enrichissement desapplications:lesmorphismes . . . . . . . . . . . 27
1.5.1.Propriétésd’unmorphisme..................... 27
56 Algèbreetprotectiondel’information
1.6.Ensemblesstructurés ........................... 28
1.6.1. Groupes,sous-groupes,morphismesdegroupes . . . . . . . . . 28
1.6.1.1. Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6.1.2. Sous-groupes . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6.1.3.Morphismes .......................... 29
1.6.2. Anneaux,sous-anneaux,idéaux,morphismesd’anneaux . . . 29
1.6.2.1.Anneaux ............................ 29
1.6.2.2. Sous-anneaux,idéaux . . . . . . . . . . . . . . . . . . . . . 30
1.6.2.3.Morphismes .......................... 30
1.6.3. Corps,sous-corps,morphismesdecorps . . . . . . . . . . . . . 31
1.6.3.1.Corps .............................. 31
1.6.3.2. Sous-corps . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.6.3.3.Morphismes .......................... 31
1.6.4. Espacesvectoriels,sous-espacesvectoriels,applicationslinéaires 32
1.6.4.1.Espacesvectoriels ....................... 32
1.6.4.2. Sous-espacevectoriel . . . . . . . . . . . . . . . . . . . . . 32
1.6.4.3.Applicationslinéaires ..................... 33
1.6.5.Classeslatéralesd’unesous-structure............... 33
1.6.5.1. Sous-structuresetclasseslatérales . . . . . . . . . . . . . . 33
1.6.5.2. Classeslatéralesdunoyaude f etrésolutiond’équations 34
1.6.5.3. Classeslatéralesetstructuresquotients . . . . . . . . . . . 34
1.7.Anneauxetcorpsimportants ...................... 35
1.7.1. Anneauximportants:Zet K[X] ................. 35
1.7.1.1.Lesdeuxordres,PGCDetPPCM.............. 35
1.7.1.2. Nombrespremiers,polynômesirréductibles . . . . . . . . 36
1.7.1.3. L’indicateurd’Euler : ϕ(n) .................. 36
1.7.1.4. Une«bonne»application . . . . . . . . . . . . . . . . . . 37
1.7.1.5.Egalitéd’Euclide........................ 37
1.7.1.6.Anneauprincipal ....................... 37
1.7.1.7.EgalitédeBezout ....................... 37
1.7.1.8.Ladécompositionprimaire.................. 38
1.7.1.9.CalculsdePGCD ....................... 38
1.7.2.Corpsimportants .......................... 40
1.7.2.1.Racinesdepolynômes..................... 40
1.7.2.2. IrréductiblessurRousuruncorpsfini F ......... 40q
1.8.AlgèbreLinéaire.............................. 41
1.8.1.Quelquespropriétésdebase .................... 41
1.8.1.1. Indépendancelinéaireetdépendancelinéaire de r vecteurs 41
1.8.1.2.Systèmesdegénérateurs.................... 42
1.8.1.3.Systèmeminimaldegénérateurs............... 42
1.8.1.4. Basede E,dimension de E.................. 42
1.8.1.5. Compléterunebased’unsous-espacevectoriel . . . . . . 43
1.8.1.6.Sommedesous-espacesvectoriels .............. 44Table desmatières 7
1.8.1.7. Sommedirectedesous-espacesvectoriels,supplémentaire 44
1.8.2.Représentation............................ 45
1.8.2.1.Représentationd’unvecteur ................. 45
1.8.2.2. Représentationd’uneapplicationlinéaire,
etreprésentationdel’imaged’unvecteur . . . . . . . . . . . . . . . . . . 45
1.8.2.3.Représentationd’unesommededeuxapplicationslinéaires 47
1.8.2.4. Représentationd’une composée dedeux
applicationslinéaires .............................. 47
1.8.3.Changementdereprésentation................... 48
1.8.3.1. Vecteurde E .......................... 48
1.8.3.2. Applicationlinéaire f de E dans F ............. 49
1.8.4.AnneauximportantsenAlgèbreLinéaire ............ 50
1.8.4.1. End(E) ............................. 50
1.8.4.2. K[h] ............................... 50
1.8.4.3. M ................................ 50n
1.8.4.4. M [X].............................. 50n
1.8.5.Calculmatriciel ........................... 51
1.8.5.1.Manipulationsélémentaires ................. 51
1.8.5.2. Expressionsmatricielles desmanipulationsélémentaires . 51
1.8.5.3.AlgorithmedeGauss ..................... 52
1.8.5.4. Recherchedel’inversed’unematrice M carrée,d’ordre n 53
1.8.5.5.Recherchedenoyau ...................... 54
1.8.5.6.Résolutiondesystèmeslinéaires............... 55
1.9.PlusloinenAlgèbreLinéaire....................... 56
1.9.1.Déterminant ............................. 56
1.9.1.1. Autresdéveloppementsd’undéterminant . . . . . . . . . 57
1.9.1.2.Propriétésd’undéterminant ................. 58
1.9.1.3. DéterminantetalgorithmedeGauss . . . . . . . . . . . . 59
1.9.1.4.
Leproduitd’unematriceetdesonadjointe(verslethéorèmedeCayley-Hamilton) .................. 60
1.9.1.5. Ledéterminantd’unproduitdedeuxmatricescarrées . . 61
1.9.2.Vecteursetvaleurspropres ..................... 63
1.9.2.1. Recherchede λetd’unebasede F ............. 64λ
1.9.2.2. Propriétésdessous-espacespropres . . . . . . . . . . . . . 64
1.9.3. Polynômesremarquablesassociésàunendomorphisme . . . . 65
1.9.3.1.Unepropriétégénérale .................... 65
1.9.3.2.Polynômecaractéristique ................... 65
1.9.3.3. Polynômecaractéristiqued’unematricecompagne . . . . 66
1.9.3.4.Polynômeminimum ...................... 67
1.9.3.5. Polynômeminimum d’unematricecompagne . . . . . . . 67
1.9.3.6. Polynômeminimum d’unélément xde E ......... 68
1.9.3.7. Calculde PMIN (X), pmin (X)et PCAR (X) ..... 68h hx
1.9.4. Premièredécompositionde Eensommedirecte......... 688 Algèbreetprotectiondel’information
k1.9.4.1. Lecasparticulierde Ker(p (h))............... 69
1.9.4.2.Lecasgénéral ......................... 73
1.9.5. Raffinementdeladécompositionensommedirecte . . . . . . . 75
1.9.5.1. Construction de ce raffinement de la décomposition en
sommedirecte.......................... 77
1.9.6. Lefindufin:ladiagonalisationde A............... 77
Chapitre2.Structuresalgébriquesfinies ..................... 79
2.1. Groupesfinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.1.1.ThéorèmedeLagrange ....................... 79
2.1.2. Sous-grouped’ungroupecycliquefini . . . . . . . . . . . . . . 79
2.1.3. Groupedespermutations . . . . . . . . . . . . . . . . . . . . . . 80
2.1.3.1. Propriétésgénéralesdespermutations . . . . . . . . . . . 80
2.1.3.2.Lasignature .......................... 82
2.2. Corpsfinis:Z/(p)et F [X]/(p(X))................... 842
2.2.1.Lesloisdecompositioninternes.................. 84
2.2.1.1. LesloisdansZ/(p) ...................... 84
2.2.1.2. Lesloisdans F [X]/(p(X)) ................. 852
2.2.1.3. Inversesetopposés . . . . . . . . . . . . . . . . . . . . . . 86
2.2.2. Z/(p)et F [X]/(p(X))sontdescorps .............. 872
2.2.3. Ordred’unélément, primitifs,nombredeprimitifs . . . . . . . 87
2.2.3.1.Ordred’unélément ...................... 87
2.2.3.2.Primitifs,nombredeprimitifs ................ 88
2.2.3.3. Primitifsetlogarithmesdiscrets . . . . . . . . . . . . . . . 89
2.2.4. Circuitsélectroniquesetcalculspolynomiaux . . . . . . . . . . 90
2.2.4.1.Elémentsdebase........................ 90
2.2.4.2. Indexationdesbasculesetdesfils . . . . . . . . . . . . . . 90
2.2.4.3. Fonctionnement général . . . . . . . . . . . . . . . . . . . 91
2.2.4.4. Circuitmultiplicateurpar X ................. 93
2.2.4.5.Circuitdiviseur......................... 93
2.2.4.6.Circuitmultiplicateur ..................... 94
2.2.4.7.Circuitmultiplicateur-diviseur ................ 94
2.2.4.8.Codeurd’uncodecyclique .................. 95
2.2.5. Legroupedesracinesn-ièmesdel’unité . . . . . . . . . . . . . 95
2.2.6. Classescyclotomiquesdans F [X]/(p(X))............ 952
2.2.6.1.Lesclassescy