Algèbre et protection de l'information

Philippe Guillot, Alain Poli

Description

Cet ouvrage couvre l'algèbre classique et l'algèbre discrète ainsi que ses applications à la cryptographie et aux codes correcteurs d'erreurs. Partant de la théorie des ensembles, il aboutit à la diagonalisation des matrices. Les structures finies sont étudiées, ainsi que certains circuits électroniques utilisés dans la pratique pour effectuer les calculs. Des exemples de complexité d'algorithmes sont donnés. Ce livre introduit les principales techniques de protection des informations contre les attaques éventuelles. De nombreuses constructions sont proposées. Un exemple concret précède chaque preuve délicate. Plus d'une centaine d'exercices et de problèmes, avec leurs corrigés complets illustrent Algèbre et protection de l'information.

Sujets

• Sciences & Techniques
• Mathématiques
• Sciences formelles
• Algèbre
• Sciences
• Computers
• Techniques
• Informatique
• Mathematics
• Ordinateur
• Arithmétique
• Science formelle
• Intermédiaire
• Technique
• Science

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 01 septembre 2022
• Nombre de lectures: 5
• EAN13: 9782746227446
• Langue: Français
• Poids de l'ouvrage: 14 Mo

Extrait

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