Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours et exercices avec solutions SCIENCES SUP THÉORIE DES CODES Compression, c

Cours et exercices avec solutions SCIENCES SUP THÉORIE DES CODES Compression, cryptage, correction Jean-Guillaume Dumas Jean-Louis Roch Éric Tannier Sébastien Varrette Master • Écoles d’ingénieurs THÉORIE DES CODES Compression, cryptage, correction Jean-Guillaume Dumas Maître de conférences à l’université Grenoble 1 Jean-Louis Roch Maître de conférences à l’ENSIMAG Éric Tannier Chercheur de l’INRIA Rhône-Alpes à l’université Lyon 1 Sébastien Varrette Doctorant à l’université du Luxembourg Illustration de couverture : Antenne-relais de transmission sur le mont Pisgah dans les Appalaches. Photographie de Jean-Guillaume Dumas. © Dunod, Paris, 2007 ISBN 9-78-210-050692-7 Pr´ eambule Cet ouvrage a ´ et´ e initi´ e au printemps 2000, avec la cr´ eation du D´ epartement ENSIMAG-ENSERG T´ el´ ecommunications ` a l’Institut National Polytechnique de Grenoble et la construction d’un cours g´ en´ eral de premi` ere ann´ ee (niveau Licence troisi` eme ann´ ee dans le sch´ ema LMD) d’introduction aux codes et ` a leurs applications. ´ Edit´ e initialement sous forme de polycopi´ e, il a ´ evolu´ e en devenant un support de cours de r´ ef´ erence pour diﬀ´ erents cours des universit´ es de Grenoble, ` a la fois ` a l’Institut National Polytechnique de Grenoble (INPG) et ` a l’Universit´ e Joseph Fourier (UJF). Nous remercions nos coll` egues qui ont particip´ e ` a ces enseignements et ont contribu´ e par leurs commentaires ` a am´ eliorer notre support de cours : Gilles Debunne, Yves Denneulin, Dominique Duval, Gr´ egory Mouni´ e et Karim Sa- mak´ e. Grenoble, Lyon, Luxembourg, le 19 d´ ecembre 2006. Jean-Guillaume Dumas, Jean-Louis Roch, ´ Eric Tannier, S´ ebastien Varrette. Sommaire Introduction 13 1 Th´ eorie des codes 19 1.1 De Jules C´ esar ` a la t´ el´ ecopie . . . . . . . . . . . . . . . . . . . 19 1.1.1 La source : de l’image ` a la suite de pixels . . . . . . . . 19 1.1.2 La compression du message . . . . . . . . . . . . . . . . 20 1.1.3 La d´ etection d’erreurs . . . . . . . . . . . . . . . . . . . 21 1.1.4 Le chiﬀrement . . . . . . . . . . . . . . . . . . . . . . . 22 1.1.5 Le d´ ecodage . . . . . . . . . . . . . . . . . . . . . . . . . 23 L’attaque et le d´ echiﬀrement . . . . . . . . . . . . . . . 23 La d´ ecompression et les pertes . . . . . . . . . . . . . . 24 1.1.6 Les d´ efauts de ce code . . . . . . . . . . . . . . . . . . . 24 1.1.7 Ordres de grandeur et complexit´ e des algorithmes . . . 26 Taille des nombres . . . . . . . . . . . . . . . . . . . . . 26 La vitesse des ordinateurs . . . . . . . . . . . . . . . . . 26 Taille et ˆ age de l’univers . . . . . . . . . . . . . . . . . . 27 Complexit´ e des algorithmes . . . . . . . . . . . . . . . . 27 1.2 Codage par ﬂot et probabilit´ es . . . . . . . . . . . . . . . . . . 28 1.2.1 Le code de Vernam . . . . . . . . . . . . . . . . . . . . . 29 1.2.2 Un peu de probabilit´ es . . . . . . . . . . . . . . . . . . . 30 ´ Ev` enements et mesure de probabilit´ e . . . . . . . . . . . 30 Probabilit´ es conditionnelles et Formule de Bayes . . . . 31 1.2.3 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Source d’information . . . . . . . . . . . . . . . . . . . . 32 Entropie d’une source . . . . . . . . . . . . . . . . . . . 33 Entropies conjointe et conditionnelle . . . . . . . . . . . 34 Extension d’une source . . . . . . . . . . . . . . . . . . 35 1.2.4 Chiﬀrement parfait . . . . . . . . . . . . . . . . . . . . . 36 1.2.5 Mise en pratique du chiﬀrement parfait ? . . . . . . . . . 37 1.3 Codage par blocs, alg` ebre et arithm´ etique . . . . . . . . . . . . 37 6 Sommaire 1.3.1 Blocs et modes de chaˆ ınage . . . . . . . . . . . . . . . . 38 Le mode ECB : Electronic Code Book . . . . . . . . . . 39 Le mode CBC : Cipher Bloc Chaining . . . . . . . . . . 39 Le mode CFB : Cipher FeedBack . . . . . . . . . . . . . 40 Le mode OFB : Output FeedBack . . . . . . . . . . . . . 40 Le mode CTR : Counter-mode encryption . . . . . . . . 41 1.3.2 Structures alg´ ebriques des mots de codes . . . . . . . . 41 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Anneaux . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Espaces vectoriels . . . . . . . . . . . . . . . . . . . . . 44 Alg` ebre lin´ eaire . . . . . . . . . . . . . . . . . . . . . . . 45 1.3.3 Codage bijectif d’un bloc . . . . . . . . . . . . . . . . . 46 Inverse modulaire : algorithme d’Euclide . . . . . . . . . 46 L’indicatrice d’Euler et le th´ eor` eme de Fermat . . . . . 49 L’exponentiation modulaire et le logarithme discret . . . 52 Fonctions ` a Sens Unique . . . . . . . . . . . . . . . . . . 54 1.3.4 Construction des corps premiers et corps ﬁnis . . . . . . 55 Tests de primalit´ e et g´ en´ eration de nombres premiers . . 55 Arithm´ etique des polynˆ omes . . . . . . . . . . . . . . . 58 L’anneau V [X]/P et les corps ﬁnis . . . . . . . . . . . . 59 Polynˆ omes irr´ eductibles . . . . . . . . . . . . . . . . . . 60 Constructions des corps ﬁnis . . . . . . . . . . . . . . . 63 1.3.5 Impl´ ementations des corps ﬁnis . . . . . . . . . . . . . . 64 Op´ erations sur les polynˆ omes . . . . . . . . . . . . . . . 64 Utilisation des g´ en´ erateurs . . . . . . . . . . . . . . . . 65 Racines primitives . . . . . . . . . . . . . . . . . . . . . 66 1.3.6 G´ en´ erateurs pseudo-al´ eatoires . . . . . . . . . . . . . . . 69 Les g´ en´ erateurs congruentiels . . . . . . . . . . . . . . . uploads/Science et Technologie/ cours-et-exercices-avec-solutions-theori.pdf