Cours-lm220-Kraus

Informations

• Publié par: Pheyn
• Nombre de lectures: 99
• Langue: Français

Extrait

COURS D’ARITHMETIQUE
LM220
Alain Kraus
Universite de Paris VI
2006/07Table des matieres
Introduction 3
Chapitre I. Arithmetique sur Z 5
1. Division euclidienne 5
2. Nombres premiers 7
3. Valuation p-adique d’un entier relatif 12
4. Plus grand commun diviseur 14
5. L’algorithme d’Euclide 16
6. L’equation ax+by =c 18
7. Plus petit commun multiple 19
8. Numeration en base b 20
Chapitre II. La notion de groupe 25
1. De nition d’un groupe 25
2. Sous-groupes d’un groupe 27
3. Classes modulo un sous-groupe - Theoreme de Lagrange 29
4. Groupe quotient d’un groupe abelien 32
5. Sous-groupe engendre par un element - Ordre d’un element 33
6. Groupes cycliques - Fonction indicatrice d’Euler 37
7. Homomorphismes de groupes 42
Chapitre III. Anneaux et corps 49
1. De nition d’un anneau 49
2. Sous-anneaux - Ideaux 51
3. Anneau quotient d’un anneau commutatif 53
4. Groupe des elements inversibles - Corps - Anneaux integres 54
5. Homomorphismes d’anneaux 57
6. La formule du binomˆ e de Newton 59
Chapitre IV. Arithmetique sur Z/nZ 61

1. Le groupe multiplicatif Z/nZ 61
2. Theoreme d’Euler et petit theoreme de Fermat 62
3. Le theoreme chinois 64
4. Determination de la fonction indicatrice d’Euler 67
5. Application a la cryptographie - Algorithme RSA 69
Chapitre V. Arithmetique sur K[X] et ses quotients 73
1. Degre - Division euclidienne 73
12. Ideaux de K[X] - pgcd - ppcm 75
3. Polynˆomes irreductibles 78
4. Racines d’un polynˆome 80
5. Les algebres quotients de K[X] modulo un ideal 85
Chapitre VI. Corps nis - Construction 95
1. Caracteristique d’un anneau 95
2. Groupe multiplicatif d’un corps ni 97
3. Corps nis comme quotients de F [X] 99p
24. Construction et unicite des corps a p elements 100
5. Polynˆomes irreductibles sur un corps ni 102
6. Theoreme d’existence et denombrement 106
7. Theoreme d’unicite 111
8. Le probleme du logarithme discret - Algorithme de Silver, Pohlig et Hellman 111
9. Application a la cryptographie - Protocole de Di e-Hellman - Algorithme de 116
El Gamal
Chapitre VII. Codes correcteurs d’erreurs 119
1. Problematique des codes correcteurs 119
2. Distance de Hamming - De nition et parametres d’un code 121
3. Decodage par maximum de vraisemblance - Capacite de correction 123
4. Codes parfaits 125
5. Les entiers A (n,d) 126q
6. Codes lineaires 128
7. Encodages associes aux codes lineaires - Matrices generatrices 131
8. Codes systematiques 132
9. Codes equivalents 137
10. Matrices de contrˆole 139
11. Applications des matrices de contrˆole 142
2Introduction
L’objectif de ce cours est de presenter les concepts de base de l’arithmetique, de la
theorie des corps nis, d’en deduire quelques applications a la cryptographie, et de donner
une introduction a la theorie des codes correcteurs d’erreurs.
On ne se preoccupera pas de la construction de l’ensemble N des entiers naturels, ni
de celle de l’ensembleZ des entiers relatifs. Nous admettrons donc que ces ensembles exis-
tent, et qu’ils sont munis de la relation d’ordre et des lois de composition usuelles que le
lecteur connaˆ t depuis longtemps. Le debut du cours est consacre a l’etude de la divisibilite
dansZ, qui est le point de depart de l’arithmetique, et a une introduction a la theorie des
groupes nis. Les premiers resultats de cette theorie sont indispensables dans la plupart
des applications arithmetiques ulterieures. Un accent particulier est mis sur l’etude des
hh iigroupes abeliens, pour lesquels on de nit la notion nonevidente de groupe quotient. On
l’etend ensuite au cas des anneaux commutatifs, en vue d’etudier les quotients de Z, les
quotients des anneaux de polynˆomes, et notamment les corps nis. On aborde a la n la
notion de code correcteur, en particulier celle de code lineaire sur un corps ni.
J’ai developpe a certains endroits, en complement, quelques resultats pour les etu-
diants qui pourraient ˆetre interesses. Les parties concernees seront precisees pendant le
semestre. A titre indicatif, je signale les ouvrages suivants comme bibliographie comple-
mentaire du cours :
1) X. Bu , J. Garnier, E. Halberstadt, T. Lachand-Robert, F. Moulin, J. Sauloy, Mathe-
matiques, Tout-en-un pour la Licence, Niveau L1, Sous la direction de J.-P. Ramis et
A. Warusfel, Dunod, 2006.
2) M. Demazure, Cours d’algebre, primalite divisibilite codes, Nouvelle bibliotheque
mathematique, Cassini, 1997.
er3) J. Dixmier, Cours de mathematiques du premier cycle, 1 annee, gauthier-villars,
deuxieme edition, 1976.
4) R.Godement,Coursd’algebre,enseignementdessciences,Hermann,troisiemeedition,
1980.
34