Cours d'algebre

Introduction......Page 10
I. Primalité......Page 16
Introduction à la première partie......Page 18
1.1.1 Règles de réécriture......Page 24
1.1.2 Réécriture et déterminisme......Page 26
1.1.3 Traduction dans un langage de programmation......Page 28
1.1.4 Récursion et itération......Page 30
1.2. Calcul rapide des puissances......Page 32
1.2.1 Des poids faibles vers les poids forts......Page 33
1.2.2 Des poids forts vers les poids faibles......Page 34
1.3.1 Coût des opérations arithmétiques élémentaires......Page 36
1.3.2 Congruences dans Z......Page 37
1.3.3 Le coût du calcul modulaire......Page 39
1.3.4 Le coût de l'exponentielle......Page 40
1.4.1 L'algorithme de base......Page 42
1.4.2 L'algorithme d'Euclide binaire......Page 45
1.4.3 La suite de Fibonacci......Page 46
1.4.5 L'algorithme d'Euclide étendu......Page 47
1.4.6 Le coût de l'algorithme d'Euclide étendu......Page 49
1.5.1 Polynômes en une variable......Page 50
1.5.3 Algorithmes d'Euclide......Page 51
1.6.1 Exemple : écriture décimale d'un nombre rationnel......Page 53
1.6.2 Période d'une suite récurrente......Page 54
1.6.3 Algorithme de Floyd......Page 55
1.6.4 Algorithme de Brent......Page 56
1.6.5 La méthode de factorisation p de Pollard......Page 57
2.1.1 L'énoncé : forme classique......Page 60
2.1.3 Les démonstrations du théorème chinois......Page 61
2.1.4 Un algorithme......Page 62
2.2.1 Le groupe (Z/nZ)*......Page 63
2.2.2 L'indicateur d'Euler......Page 64
2.3.1 Ordre d'un élément d'un groupe......Page 67
2.3.2 Le petit théorème de Fermat......Page 68
2.3.3 Une application du théorème de Fermat à la factorisation......Page 70
2.3.4 Le théorème d'Euler......Page 71
2.3.5 Cryptographie à clés publiques et nombres premiers : la méthode rsa......Page 72
2.3.6 Critères de non-primalité tirés du petit théorème de Fermat......Page 75
2.3.7 Le critère de Miller-Rabin......Page 77
3.1.2 Exposant d'un groupe commutatif fini......Page 80
3.1.3 Racines primitives de l'unité......Page 82
3.1.4 Racines primitives modulo p......Page 83
3.1.5 Recherche des racines primitives......Page 84
3.2.1 Critères de primalité « à la Lehmer »......Page 85
3.2.2 Certificats de primalité......Page 87
3.2.3 Les nombres de Fermat......Page 88
3.2.4 Nombres de Mersenne......Page 90
3.2.5 Suites de Lucas......Page 91
3.2.6 Construction d'anneaux par adjonction......Page 93
3.2.7 Le critère de primalité de Lucas-Lehmer......Page 94
3.2.8 Critère de primalité des nombres de Mersenne......Page 96
3.3.1 Nombres de Carmichael......Page 98
3.3.2 L'indicateur de Carmichael......Page 99
3.3.3 Structure du groupe (Z/p^nZ)*, p premier impair......Page 100
3.3.4 Structure du groupe (Z/2^nZ)*......Page 101
3.3.5 Calcul de l'indicateur de Carmichael......Page 102
3.3.6 Preuve du théorème de Rabin......Page 103
4.1.1 Racines principales de l'unité......Page 108
4.1.2 L'anneau A[X]/(X^n-1)......Page 109
4.1.3 Définition de la transformation de Fourier......Page 110
4.2.1 Le principe......Page 111
4.2.2 L'algorithme......Page 113
4.3.1 Transformation de Fourier rapide modulo N......Page 114
4.3.2 Applications arithmétiques......Page 115
4.3.3 Multiplication des grands entiers......Page 116
4.3.4 La méthode de Pollard......Page 117
4.3.5 La méthode de Schônhage-Strassen......Page 118
5.1.1 Carrés dans un corps fini......Page 120
5.1.2 Le symbole de Legendre......Page 121
5.1.3 Calcul d'une racine carrée dans Z/pZ......Page 124
5.1.4 Carrés dans Z/p^nZ......Page 125
5.1.5 Les signes epsilon(n), omega(n) et theta(a,b)......Page 126
5.2.1 Deux exemples......Page 127
5.2.2 Sommes de Gauss......Page 129
5.2.3 La loi de réciprocité quadratique......Page 130
5.3.1 Définition et réciprocité......Page 131
5.3.2 Algorithmes de calcul du symbole de Jacobi......Page 133
5.3.3 Le critère de Solovay et Strassen......Page 135
5.3.4 Tests probabilistes de primalité......Page 136
5.3.5 Comparaison des algorithmes de Miller-Rabin et de Solovay-Strassen......Page 138
5.4.1 Parties de type P......Page 139
5.4.2 Parties de type NP......Page 140
5.4.3 Parties de type RP......Page 142
5.4.4 Le cas des nombres premiers......Page 143
Pour aller plus loin sur la primalité......Page 146
II. Codes correcteurs......Page 148
Introduction à la deuxième partie......Page 150
6.1.2 Le modèle......Page 156
6.1.4 Le décodage......Page 158
6.2.1 Les codes triviaux : les cas k = 0,1 ,n-1,n......Page 160
6.2.2 Codes t-correcteurs, capacité de correction, codes parfaits......Page 161
6.2.3 Le code de Hamming H3 de longueur 7......Page 163
6.3.1 Constructions élémentaires......Page 164
6.3.2 Extension paire......Page 165
6.3.3 Orthogonal d'un code......Page 166
6.4. Matrices génératrices et vérificatrices d'un code linéaire......Page 167
6.4.2 Changements de base......Page 168
6.4.3 Conditions de parité généralisées......Page 169
6.4.5 Matrice vérificatrice et syndrome......Page 170
6.5.1 Construction......Page 171
6.5.2 Les codes de Hamming étendus......Page 173
7.1.1 Traductions......Page 176
7.1.2 Un exemple......Page 177
7.2. Codes d'hyperplans affines......Page 179
7.2.2 L'orthogonal du code de Hamming : le code simplexe......Page 180
7.2.3 L'orthogonal du code de Hamming étendu : le code R(1,m)......Page 181
7.3.1 Fonctions booléennes et polynômes......Page 182
7.3.2 Définition des codes de Reed-Muller......Page 183
7.3.3 Description itérative des codes de Reed-Muller......Page 184
7.3.4 Mots de poids minimal du code R(r,m)......Page 185
7.4.2 Espaces affines ou projectifs finis......Page 187
7.4.3 Plans projectifs « abstraits »......Page 189
7.5.2 Exemples......Page 190
7.5.3 Codes et systèmes de Steiner......Page 191
7.6. Automorphismes......Page 193
7.6.1 Exemple : les codes cycliques......Page 194
7.6.2 Exemple : les transformations affines......Page 195
7.6.3 Codes et géométries finies......Page 196
8.1.1 Majorations, codes optimaux......Page 198
8.1.2 Projections et raccourcissements d'un code......Page 199
8.1.3 Majoration de Griesmer......Page 200
8.1.5 Majoration de Hamming......Page 201
8.2. Conditions de Gilbert-Varshamov......Page 202
8.3.1 Le diagramme (d/n,k/n)......Page 203
8.3.2 Le domaine des codes......Page 204
8.3.3 Préliminaires......Page 205
8.3.4 Existence de bons codes......Page 207
8.3.5 Bonnes familles de codes......Page 209
8.4.1 L'approche probabiliste......Page 210
8.4.2 Le décodage total......Page 211
8.4.3 Le théorème de Shannon et sa réciproque......Page 212
8.4.5 Une idée de la démonstration......Page 213
8.4.6 Moralité......Page 215
9.1.1 Éléments algébriques, polynômes minimaux......Page 216
9.1.2 Construction de corps par adjonction......Page 217
9.1.3 Corps premiers......Page 218
9.1.4 Structure des corps finis......Page 219
9.1.5 Polynômes minimaux sur Fp......Page 220
9.2. Polynômes cyclotomiques......Page 221
9.2.1 Le polynôme Phi(n)......Page 222
9.2.2 Racines des polynômes cyclotomiques......Page 223
9.2.3 Irréductibilité sur Q des polynômes cyclotomiques......Page 224
9.2.4 Corps cyclotomiques......Page 225
9.2.5 Décomposition des polynômes cyclotomiques dans un corps fini......Page 226
9.3.1 Polynômes irréductibles sur Fp......Page 228
9.3.2 Relation entre ordre et degré......Page 230
9.3.3 « Le » corps à q éléments......Page 231
9.3.4 Racines de l'unité dans un corps fini......Page 233
9.4.2 Exemple : le corps F16......Page 234
9.4.3 Le logarithme de Zech......Page 236
9.5. Démonstration du théorème AKS......Page 237
9.6.1 Polynômes sans facteur multiple......Page 240
9.6.2 L'algorithme de Berlekamp......Page 241
9.6.3 Une variante probabiliste......Page 242
9.6.4 L'algorithme de Cantor-Zassenhaus......Page 243
9.6.5 Décomposition des polynômes dans Q[X]......Page 244
10.1.1 Paramètres d'un code linéaire......Page 246
10.1.3 Codes parfaits......Page 247
10.1.4 Codes sur Fq et codes sur Fp......Page 248
10.1.5 Un exemple......Page 249
10.2.1 La majoration de Singleton......Page 250
10.2.3 Raccourcissement......Page 251
10.2.4 Première construction des codes de Reed-Solomon......Page 253
10.3.1 Définitions......Page 254
10.3.2 Représentation des mots par des polynômes......Page 255
10.3.3 Générateurs minimaux des codes cycliques......Page 256
10.3.5 Constructions élémentaires......Page 258
10.4. Classes cyclotomiques (n premier à q)......Page 259
10.4.2 Classes cyclotomiques......Page 260
10.4.3 Exemples......Page 261
10.4.4 Distance minimale des codes cycliques......Page 262
10.4.5 Idempotents des codes cycliques......Page 263
11.1.1 Codes de Hamming binaires......Page 266
11.1.2 Les codes de Reed-Solomon comme codes cycliques......Page 267
11.1.3 L'autre description des codes de Reed-Solomon......Page 268
11.1.5 Codes BCH......Page 269
11.2.1 Construction des codes BCH binaires stricts......Page 271
11.2.2 Exemple : les codes BCH binaires de longueur 15......Page 272
11.2.3 Une autre définition des codes BCH binaires stricts......Page 273
11.3. L'algorithme de décodage des codes BCH binaires......Page 274
11.3.2 Syndrome......Page 275
11.3.4 Résolution de l'équation-clé......Page 276
11.4. L'algorithme de décodage des codes BCH généraux......Page 277
11.4.2 Correction de f effacements, f12.1.1 La chaîne de codage......Page 280
12.2.1 Entrelacement......Page 282
12.2.2 Le codage......Page 283
12.2.3 Le décodage......Page 284
12.2.4 Les détails du codage et du décodage......Page 285
12.3. Au delà du code CIRC......Page 287
13.1.1 Définition générale......Page 288
13.1.2 Idempotents des codes QR binaires......Page 290
13.1.4 Automorphismes d'un code QR binaire étendu......Page 291
13.1.5 Distance minimale d'un code QR binaire......Page 294
13.2. Les codes binaires de Golay G23 et G24......Page 295
13.2.1 Détermination des codes parfaits......Page 297
13.2.2 Automorphismes du code de Golay : le groupe M24......Page 299
13.2.3 Les groupes de Mathieu......Page 300
13.3.1 Réseaux......Page 301
13.3.2 Réseau déduit d'un code binaire......Page 302
13.3.3 Exemple : le réseau E8......Page 303
13.3.4 Vecteurs de carré scalaire 2......Page 304
13.3.5 Réseaux et matrices symétriques entières......Page 305
13.3.6 Ceci n'est pas une conclusion......Page 306
Pour aller plus loin sur les codes......Page 308
Glossaire d'algèbre......Page 310
Solutions des exercices......Page 314
Table des matières......Page 330
Bibliographie......Page 338
Index des notations......Page 340