2M120 - Éléments d'arithmétique - UPMC 2018-2019
Laurent KOELBLEN
Polycopié
Exercices
- Chapitre 1, Codes correcteurs d'erreurs (màj 11 septembre 2016)
- Chapitre 2, Corps finis (màj 26 octobre 2015)
- Chapitre 3, Cryptographie (màj 26 octobre 2015)
- Chapitre 4, Codes cycliques (màj 13 novembre 2016)
Bibliographie
- Arithmétique : application aux codes correcteurs et à la cryptographie (cours et exercices corrigés), Pierre Wassef (Paris, Vuibert, 2008)
20 exemplaires disponibles en Bibliothèque L1-L2 scientifique et en Bibliothèque Maths-Informatique Enseignement, cote 513 WAS
Annales
Avertissement : les notations utilisées en 2014-2015, pour les matrices génératrices, ne sont pas les mêmes que celles choisies pour les années suivantes.
Les vecteurs sont notés en ligne, et les matrices génératrices sont donc à k lignes et n colonnes au lieu de l'inverse, n étant la longueur
du code et k sa dimension.
Horaire des cours et des TD
Progression du cours en 2018-2019
Chapitre 1 : Codes correcteurs d'erreurs
- Mercredi 12 septembre 2018 : généralités sur les codes correcteurs d'erreurs et sur les codes linéaires binaires (extraits des § 1.1 et § 1.2)
- Définition 1.1.1 : code correcteurs d'erreur
- Exemple 1.1.2
- Proposition 1.1.3 : distance de Hamming
- Exemple 1.1.6
- Proposition 1.2.1 : le corps à 2 éléments F2
- Remarque 1.2.3 : (Fq)n est un Fq-espace vectoriel
- Définition 1.2.4 : codes linéaires sur un corps fini Fq
- Mercredi 26 septembre 2018 :
- Définition 1.2.5 : matrice génératrice d'un code linéaire, encodage associé, matrice génératrice standard, codes systématiques
- Exemple 1.2.7
- remarque 1.2.6 : code équivalents
- proposition 1.2.9 et définition 1.2.10 : matrices de contrôle, syndrôme
- distance minimum des codes linéaires : définition 1.2.13 à proposition 1.2.17
- exercice 1.2.19
- Mercredi 3 octobre 2018 :
- décodage (§ 1.2.4 en supposant connue la distance minimum)
- exemples
- codes de Hamming (§ 1.2.5)
Chapitre 2 : Corps finis
- Mercredi 3 octobre 2018 :
- division euclidienne
- divisibilité
- nombres premiers
- nombres premiers entre eux
- théorème de Bezout (non démontré)
- Définition de Z/nZ={0,1,...,n-1} et de l'addition et de la multiplicatin sur Z/nZ
- (Z/nZ,+,×) est un anneau commutatif
- (Z/nZ,+,×) est un corps si et seulement si n est premier (non démontré)
- Si p est premier, on note Fp = Z/pZ le corps à p éléments
- mercredi 10 octobre 2018 :
- Démontration du théorème de Bezout
- Lemme de Gauss
- Démontration de l'existence d'un inverse pour tout élément non nul de Z/pZ si p est premier
- Éléments inversibles de Z/nZ pour n quelconque et diviseurs de zéro dans Z/nZ
- Polynômes à coefficients dans un corps K ; degré, addition, multiplication ; (K[X],+,×) est un anneau commutatif
Progression du cours en 2017-2018
Chapitre 1 : Codes correcteurs d'erreurs
- Mercredi 13 septembre 2017 : généralités sur les codes correcteurs d'erreurs et sur les codes linéaires binaires (extraits des § 1.1 et § 1.2)
- Définition 1.1.1 : code correcteurs d'erreur
- Exemple 1.1.2
- Proposition 1.1.3 : distance de Hamming
- Exemple 1.1.6
- Proposition 1.2.1 : le corps à 2 éléments F2
- Remarque 1.2.3 : (Fq)n est un Fq-espace vectoriel
- Définition 1.2.4 : codes linéaires sur un corps fini Fq
- Définition 1.2.5 (points (1) et (2)) : matrice génératrice d'un code linéaire
- Exemple 1.2.7
- Mercredi 20 septembre 2017 :
- Définition 1.2.5 (points (3) et (4)) : matrice génératrice standard, codes systématiques
- remarque 1.2.6 : code équivalents
- proposition 1.2.8
- proposition 1.2.9 et définition 1.2.10 : matrices de contrôle, syndrôme
- décodage (§ 1.2.4 en supposant connue la distance minimum)
- Mercredi 27 septembre 2017 : pas de cours
- mercredi 4 octobre 2017 :
- distance minimum des codes linéaires (§ 1.2.3)
- codes de Hamming
Chapitre 2, Corps finis
-
- division euclidienne
- divisibilité
- nombres premiers
- nombres premiers entre eux
- théorème de Bezout (démontré)
- Lemme de Gauss (démontré)
- factorisation des entiers (admis)
- mercredi 11 octobre 2017 :
- Construction de Z/nZ
- (Z/nZ,+,×) est un anneau commutatif
- (Z/nZ,+,×) est un corps si et seulement si n est premier
- Si p est premier, on note Fp = Z/pZ le corps à p éléments
- Éléments inversibles de Z/nZ pour n quelconque
- Polynômes à coefficients dans un corps K ; degré, addition, mulitplication ; (K[X],+,×) est un anneau commutatif
- Division euclidienne des polynômes, exemple
- Diviseurs, polynômes irréductibles, polynômes premiers entre eux, théorème de Bezout, lemme de Gauss, factorisation des polynômes
- mercredi 15 novembre 2017 :
- Construction de K[X]/P.K[X]
- (K[X]/P.K[X],+,×) est un anneau commutatif
- (K[X]/P.K[X],+,×) est un corps si et seulement si P est irréductible
- Représentation par un nombre d'un élément de F2[X]/P.F2[X] :
bn-1Xn-1 + bn-2Xn-2 + ... + b1X + b0 (où bi = 0 ou 1)
est repésenté par le nombre binaire bn-1bn-2...b1b0 ; un tel nombre peut aussi être
donné en écriture décimale ou hexadécimale (0=0 ; 1=1 ; 10=2 ; 11=3 ; 100=4 ; 101=5 ; 110=6 ; 111=7 ; etc.)
- exemples : tables d"addition et de multiplication en notation binaire et décimale des corps F2[X]/P.F2[X]
pour P=X2+X+1 ; P=X3+X+1 ; P=X3+X2+1
- mercredi 22 novembre 2017
- Caractéristique d'un corps fini
- ordre multiplicatif d'un élément d'un corps fini
- Élément primitif d'un corps fini
- Tout corps fini est isomorphe à un corps Fp[X]/P.Fp[X]
- Exponentielle et logarithme discrets
Chapitre 3, Cryptographie
- Mercredi 29 novembre 2017
- Algorithme RSA
- Protocole d'échange de clefs de Diffie-Helman
Chapitre 4, Codes cycliques
- Polynôme générateur - Matrice génératrice - Encodage
- Mercredi 13 décembre 2017
- Polynôme de contrôle - Matrice de contrôle
- Codes de Reed-Solomon (définition et théorème sur la distance minimale mais pas de démonstration)
Progression du cours en 2016-2017
Chapitre 1 : Codes correcteurs d'erreurs
- Mercredi 7 septembre 2016 : généralités sur les codes correcteurs d'erreurs et sur les codes linéaires binaires (extraits des § 1.1 et § 1.2)
- Définition 1.1.1 : code correcteurs d'erreur
- Exemple 1.1.2
- Proposition 1.1.3 : distance de Hamming
- Exemple 1.1.6
- Proposition 1.2.1 : le corps à 2 éléments F2
- Remarque 1.2.3 : (Fq)n est un Fq-espace vectoriel
- Définition 1.2.4 : codes linéaires sur un corps fini Fq
- Définition 1.2.5 (points (1) et (2)) : matrice génératrice d'un code linéaire
- Exemple 1.2.7
- Mercredi 14 septembre 2016 :
- Définition 1.2.5 (points (3) et (4)) : matrice génératrice standard, codes systématiques
- remarque 1.2.6 : code équivalents
- proposition 1.2.8
- proposition 1.2.9 et définition 1.2.10 : matrices de contrôle,, syndrôme
- Mercredi 21 septembre 2016 : codes linéaires (§ 1.2.3, § 1.2.4 et § 1.2.5)
- distance minimum
- décodage
- codes de Hamming
- Mercredi 28 septembre 2016 : pas de cours
Chapitre 2, Corps finis
- Mercredi 5 octobre 2016 : Constructions de corps finis à partir de nombres entiers (§ 2.1)
- Division euclidienne
- Diviseurs, nombres premiers, nombres premiers entre eux, théorème de Bezout, lemme de Gauss
- Construction de Z/nZ
- (Z/nZ,+,×) est un anneau
- (Z/nZ,+,×) est un corps si et seulement si n est premier
- Si p est premier, on note Fp = Z/pZ le corps à p éléments
- Éléments inversibles de Z/nZ pour n quelconque
- Mercredi 12 octobre 2016 : Constructions de corps finis à partir de polynômes (§ 2.2)
- Division euclidienne
- Diviseurs, polynômes irréductibles, polynômes premiers entre eux, théorème de Bezout, lemme de Gauss
- Construction de k[X]/(P)
- (k[X]/(P),+,×) est un anneau
- (k[X]/(P),+,×) est un corps si et seulement si P est irréductible
- Caractéristique d'un corps fini
- Élément primitif d'un corps fini
- Tout corps fini est isomorphe à un corps Fp[X]/(P)
- Mercredi 19 octobre 2016 : Éléments de classification des corps finis (§ 2.3)
- Caractéristique d'un corps fini
- Élément primitif d'un corps fini
- Tout corps fini est isomorphe à un corps Fp[X]/(P)
- Mercredi 26 octobre 2016 : partiel
- Mercredi 2 novembre 2016 : pas de cours
Chapitre 3, Cryptographie
- Mercredi 9 novembre 2016
- Principe de la cryptographie (§3.1)
- Algorithme RSA (§ 3.2)
- Exponentielle et logarithme discrets (chapitre 2, § 2.4)
- Algorithme de El Gamal (§ 3.3)
- Protocole d'échange de clefs de Diffie-Helman
Chapitre 4, Codes cycliques
- Mercredi 16 novembre 2016
- Outils et notations (§4.1)
- Définition (§4.2)
- Polynôme générateur - Encodage - Matrice génératrice (§4.3)
- Polynôme de contrôle - Matrice de contrôle (§4.4)
- Codes de Reed-Solomon (§4.5) (défintion et théorème sur la distance minimale mais pas de démonstration)