Disciplines plus que bimillénaires, l'algèbre et l'arithmétique ont connu récemment des applications aussi spectaculaires qu'inattendues. Comment décomposer un nombre en facteurs premiers, comment reconnaître si un nombre est premier : ces questions, revivifiées par l'existence des moyens modernes de calcul, se retrouvent aujourd'hui au coeur des procédés de cryptographie les plus [...] [lire le résumé du livre]
Disciplines plus que bimillénaires, l'algèbre et l'arithmétique ont connu récemment des applications aussi spectaculaires qu'inattendues. Comment décomposer un nombre en facteurs premiers, comment reconnaître si un nombre est premier : ces questions, revivifiées par l'existence des moyens modernes de calcul, se retrouvent aujourd'hui au coeur des procédés de cryptographie les plus récents. La numérisation du stockage et de la transmission de l'information utilise les codes correcteurs, application surprenante des corps finis inventés par Galois. À côté de cette application moderne d'une théorie classique les ordinateurs, dans d'autres domaines, sont en train de modifier la conception que l'on a de l'algèbre. Le livre de Michel Demazure s'inscrit dans ce mouvement, et depuis la première édition de ce livre, l'enseignement de l'algèbre a évolué pour une part dans la direction qu'il indiquait.Issu d'un enseignement à l'École polytechnique, ce Cours d'algèbre est accessible à des étudiants de licence ou à de bons élèves de classes préparatoires. Il rendra de grands services aux agrégatifs.La première partie traite d'abord de l'analyse des algorithmes, puis de l'arithmétique classique et de la transformation de Fourier rapide, avec comme objectif la construction de tests performants de reconnaissance des nombres premiers. La deuxième partie, après une introduction aux corps finis et à la théorie cyclotomique, présente un exposé détaillé de leurs applications aux codes correcteurs. Cette deuxième édition est très profondément modifiée, notamment dans la deuxième partie, considérablement augmentée.Ce livre contient 270 exercices avec solutions, dont un grand nombre comporte des calculs sur ordinateur.
Auteurs :
Miche Demazure a été professeur à l'université et à l'Ecole polytechnique a aussi exercé a direction de grands établissements (Palais de la découverte et Cité des sciences et de l'industrie). préside le comité consultatif de la recherche de la région Languedoc-Roussillon.
Table des matières
Introduction 1
1. Primalité
Introduction à la première partie 9
Chapitre 1. Trois algorithmes fondamentaux 15
1..1 R"" . 15
eecniture
1.1.1. Règles de réécriture . 15
1.1.2. Réécriture et déterminisme .. 17
1.1.3. Traduction dans un langage de programmation 19
1.1.4. Récursion et itération . 21
1.2. Calcul rapide des puissances . . . . . . . . . 23
1.2.1. Des poids faibles vers les poids forts 24
1.2.2. Des poids forts vers les poids faibles 25
1.3. Complexité des algorithmes arithmétiques . 27
1.3.1. Coût des opérations arithmétiques élémentaires 27
1.3.2. Congruences dans Z .... 28
1.3.3. Le coût du calcul modulaire
3°
1.3.4. Le coût de l'exponentielle 31
1.4. Algorithmes d'Euclide . 33
104.1. L'algorithme de base . 33
1.4.2. L'algorithme d'Euclide binaire. 36
1.4.3. La suite de Fibonacci . . . . . .
37
1.4.4. Le coût de l'algorithme d'Euclide 38
104.5. L'algorithme d'Euclide étendu .. 38
1.4.6. Le coût de l'algorithme d'Euclide étendu
4°
1.5. Algorithmes d'Euclide pour les polynômes . 41
1.5.1. Polynômes en une variable ..... 41
1.5.2. Division euclidienne des polynômes 42
1.5.3. Algorithmes d'Euclide . . . . . . . 42
1.6. Algorithmes de recherche d'une période .. 44
1.6.1. Exemple: écriture décimale d'un nombre rationnel . 44
1.6.2. Période d'une suite récurrente
45
1.6.3. Algorithme de Floyd 46
32 1
1.6.4. Algorithme de Brent . . . . . . . . . . .
1.6.5. La méthode de factorisation p de Pollard
Chapitre 2. Théorème de Fermat et primalité
2.1. Théorème chinois . . . . . . . . . 51
2.1.1. L'énoncé: forme classique . . . 51
2.1.2. L'énoncé: forme abstraite . . . 52
2.1.3. Les démonstrations du théorème chinois 52
2.1.4. Un algorithme ... 53
2.2. L'indicateur d'Euler . . . . . 54
2.2.1. Le groupe (Z/nZ)* . 54
2.2.2. L'indicateur d'Euler 55
2.3. Le petit théorème de Fermat 58
2.3.1. Ordre d'un élément d'un groupe. 58
2.3.2. Le petit théorème de Fermat . . . 59
2.3.3. Une application du théorème de Fermat à la factorisation 61
2.3-4. Le théorème d'Euler . . . . . . . . . . . . . . . . . . 62
2.3.5. Cryptographie à clés publiques et nombres premiers: la
méthode R5A . . . . . . . . . . . . . . . . . . . . . 63
2.3.6. Critères de non-primalité tirés du petit théorème de Fer
mat. . . . . . . . . . . 66
2.3.7. Le critère de Miller-Rabin 68
Chapitre 3. Racines primitives
3.1. Structure du groupe K* .
3.1.1. Groupes cycliques .
3.1.2. Exposant d'un groupe commutatif fini .
3.1 .3. Racines primitives de l'unité .
3.1.4. Racines primitives modulo p .
3.1.5. Recherche des racines primitives.
3.2. Critères de primalité . . . . . . . . . . . .
3.2.1. Critères de primalité « à la Lehmer »
3.2.2. Certificats de primalité .
3.2.3. Les nombres de Fermat
3.2-4-Nombres de Mersenne .
3.2.5. Suites de Lucas .... .
3.2.6. Construction d'anneaux par adjonction
3.2.7. Le critère de primalité de Lucas-Lehmer
3.2.8. Critère de primalité des nombres de Mersenne
3.3. Indicateur et nombres de Carmichael
3.3.1. Nombres de Carmichael ..
3.3.2. L'indicateur de Carmichael .
TABLE DES MATIÈRES
3.3.3. Structure du groupe (Z/pnZ)*, p premier impair. 91 3.3-4. Structure du groupe (Z/2nZ)* .... 92
3.3.5. Calcul de l'indicateur de Carmichael . 93
3.3.6. Preuve du théorème de Rabin . . 94
Chapitre 4. Transformation de Fourier rapide 99
4.1. Transformation de Fourier discrète . .
99
4.1.1. Racines principales de l'unité . . 99
4.1.2. L'anneau A[X]/(Xn -1) ..... 100
4.1.3. Définition de la transformation de Fourier 101
4.2. Transformation de Fourier rapide 102
4.2.1. Le principe . 102
4.2.2. L'algorithme . 1°4
4.3.Applications ........... 1°5
4.3.1. Transformation de Fourier rapide modulo N 1°5
4.3.2. Applications arithmétiques .... 106
4.3.3. Multiplication des grands entiers .. 1°7
4.3.4. La méthode de Pollard . 108
4.3.5. La méthode de Schônhage-Strassen 1°9
Chapitre 5. Résidus quadratiques et applications III
5.1. Résidus quadratiques .. . . . . 1II
5.1.1. Carrés dans un corps fini 111
5.1.2. Le symbole de Legendre Il2
5.1.3. Calcul d'une racine carrée dans Z/pZ . 115
5.1.4. Carrés dans Z/ pnZ ....... Il6
5.1.5. Les signes 8(n), w(n) et 8(a, b) . 117
5.2. Réciprocité quadratique . . Il8
5.2.1. Deuxexemples . . . . . . . . . Il8
5.2.2. Sommes de Gauss 120
5.2.3. La loi de réciprocité quadratique 121
5.3.SymboledeJacobi ............. 122
5.3.1. Définition et réciprocité . . . . . 122
5.3.2. Algorithmes de calcul du symbole de Jacobi. 124
5.3.3. Le critère de Solovay et Strassen. . . . . . . 126
5.3.4. Tests probabilistes de primalité 127
5.3.5. Comparaison des algorithmes de Miller-Rabin et de Solovay-Strassen . . . 129 5-4. Algorithmes probabilistes . 130
5.4.1. Parties de type:P . 130 5-4.2. Parties de type JI:P 131 5-4.3. Parties de type :R:P 133
5.4.4. Le cas des nombres premiers .
Pour aller plus loin sur la primalité I37
II. Codes correcteurs
Introduction à la deuxième partie
Chapitre 6. Codes binaires I47
6.1. Définitions générales. 147
6.1.1. Le corps F2 • 147
6.1.2. Le modèle. . 147
6.1.3. Le modèle d'erreur: le canal binaire symétrique 149
6.1.4. Le décodage 149
6.I.5. Codeslinéaires ............... 151
6.2.Exemples. ...................... 151
6.2.1. Les codes triviaux: les cas k = 0, 1,n -l, n 151
6.2.2. Codes t -correcteurs, capacité de correction, codes parfaits 152
6.2.3. Le code de Hamming H3 de longueur 7 154
6.3. Outils de construction de codes . . . 155
6.3. I. Constructions élémentaires 155
6.3.2. Extension paire . . . . . . . 156
6.3.3. Orthogonal d'un code ... 157
6.4. Matrices génératrices et vérificatrices d'un code linéaire 158
6.4.1. Matrices génératrices et vérificatrices 159 6-4.2. Changements de base. . . . . . . 159
6.4.3. Conditions de parité généralisées 160 6-4-4. Extensionpaire . . . . . . . . . . 161
6.4.5. Matrice vérificatrice et syndrome 161
6.5. Les codes binaires de Hamming . . . . . 162
6.5.1.Construction .......... 162
6.5.2. Les codes de Hamming étendus 164
Chapitre 7. Codes, combinatoire, géométrie I67
7.1. Les codes binaires comme codes de parties 167
7.1.1. Traductions . . . . 167
7.1.2. Un exemple. . . . 168
7.2. Codes d'hyperplans affines 170
7.2 .1. Hyperplans . . . . I71
7.2.2. L'orthogonal du code de Hamming : le code simplexe 171
7.2.3. L'orthogonal du codede Hamming étendu: le code R1 ,m 172
TABLE DES MATIÈRES
7.3.CodesdeReed-Muller ............. 173
7.3.1. Fonctions booléennes et polynômes . 173
7.3.2. Définition des codes de Reed-Muller 174
7.3.3. Description itérative des codes de Reed-Muller . 175
7.3.4. Mots de poids minimal du code Rr,m . 176
7.4. Géométries finies 178 7·4·I. Corpsfinis. ............ 178
7.4.2. Espaces affines ou projectifs finis 178
7.4.3. Plans projectifs « abstraits» . . . 180
7.5.SystèmesdeSteiner ............ 181
7.5.I. Définition des systèmes de Steiner. 181
7.5.2.Exemples ........... 181
7.5.3. Codes et systèmes de Steiner. 182
7.6.Automorphismes............ 184
7.6.I. Exemple: les codes cycliques 185
7.6.2. Exemple: les transformations affines 186
7.6.3. Codes et géométries finies . . . 187
Chapitre 8. Majorations de la taille des codes I89
8.I.Conditionsnécessaires ................ 189
8.1.1. Majorations, codes optimaux . . . . . . . . 189
8.1.2. Projections et raccourcissements d'un code 19°
8.r.3. Majoration de Griesmer 191
8.l -4. Majorations de Plotkin . . 192
8.1.5. Majoration de Hamming . 192
8.2. Conditions de Gilbert-Varshamov . 193
8.3. Formes asymptotiques . 194
8.3.I. Le diagramme idfn,k/n) 194
8.3.2. Le domaine des codes . 195
8.3.3. Préliminaires . . . . . .. 196 8.3-4. Existence de bons codes . 198
8.3.5. Bonnes familles de codes . 200
8.4. Et Shannon dans tout cela? . . . 201
8.4.1. L'approche probabiliste . 201
8.4.2. Le décodage total . . . . . 202 8-4.3. Le théorème de Shannon et sa réciproque. 2°3 8.4-4. Quel rapport avec ce qui précède? 2°4
8.4.5. Une idée de la démonstration 2°4
8.4.6.Moralité............... 206
Chapitre 9. Les corps finis 207
9.1.Structuredescorpsfinis ................ 207
9.1.1. Éléments algébriques, polynômes minimaux 207
9.1 .2. Construction de corps par adjonction 208
9.1.3. Corps premiers . . . . . . . 209
9.1.4. Structure des corps finis .... 210
9.1.5. Polynômes minimaux sur Fp • . 211
9.1.6. Automorphismes d'un corps fini 212
9.2. Polynômes cyclotomiques . . . . . . . . 212
9.2.1. Le polynôme n 213
9.2.2. Racines des polynômes cyclotomiques . 214
9.2.3. Irréductibilité sur Q des polynômes cyclotomiques 215
9.2.4.Corpscyclotomiques ................ 216
9.2.5. Décomposition des polynômes cyclotomiques dans un corpsfini .......... 217
9.3. Construction des corps finis . . . . . . 219
9.3.1. Polynômes irréductibles sur Fp 219
9.3.2. Relation entre ordre et degré 221
9.3.3. « Le» corps à q éléments . . . 222
9.3.4. Racines de l'unité dans un corps fini 224 9-4. Calculs explicites dans un corps fini 225 9-4.1. Les corps à 2m éléments 225 9+2. Exemple: le corps FI6 .. 225 9-4.3. Le logarithme de Zech . . 227
9.5. Démonstration du théorème AKS 228
9.6. Décomposition des polynômes dans Fp[X] 231
9.6.1. Polynômes sans facteur multiple 231
9.6.2. L'algorithme de Berlekamp 232
9.6.3. Une variante probabiliste 233 9.6-4. L'algorithme de Cantor-Zassenhaus 234
9.6.s. Décomposition des polynômes dans Q[X] 235
Chapitre IO. Codes linéaires cycliques 237
10.1. Codes linéaires sur Fq ....... 237
10.1.1. Paramètres d'un code linéaire 237
10.1.2.Décodage ......... 238
10.1.3. Codes parfaits . 238
10.1.4. Codes sur Fet codes sur F
qp 239
10.1.5. Un exemple . . 240
10.1.6. Extension paire 241
10.1.7. Orthogonal .. 241
TABLE DES MATIÈRES
10.2. Codes de type MDS . 241
10.2.1. La majoration de Singleton 241
10.2.2. Codes triviaux . .. 242
10.2.3. Raccourcissement .. 242
10.2.4. Première construction des codes de Reed-Solomon 244 Codes cycliques . . . 245
10.3.1. Définitions . . 245
10.3.2. Représentation des mots par des polynômes 246
10.3.3. Générateurs minimaux des codes cycliques 247
10.3.4. Codages pour un code cyclique 249
10.3.5. Constructions élémentaires 249 10·4· Classes cyclotomiques (n premier à q) 25°
10.4.1. Diviseurs de X" -1 251
10.4.2. Classes cyclotomiques ... 251 10-4.3. Exemples ... 252
10.4.4. Distance minimale des codes cycliques 253
10.4.5. Idempotents des codes cycliques 254
Chapitre II. Codes BCH 257
ILL Codes cycliques usuels .. . 257
II.1.1. Codes de Hamming binaires . 257
II.1.2. Les codes de Reed-Solomon comme codes cycliques 258
11.1.3. L'autre description des codes de Reed-Solomon 259
11.1.4. Codes de Reed-Solomon raccourcis 260
11.1.5. Codes BCR . 260
II.2. Codes BCR binaires stricts. .. . 262
II.2.1. Construction des codes BCR binaires stricts . 262
11.2.2. Exemple: les codes BCR binaires de longueur 15 263
11.2.3. Une autre définition des codes BCH binaires stricts 264
11.2.4. Automorphismes d'un code BCH binaire strict étendu 265
11.3. L'algorithme de décodage des codes BCR binaires 265
11.3.1. Position du problème 266
11.3.2. Syndrome . 266
11.3.3. L'équation-clé . 267 11.3-4. Résolution de l'équation-clé 267
II.4. L'algorithme de décodage des codes BCH généraux 268
11.4.1. Correction de terreurs, t < 8/2 269
II.4.2. Correction de f effacements, f < 8 269
Chapitre n. Le codage des disques compacts 271
12.1. Position du problème . 271
12.1.1. La chaîne de codage . 271
12.1.2. Les contraintes du codage correcteur . 273
12.2. Le code CIRC ..... . • 273
12.2.1. Entrelacement. 273
12.2.2. Le codage . . . 274
12.2.3. Le décodage . . 275
12.2.4. Les détails du codage et du décodage . 276
12.3. Au delà du code CIRC . 278
Chapitre IJ. Codes de résidus quadratiques 279
13.1. Codes de résidus quadratiques . . . . . 279
13.1.1. Définition générale . . . . . . 279
13.1.2. Idempotents des codes QR binaires 281
13.1.3. Codes QR binaires étendus . . . . 282
13.1.4. Automorphismes d'un code QR binaire étendu 282
13.1.5. Distance minimale d'un code QR binaire 285
13.2. Les codes binaires de Golay G23 et G24 ••.. •••. 286
13.2.1. Détermination des codes parfaits. . . . . . . 288
13.2.2. Automorphismes du code de Golay : le groupe M24 290
13.2.3. Les groupes de Mathieu. 291
13.3.Codesetréseaux ............. 292
13.3.1.Réseaux ............. 292
13.3.2. Réseau déduit d'un code binaire 293
13.3.3. Exemple : le réseau Es . . ... 294
13.3.4. Vecteurs de carré scalaire 2... 295 13.3-5-Réseaux et matrices symétriques entières 296
13.3.6. Ceci n'est pas une conclusion . . . . . . . 297
Pour aller plus loin sur les codes 299
Glossaire d'algèbre 301
Solutions des exercices 305
Bibliographie 329
Index des notations 331
SOMMAI R E
1NTROOUCTION
LES ESP{CES
Scyl'OI'"h''''dEoS 1& Triakideo;._ .._ 18
Squahdn '9
Sq~hllld"' __ 20
0"
lorpHIlfodes .._u 21
Ra~dé-s .._. n Dasyal des 15
ACI~nWrtdM 26
Angull.bdfl. ..._ .._. n
COfl}n~ 30 Muretlidês .. 31 [ngra.ulK1n 33 Clupe.db .3' Salmonldn .._.......... ]7
G~ldes 38
MU9,hdes .. u. Al~forin ld.s '7
Béolllmdés 48 Zéldés ,.. 48
8ah!ohdt's 49 G,wt'rosletd"s 50
S)'f19flollhides 5t
Avis clients
Avis clients sur Cours d'algèbre - cassini - Nouvelle bibliothèque mathématique
(Ils sont modérés par nos soins et rédigés par des clients ayant acheté l'ouvrage)
Nous utilisons des cookies pour assurer le bon fonctionnement du site et améliorer votre expérience-utilisateur.
Ce site respecte la loi RGPD du 25 mai 2018.
Vous pouvez modifier vos préférences à tout moment.
Consulter notre politique de confidentialité
Nécessaires
Les cookies nécessaires contribuent à rendre un site web utilisable en activant des fonctions de base comme la navigation de page et l'accès aux zones sécurisées du site web. Le site web ne peut pas fonctionner correctement sans ces cookies.
Statistiques
Les cookies statistiques aident les propriétaires du site web, par la collecte et la communication d'informations de manière anonyme, à comprendre comment les visiteurs interagissent avec les sites web.
Marketing
Les cookies marketing sont utilisés pour effectuer le suivi des visiteurs au travers des sites web. Le but est d'afficher des publicités qui sont pertinentes et intéressantes pour l'utilisateur individuel et donc plus précieuses pour les éditeurs et annonceurs tiers.