Formulaire et glossaire

Ce formulaire rassemble, chapitre par chapitre, les définitions, les formules et les théorèmes essentiels du cours, avec la notation des chapitres correspondants: les numéros d'équations et de théorèmes y renvoient directement. Chaque formule est suivie de la signification des symboles, de ses conditions de validité et du résultat numéroté dont elle provient; les démonstrations, les exemples chiffrés et les pièges classiques restent dans les chapitres. Les rappels de mathématiques — puissances de deux, logarithmes, sommes usuelles, dénombrement, congruences, Stirling — sont à l'annexe A et ne sont pas répétés ici.

Conventions du cours, fixées une fois pour toutes: le logarithme est toujours en base 2 et la base est écrite, ${\log }_2$, sauf à l'intérieur d'une classe de complexité où elle ne change rien (on écrit alors $\Theta (\log n)$, la formule de changement de base faisant que la classe ne dépend pas de la base); $\ln$ est le logarithme naturel. L'unité d'information est le bit (symbole b), le groupe de huit bits est l'octet (symbole o) — le mot anglais n'est jamais employé. Les préfixes décimaux (ko $=10^3$ o, Mo, Go, To) servent aux tailles de fichiers et aux débits, les préfixes binaires (Kio $=2^{10}$ o, Mio, Gio, Tio) là où le matériel est binaire; chaque fois, on dit lequel. Une base s'écrit en indice, , , . La taille de l'entrée est , son nombre de bits , la taille d'un alphabet ou . Décimales à la virgule (), milliers séparés par une espace fine ().

Tableau I – Toutes les complexités établies dans le cours

Les coûts ci-dessous sont ceux que les chapitres démontrent ou mesurent, avec l'opération comptée. Rappel du chapitre 2: une affirmation de complexité utile précise quel algorithme, quelle opération, en fonction de quelle taille, dans quel cas et avec quelle notation.

Trois lectures de ce tableau. D'abord, la classe de croissance décide de ce qui est faisable: à l'hypothèse de travail de $10^9$ opérations élémentaires par seconde, une seconde traite $n=10^9$ en linéaire, $39620077$ en quasi-linéaire, $31622$ en quadratique, $1000$ en cubique, $29$ en exponentiel et $12$ en factoriel (chapitre 2). Ensuite, : avec les constantes et , le tri quadratique l'emporte jusqu'à (exemple 2.4). Enfin, : la même recherche répétée coûte milliards de comparaisons dans un tableau non trié, par dichotomie et quelques dizaines de milliers en table de hachage (chapitre 4).

Tableau II – Tous les codes et toutes les bornes

Le fil qui relie les trois familles: le chapitre 7 retire de la redondance jusqu'au plancher $H$, le chapitre 8 en rajoute une, choisie et mesurée, jusqu'au plafond $C$, et le chapitre 10 en ajoute une troisième, les $58$ octets d'en-têtes, qui ne portent ni information ni protection mais organisation. Sur ABRACADABRA, les quatre nombres à retenir sont $33$ bits en longueur fixe, $23$ bits par Huffman, $22,44$ bits de plancher d'entropie, et $69,7\%$ pour le taux de compression.

Chapitre 1 – Représentation de l'information

Définition du bit et relation (1.1): une information est la désignation d'une possibilité parmi plusieurs, également plausibles — hypothèse que le chapitre 6 lèvera. Repères à connaître: $2^{10}=1024$, $2^{20}\approx 10^6$, $2^{32}\approx 4,3\cdot 10^9$, .

Écriture positionnelle en base $b\ge 2$ (1.2). L'entier se convertit par divisions successives (les restes lus du dernier au premier), la partie fractionnaire par multiplications successives (les parties entières lues du premier au dernier). Puisque $8=2^3$ et $16=2^4$, un chiffre octal vaut trois bits et un chiffre hexadécimal quatre: l'hexadécimal est une abréviation du binaire, pas une base de calcul.

Critère de finitude (exemple 1.2). En base 2, seules les fractions dyadiques s'écrivent exactement: $0,6875=11/16=(0,1011{)}_2$ est finie, $0,1=(0,0\overline{0011}{)}_2$ ne l'est pas.

Complément à deux (1.3) et théorème 1.1 avec sa relation (1.4): le bit de poids fort porte un poids négatif, l'opposé s'obtient en inversant tous les bits et en ajoutant 1, et la soustraction devient une addition, donc un seul circuit additionneur suffit. La plage $[-2^{n-1},2^{n-1}-1]$ est asymétrique: sur huit bits $[-128,127]$, et $-(-128)$ n'est pas représentable. Un même motif n'a aucun sens en soi: $(10011100{)}_2$ vaut non signé et en complément à deux.

Format binary64 de la norme IEEE 754 (1.5): 1 bit de signe, 11 bits d'exposant biaisé de $1023$, 52 bits de mantisse plus un bit implicite, soit 53 bits significatifs. Les valeurs $E=0$ et $E=2047$ sont réservées (dénormalisés, zéros, infinis, NaN). Le double le plus proche de $0,1$ vaut exactement $3602879701896397/2^{55}$, c'est-à-dire , et rend : ce n'est pas un bogue, c'est un arrondi correct. L'écart relatif entre deux doubles voisins au voisinage de 1 vaut , et l'erreur relative d'un arrondi ne dépasse jamais . Le premier entier non représentable est .

Deux pièges. L'absorption: $x\oplus y=x$ dès que $|y|$ est inférieur à la moitié du pas au voisinage de $x$; 1e16 + 1.0 rend 1e16, et additionner dix fois $0,1$ donne 0.9999999999999999. L'élimination catastrophique: soustraire deux nombres proches promeut en tête les chiffres faux déjà présents; sur $x^2-10^{8}x+1=0$, la formule scolaire rend au lieu de , soit plus de d'erreur relative, que la forme corrige.

Taille d'une image matricielle de $L\times H$ pixels sur $p$ bits (1.6), débit et taille d'un son échantillonné à $f_e$ hertz sur $q$ bits pour $c$ canaux pendant $d$ secondes (1.7). Valeurs de référence: une image $1920\times 1080$ en couleur vraie pèse Mo; une minute au format du disque compact ( Hz, 16 bits, 2 canaux) pèse Mo, soit Mio, à un débit de Mbit/s. Le théorème d'échantillonnage de Nyquist–Shannon, ici parce que sa démonstration relève de l'analyse de Fourier, exige .

Texte: ASCII code 128 caractères sur sept bits (majuscules et minuscules décalées de $32=2^5$, donc un bit à basculer pour changer la casse). Unicode attribue un point de code de U+0000 à U+10FFFF; UTF-8 (RFC 3629) l'écrit sur 1 à 4 octets selon les gabarits 0xxxxxxx, 110xxxxx 10xxxxxx, 1110xxxx 10xxxxxx 10xxxxxx, 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx. Trois conséquences: tout fichier ASCII est déjà de l'UTF-8 valide; un octet de continuation se reconnaît à ses bits de tête 10; et aucun mot n'est le préfixe d'un autre — c'est un code préfixe au sens du chapitre 7. Ainsi é (U+00E9) s'écrit C3 A9 et € (U+20AC) s'écrit E2 82 AC. Lire de l'UTF-8 comme du latin-1 produit du mojibake — é devient é — sans qu'aucun bit n'ait changé.

Norme ISO/IEC 80000-13. Excès du binaire sur le décimal: $+2,4\%$ au kilo, $+4,9\%$ au méga, $+7,4\%$ au giga, $+10,0\%$ au téra. Un disque annoncé à $500$ Go contient exactement $5\cdot 10^{11}$ octets et s'affiche $500\cdot 10^9/2^{30}=465,66$ : l'écart apparent de n'est aucune perte, c'est le rapport . Et un abonnement à «100 Mbit/s» transfère au mieux Mo/s: un facteur 8 se cache dans la minuscule du symbole.

Chapitre 2 – Algorithmes et complexité

Identité d'Euclide (2.1). L'algorithme s'écrit tant que b ≠ 0: (a, b) ← (b, a mod b). Sa correction et sa terminaison (théorème 2.2) illustrent la méthode du chapitre: invariant $\gcd (a,b)=\gcd (a_0,b_0)$ pour la correction, variant $V=b$, entier positif strictement décroissant dans $\mathbb{N}$ bien fondé, pour la terminaison. Le majorant grossier est divisions; le vrai majorant, obtenu en montrant que (exercice 2.1), est : le coût d'Euclide est , donc , ce qui le rend utilisable sur les entiers de 2048 bits du chapitre 9.

Un invariant est vrai avant le premier tour, conservé par un tour, et donne le résultat une fois joint à la négation de la condition de boucle. Un ensemble bien fondé ne contient aucune suite infinie strictement décroissante; un variant prend ses valeurs dans un tel ensemble et décroît strictement à chaque tour. Les deux mots comptent: une décroissance large autorise la stagnation, et $V_k=1/k$ décroît strictement dans ${\mathbb{R}}_{>0}$, qui n'est pas bien fondé, sans jamais s'arrêter.

Définitions (2.2) et (2.3). Le premier quantificateur autorise à ignorer tout facteur constant, le second tout comportement en petites tailles: $O$ est une propriété de la queue, à une constante multiplicative près. L'écriture avec un signe égal est un abus toléré — $O(g)$ est un ensemble de fonctions — et elle ne se retourne pas.

Définition (2.4) et théorème 2.3: $\Theta =O\cap \Omega$; tout polynôme $P$ de degré $d$ à coefficient dominant positif vérifie $P(n)=\Theta (n^d)$; et si $f(n)/g(n)\to L$ avec , alors . : dire qu'un algorithme est en n'affirme pas qu'il coûte , et tout algorithme en est aussi en .

Coût du tri par sélection (2.5), identique au meilleur, au pire et en moyenne: les deux boucles sont bornées et sans sortie anticipée, donc le contenu du tableau n'y change rien. Son seul atout est le nombre d'échanges, au plus $n-1$.

Coût en comparaisons du tri par insertion (théorème 2.4), sur des éléments deux à deux distincts; le cas moyen (2.6), sous la loi uniforme sur les $n!$ permutations, vaut environ $n^2/4$, soit la moitié du pire cas — même classe. Le tri par insertion est donc adaptatif et le tri par sélection ne l'est pas, ce qui est la seule différence qui compte en pratique.

Le tableau du cours, $A=[38,27,43,3,9,82,10]$, trié $[3,9,10,27,38,43,82]$, sert de référence commune aux chapitres 2, 3 et 4 (et au chapitre 10 du cours Introduction à la programmation). Comptages d'exécution:

Les $15$ comparaisons du tri par insertion se décomposent en $1+1+3+4+1+5$, une étape par élément inséré. La borne d'information du chapitre 3 vaut ici $\lceil {\log }_2(7!)\rceil =\lceil 12,2992\rceil =13$: le tri fusion est à de l'optimum théorique pour .

À $10^9$ opérations élémentaires par seconde — hypothèse de travail, jamais une mesure —, la plus grande taille traitable en une seconde vaut $10^9$ en $\Theta (n)$, $39620077$ en $\Theta (n{\log }_{2}n)$, en , en , en et en . Multiplier la machine par mille fait passer à et à :

Chapitre 3 – Récursivité et diviser pour régner

Définitions récursives (3.1) et (3.2). Une définition récursive bien fondée comporte un cas de base, un cas récursif et une taille qui décroît strictement; les trois sont nécessaires, et les cas de base doivent couvrir toutes les valeurs que le cas récursif peut atteindre par le bas — d'où deux cas de base pour Fibonacci. Prouver un algorithme récursif, c'est faire une récurrence: le cas de base est l'initialisation, l'appel récursif est l'hypothèse de récurrence (théorème 3.1).

Nombre total d'appels de Fibonacci récursif naïf (théorème 3.2, relations (3.3) et (3.4)): $15$ appels pour $n=5$, $2692537$ pour $n=30$, $331160281$ pour $n=40$. L'arbre a $F_{n+1}$ feuilles et nœuds internes, donc autant d'additions: . La mémoïsation ramène le coût à temps et mémoire, la boucle à deux variables à temps et mémoire.

Chaque appel en cours occupe un cadre sur la pile d'appels (paramètres, variables locales, adresse de retour), en discipline «dernier entré, premier sorti». La pile est de taille fixe: une récursion de profondeur linéaire finit par déborder — en Python, dès $998$ appels avec la limite par défaut — alors qu'une récursion qui divise reste à une vingtaine de cadres pour un million d'éléments. Règle pratique: une récursion qui divise la taille est presque toujours bonne, une récursion qui la décrémente est une boucle mal écrite, et une récursion qui recalcule les mêmes sous-problèmes doit être mémoïsée.

Coût de la recherche dichotomique sur un tableau trié (théorème 3.3, relation (3.5)): $3$ pour sept éléments, $20$ pour un million, $30$ pour un milliard. Son invariant: si $x$ figure dans $a$, alors son indice appartient à $[\text{bas},\text{haut}]$. Deux avertissements: le tri est un prérequis que rien dans le code ne vérifie, et m ← (bas + haut) / 2 peut déborder — écrire m ← bas + (haut − bas) / 2.

Récurrence du schéma diviser pour régner (3.6): $a$ sous-problèmes de taille $n/b$, plus $f(n)$ pour diviser et combiner. Dichotomie: $a=1$, $b=2$, $f=\Theta (1)$. Tri fusion: $a=2$, , .

Résolution par l'arbre de récursion (3.7): au niveau $k$ il y a $a^k$ sous-problèmes de taille $n/b^k$, et il y a $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ feuilles. Tout se joue dans la comparaison entre le coût des feuilles et celui de la racine.

Théorème maître (théorème 3.5), admis: sa démonstration ne contient aucune idée que l'arbre n'ait déjà livrée, mais elle exige de traiter les parties entières et de majorer (3.7) par une série géométrique dans chacun des trois cas. La condition de régularité du cas 3 est $af(n/b)\le \kappa f(n)$ pour un $\kappa <1$. Trois limitations: il laisse un trou entre les cas 1 et 2 (ainsi $T=2T(n/2)+n{\log }_{2}n$ donne et échappe au théorème), la régularité n'est pas décorative, et il ne s'applique aux récurrences qui décrémentent — ou .

Applications: tri fusion $\Theta (n{\log }_{2}n)$ (cas 2); dichotomie $\Theta ({\log }_{2}n)$ (cas 2 avec $c=0$); multiplication de matrices naïve par blocs $T=8T(n/2)+\Theta (n^2)=\Theta (n^3)$ (cas 1, aucun gain), et avec ; Karatsuba , .

Borne inférieure des tris par comparaisons (théorème 3.6, relations (3.8) et (3.9)). L'argument est celui de l'arbre de décision: chaque nœud interne porte une comparaison, chaque feuille une permutation; l'arbre a au moins $n!$ feuilles puisque l'algorithme doit être correct sur chacune des $n!$ entrées, et un arbre binaire de hauteur $h$ en a au plus $2^h$; donc $2^h\ge n!$. La minoration élémentaire $n!\ge (n/2{)}^{n/2}$ donne , et Stirling la valeur exacte avec . — à , contre une borne de , soit . Attention: une borne inférieure n'est pas toujours atteignable; elle l'est pour et , elle ne l'est pas pour où le minimum vrai vaut alors que .

Tours de Hanoï (3.10, théorème 3.7). La formule est atteinte par la procédure récursive, et aucune stratégie ne fait mieux: le plus grand disque doit quitter $A$ vers $C$ à un instant où les $n-1$ autres sont tous sur $B$, d'où $M(n)\ge 2M(n-1)+1$. Pour $n=64$, déplacements, soit milliards d'années à un par seconde.

Chapitre 4 – Structures de données et graphes

Adressage d'un tableau (4.1): une multiplication et une addition, indépendantes de $n$, de $i$ et du contenu — d'où l'accès en $\Theta (1)$, et d'où la possibilité même de la dichotomie. La contrepartie est la contiguïté: insérer en position $i$ décale $n-i$ éléments. L'ajout en fin avec doublement de capacité coûte $\Theta (1)$ amorti: construire $1000$ éléments déclenche $1+2+4+\cdots +512=1023$ recopies, moins de deux par élément, quelle que soit la taille finale. La liste chaînée échange exactement l'inverse: pour atteindre le -ème, pour insérer à une position déjà tenue, au prix d'une ou deux adresses par cellule.

Une pile (LIFO) et une file (FIFO) ont les mêmes coûts, $\Theta (1)$ partout, et pas le même ordre de sortie: sur la séquence «ajouter 3, 7, 5, retirer, ajouter 9, retirer trois fois», la pile rend $5,9,7,3$ et la file rend $3,7,5,9$. Cette seule différence sépare la pile d'appels d'une file d'attente, et — à la fin du chapitre — le parcours en profondeur du parcours en largeur.

Borne inférieure sur la hauteur d'un arbre binaire (théorème 4.1, relation (4.2)). Un arbre binaire de recherche vérifie en tout nœud la propriété d'ordre (sous-arbre gauche plus petit, droit plus grand) et se cherche en au plus $h+1$ comparaisons. Le coût est $O(h)$, pas $O(\log n)$: la hauteur dépend de l'ordre d'insertion, pas de l'ensemble des clefs. Le tableau du cours inséré dans l'ordre donne un arbre de hauteur 4 pour $13$ comparaisons d'insertion; les mêmes clefs triées donnent une chaîne de hauteur 6 pour $21$ comparaisons — un ABR dégénéré est une liste chaînée. Le $O(\log n)$ est la propriété des arbres équilibrés (AVL, rouge-noir, arbres B). Le rend les clefs triées quelle que soit la forme de l'arbre.

Facteur de charge d'une table de hachage à chaînage et coûts moyens sous l'hypothèse du hachage uniforme. Si l'on maintient $m$ proportionnel à $n$ (redimensionnement dès que $\alpha$ dépasse un seuil, typiquement $0,75$), les trois opérations coûtent $O(1)$ en moyenne, le re-hachage s'amortissant comme le doublement d'un tableau. Le $O(1)$ est conditionnel et ses deux conditions sont explicites: la fonction doit réellement disperser vos clefs, et le facteur de charge doit rester borné. Le pire cas reste $\Theta (n)$. Les collisions sont inévitables par le principe des tiroirs et arrivent bien avant la saturation: avec 6 clefs dans 7 seaux, la probabilité d'au moins une collision vaut $1-5040/117649\approx 95,7\%$ — c'est le calcul des anniversaires, qui reviendra au chapitre 9.

Lemme des poignées de main (théorème 4.2), par double comptage des couples (sommet, arête incidente); en particulier le nombre de sommets de degré impair est pair. Un graphe connexe sans cycle est un arbre et vérifie $m=n-1$, nombre minimal d'arêtes d'un graphe connexe.

Le seuil se calcule: les listes battent la matrice d'octets lorsque $16m+8n<n^2$, soit une densité d'environ $12,5\%$, et les graphes réels sont très en dessous — $0,32$ Mo contre $12,5$ Mo pour un réseau routier de $10000$ carrefours et $15000$ tronçons, To contre Po pour un graphe social hypothétique de comptes de degré moyen 200, c'est-à-dire la différence entre faisable et impossible.

Un seul schéma de parcours donne les deux algorithmes: on marque, on met dans un conteneur, on retire, on visite, on ajoute les voisins non découverts. File $\Rightarrow$ parcours en largeur, pile $\Rightarrow$ parcours en profondeur. Les deux coûtent $\Theta (n+m)$ en listes d'adjacence, chaque sommet entrant au plus une fois dans le conteneur et chaque arête étant examinée deux fois.

Le parcours en largeur calcule les distances d'un graphe non pondéré (théorème 4.3). Le ressort de la preuve est la monotonie de la file: si elle contient $x_1,\dots ,x_r$ de la tête vers la queue, alors $d[x_1]\le \cdots \le d[x_r]\le d[x_1]+1$, donc les sommets sortent par valeurs de non décroissantes et l'on n'atteint jamais la couche avant d'avoir épuisé la couche . Le parcours en profondeur n'est pas un algorithme de plus court chemin, et son erreur peut être arbitrairement grande.

Opération centrale de l'algorithme de Dijkstra, qui rend définitif à chaque tour le sommet non définitif de $d$ minimal. Coût $\Theta (n^2)$ avec un tableau (bon pour un graphe dense), $O((n+m)\log n)$ avec un tas binaire (bon pour un graphe creux). Les sommets deviennent définitifs par distances croissantes, et c'est le cœur de la preuve: tout chemin non encore envisagé doit sortir de l'ensemble des définitifs par un sommet $x$ non définitif, de sorte que son poids vaut au moins $d[x]\ge d[u]$ le poids du reste, positif ou nul. L'hypothèse de sert exactement là et nulle part ailleurs; avec un poids négatif l'algorithme rend des résultats faux, et ajouter une constante à tous les poids ne corrige rien, puisque le décalage s'applique et pénalise davantage les chemins longs.

Chapitre 5 – Les limites du calcul

Une machine de Turing est la donnée d'un ruban infini sur un alphabet fini $\Gamma$ contenant un blanc, d'une tête, d'un ensemble fini d'états $Q$ et d'une table de transition $\delta$ envoyant (état, symbole lu) sur (symbole écrit, déplacement, nouvel état). Une configuration est le triplet (ruban, position de la tête, état). Tout y est fini sauf le ruban — la table n'a que $|Q|\times |\Gamma |$ lignes — donc une machine s'écrit comme un mot fini $⟨M⟩$.

Robustesse du modèle (théorème 5.1, admis): plusieurs rubans, ruban semi-infini, alphabet binaire, non-déterminisme, machines à registres, $\lambda$-calcul, fonctions récursives générales et tout langage usuel à mémoire non bornée calculent exactement la même classe de fonctions. Les simulations coûtent du temps — passer de $k$ rubans à un seul peut élever le nombre d'étapes au carré — mais rien de calculable ne devient incalculable. Machine universelle (théorème 5.2, admis): il existe $U$ qui, sur $⟨M⟩\#w$, simule $M$ sur $w$ et s'arrête si et seulement si $M$ s'arrête. Un ordinateur est une machine universelle, un programme est une donnée: on écrit donc des programmes qui manipulent des programmes, et l'on fait raisonner un programme sur lui-même.

Thèse de Church–Turing: toute fonction calculable par un procédé effectif l'est par une machine de Turing. Ce n'est pas un théorème et ne peut pas en être un, l'un de ses deux membres étant informel; elle s'appuie sur la convergence de modèles conçus indépendamment, sur l'analyse du calcul humain faite par Turing, et sur quatre-vingt-dix ans sans contre-exemple. Elle sert à passer de l'informel au formel — un algorithme en français suffit à établir la calculabilité — et jamais à établir une impossibilité. Elle ne dit rien de l'efficacité: l'idée que tout modèle raisonnable en simule un autre avec un surcoût seulement polynomial est la thèse étendue (Cobham–Edmonds), bien plus fragile.

Hypothèse (5.1) du théorème 5.3: un tel $H$ n'existe pas. La démonstration construit $D(x)$ qui calcule $H(x,x)$, boucle si la réponse est «oui» et s'arrête sinon, d'où (5.2), puis applique $D$ à sa propre description:

Contradiction (5.3): $A⟺\neg A$. Rien dans la construction n'est douteux — appeler un sous-programme, tester, boucler, passer un mot en argument — donc l'hypothèse tombe. $\text{ARREˆT}$ est semi-décidable: on reconnaît les «oui» par simulation, jamais les «non».

Le théorème dit: impossible, pas difficile — aucun algorithme, sur aucune machine, en aucun temps. Il ne dit pas qu'on ne peut rien dire d'un programme: il porte sur une procédure universelle et exacte, et renoncer à l'un de ces adjectifs rend la tâche possible (langages dont tous les programmes terminent, analyseurs autorisés à répondre «je ne sais pas», simulation bornée en temps). L'argument est la diagonalisation de Cantor transportée aux programmes, et il donne gratuitement le théorème 5.4: les programmes sont dénombrables, les fonctions $\mathbb{N}\to \{0,1\}$ ne le sont pas, donc presque aucune fonction n'est calculable — plus fort en quantité, plus faible en contenu, puisqu'il n'en exhibe aucune.

Réduction (5.4) et théorème 5.5: si $A\le B$ et $B$ décidable, alors $A$ décidable; par contraposée, si $A$ est indécidable, $B$ l'est aussi. Le sens de la flèche est toute la difficulté: pour montrer que $B$ est indécidable, il faut $\text{ARREˆT}\le B$, jamais l'inverse — On obtient ainsi l'indécidabilité de «ce programme affiche-t-il bonjour?», de l'équivalence de deux programmes, de la totalité, de l'atteignabilité d'une ligne, du problème de correspondance de Post et du dixième problème de Hilbert (Matiyasevich, 1970).

Théorème de Rice (théorème 5.7, informel, admis): toute propriété non triviale de la fonction qu'un programme calcule est indécidable. L'hypothèse «de ce qu'il calcule, et non de la manière dont il est écrit» sauve l'analyse de programmes: les propriétés syntaxiques — nombre de lignes, présence d'une instruction, déclaration des variables, compilation — restent décidables.

Classe $\mathsf{P}$, la taille de l'entrée étant le nombre de symboles qu'il faut pour l'écrire — pour un entier, son nombre de bits et non sa valeur. La classe est robuste (changer de modèle multiplie le temps par un polynôme, et un polynôme d'un polynôme est un polynôme) et stable par composition. Deux réserves: $\Theta (n^{100})$ est dans $\mathsf{P}$ et inutilisable, $\Theta (2^{n/1000})$ n'y est pas et serait excellent; l'identification de $\mathsf{P}$ à «traitable» est une convention.

Classe $\mathsf{NP}$, définie par certificat et vérificateur. En une phrase: les problèmes dont les réponses «oui» admettent une preuve courte et facile à vérifier. Le nom signifie «non déterministe polynomial», jamais «non polynomial»: $\mathsf{NP}$ est une classe de problèmes, pas d'algorithmes, et $\mathsf{P}\subseteq \mathsf{NP}$ (théorème 5.8, en ignorant le certificat). Tout problème de $\mathsf{NP}$ est décidable en temps exponentiel par énumération des certificats, donc $\mathsf{NP}$ ne contient aucun problème indécidable.

Réduction polynomiale et théorème 5.9: ${\le }_p$ est transitive, et si $B\in \mathsf{P}$ alors $A\in \mathsf{P}$. Le ressort du coût est que $|f(x)|=O(n^a)$ . Un problème est - si pour tout , et - s'il est de plus dans . : si un seul problème -complet est dans , alors et y sont — des milliers de problèmes de domaines sans rapport tombent ou résistent ensemble. (théorème 5.11, admis): SAT et 3-SAT sont -complets; la démonstration code l'existence d'un calcul acceptant par une formule booléenne, avec variables du type «à l'instant , la case contient le symbole ».

Catalogue: 3-SAT, CLIQUE, ENSEMBLE INDÉPENDANT, COUVERTURE PAR SOMMETS, COLORIAGE à 3 couleurs, SAC À DOS, VOYAGEUR (version décision), CIRCUIT HAMILTONIEN, PARTITION. Frontières instructives: 2-SAT est dans $\mathsf{P}$ (parcours du graphe d'implications), le 2-coloriage aussi (bipartition), le circuit eulérien aussi (degrés pairs). Relations utiles: $\alpha (G)+\tau (G)=n$ et $\alpha (G)=\omega (\bar{G})$.

Aucune des trois inclusions n'est connue stricte, mais le théorème de hiérarchie en temps donne $\mathsf{P}\ne \mathsf{EXPTIME}$: au moins une l'est, sans qu'on sache laquelle. $\mathsf{P}$ contre $\mathsf{NP}$ est ouvert (prix du millénaire), et toute figure de ces classes n'a de sens que sous une hypothèse déclarée. $\mathsf{NP}$-complet ne veut pas dire impossible en pratique: heuristiques, approximation avec garantie prouvée (facteur 2 pour la couverture par sommets, en temps linéaire), cas particuliers polynomiaux, algorithmes pseudo-polynomiaux — le sac à dos en $O(nW)$ est exponentiel en la taille de l'entrée, $W$ s'écrivant sur ${\log }_{2}W$ bits — et solveurs exacts très efficaces sur les instances structurées. Et : c'est pourquoi la -complétude est une mauvaise base pour la cryptographie.

Chapitre 6 – Théorie de l'information et entropie

Théorème 6.1 et relation (6.1): l'additivité sur des événements indépendants force le logarithme, par l'équation fonctionnelle de Cauchy. Ce n'est pas un choix de commodité, c'est une conséquence.

Quantité d'information, ou surprise, d'un événement de probabilité $p\in ]0,1]$ (6.2); la base 2 est fixée par la convention $I(1/2)=1$. Autres unités: le nat ($1$ nat $=1/\ln 2\approx 1,4427$ bit), le dit en base 10. Distinguez toujours le bit physique, case valant 0 ou 1, du bit d'information, unité de mesure qui peut valoir $2,0404$.

Entropie de Shannon (6.3), avec la convention $0{\log }_{2}0=0$, seule valeur rendant $x{\log }_{2}x$ continue en 0 — d'où le fait qu'ajouter des symboles de probabilité nulle ne change pas l'entropie, ce qui permet de comparer des sources d'alphabets différents. $H$ ne dépend que du vecteur $(p_1,\dots ,p_n)$, jamais des symboles. Multipliée par le nombre de symboles, elle donne des bits; multipliée par un débit de symboles, des bits par seconde.

Inégalité de Gibbs (théorème 6.2, relation (6.4)), démontrée par $\ln t\le t-1$. Tout le reste du chapitre en découle. La quantité $D(p\Vert q)={\sum }_i{p}_i{\log }_2(p_i/q_i)\ge 0$ est la ; elle mesure le prix d'un mauvais modèle, et elle n'est symétrique, donc pas une distance.

Bornes (théorème 6.3, relation (6.5)), avec égalité à gauche si et seulement si la source est déterministe, à droite si et seulement si elle est uniforme. La borne haute s'obtient par Gibbs avec $q_i=1/n$, ou par Jensen appliqué à ${\log }_2$ concave.

Règle de regroupement (théorème 6.4, relation (6.6)). Conséquences: fusionner deux symboles fait toujours baisser l'entropie, scinder la fait monter d'au plus $p$ bit. Vérification sur ABRACADABRA: confondre C et D fait passer $H$ de $2,0404$ à $1,8586$, soit une perte de $\frac{2}{11}\times 1=0,1818$ bit par symbole, donc exactement 2 bits sur les onze symboles.

Entropie binaire (6.7): symétrique, strictement concave, maximale et égale à 1 en $p=1/2$, nulle en 0 et en 1, avec une tangente verticale aux bords. Valeurs de référence, toutes calculées:

Repère à retenir: il faut déjà onze pour cent d'erreurs pour détruire la moitié d'un bit (la racine exacte de $H(p)=1/2$ vaut $p=0,11003$). Cette lenteur est ce qui rend possibles les codes correcteurs du chapitre 8.

Entropie conjointe et entropie conditionnelle (6.8). $H(X\mid Y)$ est un nombre, pas une fonction de $y$: c'est l'incertitude qui reste sur $X$ une fois $Y$ connu, en moyenne. Et $H(X\mid Y)\ne H(Y\mid X)$ en général.

Règle de chaînage (théorème 6.5, relation (6.9)): décrire le couple coûte le prix de $X$, plus ce qu'il reste à dire de $Y$ une fois $X$ connu — et l'on peut commencer par l'un ou par l'autre.

Information mutuelle (6.10), symétrique bien que la première écriture ne le laisse pas deviner. Théorème 6.6: $I(X;Y)=D(p(x,y)\Vert p(x)p(y))\ge 0$, avec égalité si et seulement si $X$ et $Y$ sont indépendantes; en particulier conditionner ne peut pas augmenter l'entropie en moyenne. Attention: cela n'interdit pas $H(X\mid Y=y)>H(X)$ pour un particulier, ni — avec , indépendants et , on a et bit. Le diagramme de Venn est un aide-mémoire fidèle à deux variables et , où l'«intersection triple» peut valoir bit.

Le canal binaire symétrique du cours, $\mathbb{P}(X=0)=0,30$, $p=0,10$, sert de fil au chapitre 8. Loi conjointe $(0,27;0,03;0,07;0,63)$, marges $(0,30;0,70)$ et . Les six entropies, toutes recoupées:

Sur un canal binaire symétrique, $H(Y\mid X)=H(p)$ toujours, quelle que soit la loi de la source: c'est le bruit du canal et rien d'autre.

Redondance relative (6.11), à ne pas confondre avec la redondance du codage $1-H(X)/\ell$ lorsqu'un code de longueur fixe $\ell$ est imposé; dire chaque fois laquelle on utilise. C'est la grandeur qui articule toute la seconde moitié du cours: le chapitre 7 la supprime, le chapitre 8 en rajoute.

La source du cours, ABRACADABRA, onze symboles sur $\{\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D},\mathrm{R}\}$, modèle d'ordre 0:

Relation (6.12). Redondance du codage à longueur fixe: $1-2,0404/3=0,3199$, soit $32,0\%$. Redondance de la source par rapport à ${\log }_{2}5=2,3219$: $0,1213$, soit $12,1\%$. Les deux ne mesurent pas la même chose — le premier inclut le gaspillage dû au fait que 5 n'est pas une puissance de 2.

L'entropie est une propriété du modèle, jamais de la chaîne. ABABABABAB vaut $1$ bit/symbole à l'ordre 0 et $0$ à l'ordre 1. ABRACADABRA vaut $H_0=2,0404$ et, sur ses dix transitions, $H_1=0,6000$ bit/symbole — chiffre qui illustre un principe et ne mesure rien, puisqu'estimer vingt-cinq probabilités conditionnelles sur dix observations est statistiquement indéfendable. Améliorer le modèle abaisse la borne sans jamais contredire le théorème. Et l'entropie n'est ni une mesure de sens, ni de valeur, ni de vérité, ni la d'un objet individuel — celle-ci n'est pas calculable, par un argument voisin de celui du chapitre 5.

Chapitre 7 – Compression des données

Taux de compression (7.1). Certains auteurs emploient le rapport inverse et disent «3 pour 1»: précisez toujours lequel. Un compresseur sans perte a un codeur injectif et vérifie $d(c(x))=x$; un compresseur avec pertes gagne de la place précisément en confondant des données distinctes.

Argument de comptage (théorème 7.1, relation (7.2)), simple principe des tiroirs appliqué à une application injective. Pour $k=1$: au moins une suite de longueur $n$ n'est pas raccourcie. Quantitativement, moins d'une suite sur $2^9=512$ peut être raccourcie de 10 bits, moins d'une sur $524288$ de 20 bits. Un compresseur est donc un pari sur la structure des fichiers réels; il perd nécessairement sur le bruit, sur les données déjà comprimées et sur les données chiffrées. Vérification: zlib porte $10000$ octets pseudo-aléatoires à $10011$ octets, et un texte de octets comprimé à repasse à puis octets si l'on comprime à nouveau.

Un code est non singulier si les mots sont distincts, déchiffrable si son extension par concaténation, sans séparateur, est injective, et préfixe (ou instantané) si aucun mot n'est le début d'un autre. Préfixe $\Rightarrow$ déchiffrable, mais pas l'inverse: $\{0,01,011\}$ est déchiffrable sans être préfixe, au prix de l'instantanéité. Un code préfixe est exactement un choix de feuilles dans l'arbre binaire des préfixes.

Inégalité de Kraft (théorème 7.2, relation (7.3)), dans les deux sens. Sens direct: dans l'arbre complet de profondeur $L={\max }_i{\ell }_i$, le mot $c_i$ est ancêtre d'exactement $2^{L-{\ell }_i}$ feuilles et les descendances sont deux à deux disjointes. Réciproque: en triant et en posant (7.4), les premiers bits du développement binaire de forment un code préfixe des longueurs voulues. Le code est dit lorsque la somme vaut exactement 1: l'arbre n'a alors aucune feuille inutilisée. Le (1956, admis) étend l'inégalité aux codes déchiffrables: se restreindre aux codes préfixes ne coûte .

Longueur moyenne (7.5) et borne inférieure du codage de source (théorème 7.3, relation (7.6)). La démonstration pose $K={\sum }_i{2}^{-{\ell }_i}\le 1$ et $q_i=2^{-{\ell }_i}/K$, d'où par (7.7). L'égalité exige , donc des probabilités qui sont toutes des .

Théorème du codage de source (théorème 7.4, relation (7.8), Shannon 1948). La borne haute s'obtient avec les longueurs de Shannon–Fano ${\ell }_i=\lceil -{\log }_2{p}_i\rceil$ (7.9), admissibles puisque $2^{-{\ell }_i}\le p_i$, donc Kraft, puis . Le code optimal fait au moins aussi bien.

Codage par blocs de $k$ symboles indépendants, dont l'entropie vaut $kH$: le surcoût est divisé par $k$, au prix d'un alphabet de $2^k$ super-symboles. Sur une source binaire de paramètre $p=0,9$, d'entropie $H=0,4690$: ${\bar{L}}_k/k$ vaut , , et pour .

Algorithme de Huffman (1952): file de priorité sur les fréquences, fusion répétée des deux plus petits poids, $m-1$ fusions en $\Theta (m\log m)$. Le code se lit sur l'arbre (gauche $=0$, droite $=1$) et il est préfixe par construction. Théorème 7.5: il est optimal parmi les codes préfixes. La démonstration repose sur deux lemmes — l'arbre d'un code optimal est complet et donne des mots plus courts aux symboles plus probables (argument d'échange, $\Delta =-(p_i-p_j)({\ell }_i-{\ell }_j)<0$), et les deux symboles les moins probables peuvent être pris frères — puis sur la récurrence fondée sur

relation (7.10), où le terme ajouté ne dépend pas du code.

Le code du cours pour ABRACADABRA, avec la convention de départage de la file de priorité:

Contrôle de Kraft: $2^{-1}+4\cdot 2^{-3}=1$, le code est complet. Le message codé, $01101110100010101101110$, fait

soit $\bar{L}=23/11=2,0909$ bit/symbole et $\rho =23/33=0,697$, c'est-à-dire $69,7\%$ de la version à longueur fixe. L'encadrement du théorème 7.4 est vérifié: $2,0404\le 2,0909<3,0404$. L'écart bit sur le message, soit bit par symbole, est la , et non un défaut de l'algorithme: les longueurs idéales , et ne sont pas entières.

Ce qui est forcé ici, c'est le total, pas les longueurs. Les motifs binaires ne sont pas uniques (échanger deux fils échange un 0 et un 1 dans tout un sous-arbre, d'où $2^4=16$ codes de même arbre), et les longueurs elles-mêmes ne le sont pas non plus: un autre départage entre poids égaux, également légitime, donne $\mathrm{A}=1$, $\mathrm{R}=2$, $\mathrm{B}=3$, $\mathrm{C}=\mathrm{D}=4$, pour un total de bits. Le total est forcé parce qu'il est optimal; la répartition est une convention de départage. Un décodeur a donc toujours besoin de la table du code.

Codage arithmétique (7.11): on code le message entier comme un intervalle, dont la largeur est le produit des probabilités; nommer un point dans un intervalle de largeur $w$ coûte environ $\lceil -{\log }_{2}w\rceil$ bits, plus un ou deux de terminaison. Pour ABRACADABRA, $w=5^5{2}^4/11^{11}=50000/285311670611\approx 1,7525\cdot 10^{-7}$ et , — ce n'est pas une coïncidence, le logarithme transformant le produit en la somme des surprises. Sur onze symboles, l'arrondi coûte plus qu'il ne rapporte ( bits contre pour Huffman); sur dix répétitions, contre ; sur cent, contre .

Lempel–Ziv ne modélise pas: il remplace les répétitions par des renvois, le dictionnaire se construisant identiquement chez le codeur et le décodeur, d'où aucune table à transmettre. LZ78 émet des couples (indice de la phrase antérieure, caractère ajouté); LZ77 émet des triplets (distance, longueur, caractère) dans une fenêtre glissante, et la copie peut se chevaucher elle-même — le décodeur copie caractère par caractère, ce qui encode une répétition périodique à prix constant. Sur ABRACADABRA, LZ78 produit sept couples pour onze symboles et perd contre Huffman: l'algorithme passe la première moitié du fichier à apprendre. DEFLATE (zlib, gzip, zip, PNG) combine LZ77 puis Huffman — un modèle, puis un codeur entropique.

Compression avec pertes, trois étages: transformer (représentation réversible qui concentre l'information), quantifier (seul étage où l'information est détruite, celui que règle le curseur de qualité), coder sans perte. JPEG l'applique aux images (luminance-chrominance, blocs de $8\times 8$, transformée en cosinus discrète, table de quantification, zigzag, plages, Huffman), MP3 au son via un modèle psychoacoustique qui estime le seuil de masquage et alloue les bits sous ce seuil. Le réencodage cumule les dégâts. Enfin comprimer, chiffrer, protéger — dans cet ordre: un bon chiffré ressemble à une suite aléatoire, donc ne se comprime pas.

Chapitre 8 – Détection et correction d'erreurs

Bit de parité paire (8.1). Le contrôle du récepteur vérifie $\sigma (y)=\sigma (x)\oplus \sigma (e)=\sigma (e)$ — pour un code linéaire, le résultat du contrôle ne dépend que du motif d'erreur, jamais du mot émis. Théorème 8.1: la parité détecte toute erreur de poids impair et aucune erreur de poids pair. Sur $n=8$ bits à $p=0,01$, elle intercepte des mots abîmés et laisse passer mots pour mille — un filtre grossier, pas une garantie d'intégrité.

Distance de Hamming (8.2), qui est une vraie distance (théorème 8.2): l'inégalité triangulaire vient de $A\subseteq B\cup C$ sur les ensembles de positions où les mots diffèrent. Elle compte exactement le nombre d'erreurs qu'il faut pour transformer $x$ en $y$.

Distance minimale (8.3). Pour un code linéaire, c'est simplement le plus petit poids d'un mot de code non nul: pour le code (7,4), 15 poids à examiner au lieu de 120 paires.

Théorèmes 8.3 et 8.4 (relation (8.4)), et les deux bornes sont atteintes. La géométrie: la boule $B(x,t)$ compte

mots (8.5), et le décodage au plus proche voisin est correct si et seulement si les boules de rayon $t$ centrées sur les mots de code sont deux à deux disjointes, c'est-à-dire $d_{\min }\ge 2t+1$. D'où le facteur deux entre les deux théorèmes: détecter, c'est ne retomber sur aucun centre ($d_{\min }\ge w+1$); corriger, c'est rester dans le bon domaine. Les deux usages : un code de distance 3 corrige une erreur en détecte deux.

Erreur résiduelle du code de répétition de longueur $m$ impaire (8.6), décodé par vote majoritaire, de rendement $1/m$ et de distance minimale $m$. Développement en petit $p$: $q_3\approx 3p^2$, $q_5\approx 10p^3$ — chaque paire de copies supplémentaires gagne un ordre en , pour un prix . Pour descendre sous à , il faudrait dix-neuf copies de chaque bit.

Code de Hamming (7,4), convention du cours: les bits sont numérotés $b_1,\dots ,b_7$ de gauche à droite, les parités occupent les positions puissances de deux 1, 2, 4 et les données les positions 3, 5, 6, 7, dans l'ordre $(p_1,p_2,d_1,p_4,d_2,d_3,d_4)$.

Équations de parité (8.7): le contrôle $p_k$ porte sur les positions dont le numéro, écrit en binaire, a un 1 au poids $k$. Matrice génératrice (8.8), $\mathbf{c}=\mathbf{d}G$ sur $\mathrm{GF}(2)$:

Distribution des poids des 16 mots: un de poids 0, sept de poids 3, sept de poids 4, un de poids 7. Donc $d_{\min }=3$, $t=1$, $R=4/7\approx 0,5714$.

Syndrome (8.9) et théorème 8.5: le syndrome ne dépend que de l'erreur, il vaut 0 s'il n'y en a pas, et il vaut $j$ pour une erreur simple en position $j$. Inverser le bit $s$ corrige donc toute erreur simple, en temps constant, sans jamais comparer aux seize mots de code. Les 3 bits de syndrome offrent $2^3=8$ valeurs pour $7+1=8$ situations: rien n'est gaspillé, rien ne reste en réserve — et c'est exactement ce qui fait que le code est parfait, donc sans aucune marge face à une erreur double. Vérifications exhaustives: les $16\times 7=112$ erreurs simples sont toutes corrigées, et les erreurs doubles sont . Le code (8,4), obtenu en ajoutant une parité globale, porte à 4 et distingue les deux cas: c'est le principe des mémoires ECC, en général sous la forme (72,64).

Probabilité qu'un bloc de sept bits reçoive deux erreurs ou plus (8.10). Erreur résiduelle par bit de données, obtenue par énumération exhaustive des 128 motifs (8.11):

À $p=0,01$, le code de Hamming est $2,9$ fois moins fiable que la répétition 3 et $1,71$ fois plus rapide: pas de vainqueur absolu, un compromis. Et au-delà de $p\approx 0,211$, la courbe du code de Hamming passe au-dessus de celle du canal nu: en «corrigeant» des blocs qui portent presque toujours deux erreurs ou plus, le décodeur en ajoute plus qu'il n'en retire. Un code correcteur n'est pas une protection inconditionnelle.

Borne de Hamming, ou borne de l'empilement de sphères (théorème 8.6, relation (8.12)): les boules de rayon $t$ sont disjointes par l'inégalité triangulaire, et toutes contenues dans $\{0,1{\}}^n$. C'est un théorème d'impossibilité: aucun code $(10,5)$ ne corrige deux erreurs, puisque $32\times 56=1792>1024$; aucun code $(15,9)$ non plus, puisque . Un code est quand l'égalité est atteinte, c'est-à-dire quand les boules l'espace. Le code (7,4) l'est: . Toute la famille l'est: . Les répétitions aussi (; ), la répétition 4 non — c'est pourquoi on ne répète jamais un nombre pair de fois. La liste complète des codes binaires parfaits est connue (van Lint, Tietäväinen): les codes triviaux, les répétitions impaires, les codes de Hamming, et , le code de Golay . Les codes parfaits sont des accidents arithmétiques.

CRC: un bloc de bits est un polynôme sur $\mathrm{GF}(2)$, où l'addition est le OU exclusif et donc la soustraction aussi. On décale de $r$ zéros, on divise par le générateur $G$ de degré $r$, on transmet le message suivi du reste; le récepteur divise et accepte si le reste est nul. Comme $T+E\equiv E$, le contrôle ne voit encore une fois que l'erreur, et le CRC échoue exactement sur les multiples de $G$. Garanties: toute erreur simple si $G$ a au moins deux termes; toute erreur de poids impair si $(x+1)$ divise ; et , puisqu'une telle rafale s'écrit avec et que ne divise ni ni . Pour les rafales plus longues, sous l'hypothèse idéalisée d'un motif uniforme, il en passe une fraction , soit pour CRC-32. : il est trivialement falsifiable.

Capacité du canal binaire symétrique (8.13). L'interprétation est celle du chapitre 6: le canal détruit $H(Y\mid X)=H(p)$ bit par usage, et l'information mutuelle maximisée sur les lois d'entrée vaut $1-H(p)$. Valeurs: $C(0)=1$; $C(0,01)=0,9192$; ; ; ; ; , canal mort où la sortie est indépendante de l'entrée. Au-delà de la capacité remonte, puisqu'il suffit d'inverser tout ce que l'on reçoit.

Théorème du codage de canal (théorème 8.7, Shannon 1948, admis). Partie directe: pour tout $R<C$ et tout $\epsilon >0$, il existe une longueur de bloc à partir de laquelle un code de rendement au moins $R$ a une erreur de bloc inférieure à $\epsilon$. Réciproque: pour $R>C$, l'erreur est minorée par une constante strictement positive. C'est un seuil net: en dessous de $C$, la fiabilité parfaite s'obtient en allongeant les blocs et sans sacrifice de rendement supplémentaire; au-dessus, rien n'y fait. La démonstration est non constructive — elle tire un code au hasard et montre que la moyenne sur tous les codes tend vers 0 — et le code dont elle prouve l'existence serait inutilisable: stocker mots pour et demanderait entrées, très au-delà des atomes de l'univers observable. Ce qui manque est une : un code décrit par une règle courte et surtout en temps raisonnable.

L'écart se chiffre. À $p=0,01$, $C=0,9192$ alors que le code de Hamming (7,4) plafonne à $R=0,5714$ avec $8,7\cdot 10^{-4}$ d'erreur résiduelle, quand le théorème promet une erreur aussi petite qu'on veut à ce rendement; inversement, le rendement $4/7$ n'est fiable que tant que , soit . Chronologie: Golay et Hamming (1949–1950), Reed–Solomon (1960, sur des symboles, donc résistants aux rafales), LDPC de Gallager (1962, oubliés trente ans), turbocodes (1993), redécouverte des LDPC (1996), d'Arıkan (2008), les premiers dont on démontre qu'ils atteignent la capacité, en .

Chapitre 9 – Cryptographie et sécurité

Quatre objectifs distincts, dont aucun n'entraîne les autres: confidentialité (chiffrement), intégrité (empreintes et codes d'authentification), authenticité (signatures et protocoles), non-répudiation (signatures à clef publique et certificats). Un message chiffré peut être modifié sans être détecté; un message intègre peut venir de n'importe qui; une authenticité à clef partagée ne prouve rien devant un tiers, chacune des deux parties ayant pu fabriquer le message.

Principe de Kerckhoffs: la sécurité repose uniquement sur le secret de la clef, jamais sur celui de l'algorithme, supposé connu de l'adversaire — parce qu'un algorithme finit par être connu, ne se remplace pas comme une clef, n'est examiné que s'il est public, et parce que seule cette hypothèse rend la sécurité quantifiable. La sécurité par l'obscurité peut être une gêne supplémentaire, jamais la couche qui porte.

Chiffre de César (9.1) et chiffre de Vigenère (9.2). Le premier a 26 clefs, soit ${\log }_{2}26\approx 4,70$ bits. La substitution mono-alphabétique quelconque en a $26!\approx 4,03\cdot 10^{26}$, soit ${\log }_2(26!)=88,38$ bits — : un grand espace de clefs est une condition , jamais suffisante, et la substitution ne fait que renommer les barres de l'histogramme des fréquences. Le test du khi-deux sur les 26 déchiffrements tranche sans ambiguïté.

Indice de coïncidence (9.3): $1/26\approx 0,0385$ pour un texte aléatoire uniforme, $\approx 0,0734$ pour du français. Contre Vigenère, on découpe le chiffré en $\ell$ colonnes et l'on retient la plus petite valeur de $\ell$ pour laquelle l'indice moyen des colonnes remonte à celui du français, un multiple de la vraie longueur donnant le même effet; chaque colonne est alors un César. La faiblesse est la clef courte et répétée, pas la formule.

Secret parfait au sens de Shannon (9.4): observer le chiffré n'apprend rien, même avec un temps de calcul infini.

Masque jetable (9.5) et théorème 9.1: $\mathbb{P}(C=c\mid M=m)=\mathbb{P}(K=m\oplus c)=2^{-n}$, valeur qui ne dépend pas de $m$, d'où le résultat par Bayes. Tout clair de même longueur reste exactement aussi probable qu'avant l'interception.

Borne de Shannon (théorème 9.2): une clef ne peut pas être plus courte que le message qu'elle protège parfaitement. Le masque jetable ne résout donc pas la confidentialité, il la déplace vers la distribution des clefs sans la réduire d'un octet. Deux autres conditions, aussi contraignantes: la clef doit être véritablement aléatoire (la remplacer par un générateur pseudo-aléatoire de graine 128 bits ramène à la sécurité calculatoire du chiffrement par flot ainsi défini), et elle ne doit jamais servir deux fois:

Relation (9.6): la clef disparaît, et deux textes naturels superposés se séparent statistiquement. Si de plus un clair est connu, on retrouve $k$ puis tous les autres.

Sécurité calculatoire et AES. L'AES (Rijndael, concours public, FIPS 197, 2001) opère sur des blocs de 128 bits avec des clefs de 128, 192 ou 256 bits. Contre AES-128, la meilleure approche réaliste reste la recherche exhaustive: $2^{128}\approx 3,40\cdot 10^{38}$ clefs, soit $1,1\cdot 10^{13}$ années à $10^{18}$ essais par seconde, près de mille fois l'âge de l'univers; et , environ le millième du nombre d'atomes de l'univers observable (). Trois pièges indépendants de la force du chiffre: le (en ECB, deux blocs de clair identiques donnent deux chiffrés identiques et la structure du document transparaît), l' sans authentification ajoutée, et les — tailles, nombre, rythme, correspondants — qui traversent le chiffrement intactes.

Nombre de clefs symétriques pour $n$ correspondants deux à deux (9.7): 45 pour 10 personnes, $499500$ pour mille, près de $5\cdot 10^{11}$ pour un million — un coût en $\Theta (n^2)$ pour un nombre de participants en $\Theta (n)$. La cryptographie à clef publique ramène cela à $\Theta (n)$: chacun publie clef.

Petit théorème de Fermat (théorème 9.3, relation (9.8), $p$ premier ne divisant pas $a$) et théorème d'Euler (théorème 9.4, relation (9.10), $\gcd (a,n)=1$). Les deux se démontrent de la même façon: la multiplication par $a$ permute l'ensemble des classes inversibles, on multiplie le tout et l'on simplifie. L'exponentiation rapide par carrés successifs, lue de gauche à droite sur l'écriture binaire de l'exposant, coûte au plus $2{\log }_{2}k$ multiplications modulaires au lieu de $k-1$, et chaque produit reste borné par grâce à la réduction immédiate.

Indicatrice d'Euler (9.9). Point capital: calculer $\phi (n)$ à partir de $n$ seul revient à factoriser $n$, puisque $p+q=n-\phi (n)+1$ et $pq=n$ font de $p$ et les racines d'une équation du second degré. Sur la clef du cours: , , , soit 61 et 53.

Échange de Diffie-Hellman (1976). Alice et Bob conviennent publiquement de $p$ premier et de $g$; Alice publie $A=g^a\mathrm{mod}p$, Bob publie $B=g^b\mathrm{mod}p$, et tous deux calculent

Valeurs du cours: $p=227$, $g=2$ (racine primitive: l'ordre de 2 modulo 227 vaut bien $226=p-1$), $a=57$, $b=101$, d'où $A=15$, et le , qui n'a jamais transité — un observateur lit , , , et rien d'autre. L'adversaire passif doit résoudre le — «pas de bébé, pas de géant» demande de l'ordre de opérations , soit pour un de 2048 bits — ou le problème de Diffie-Hellman calculatoire, qu'on ne sait pas résoudre autrement sans avoir démontré l'équivalence.

Diffie-Hellman nu ne fournit aucune authentification et cède à l'intercepteur. Avec $m=73$, d'où $M=2^{73}\mathrm{mod}227=130$: Mallory substitue $M$ dans les deux sens, partage $130^{57}=15^{73}=18$ avec Alice et avec Bob, déchiffre, lit, modifie, rechiffre — . L'attaque n'exploite aucune faiblesse calculatoire (agrandir ne sert à rien) mais l'absence de lien entre une valeur et une identité; la parade est une signature vérifiée par certificat.

RSA (Rivest, Shamir, Adleman, 1978): choisir $p\ne q$ premiers, poser $n=pq$ et $\phi (n)=(p-1)(q-1)$, choisir $e$ avec , calculer tel que

relation (9.11), publier $(n,e)$, garder secrets $d$, $p$, $q$ et $\phi (n)$ — et si possible les détruire. Chiffrement $c=m^e\mathrm{mod}n$, déchiffrement $m=c^d\mathrm{mod}n$, pour .

Correction de RSA (théorème 9.5, relation (9.12)). On écrit $ed=1+k\phi (n)$. Si $\gcd (m,n)=1$, Euler conclut. Dans le cas général, on travaille modulo $p$ puis modulo $q$: ou bien $p\mid m$ et $m^{ed}\equiv 0\equiv m$, ou bien Fermat donne et ; de même modulo ; et , premiers distincts divisant , leur produit le divise aussi.

La clef jouet du cours, à utiliser telle quelle:

Chiffrement de $m=65$: les carrés successifs donnent $65^1=65$, $65^2=992$, $65^4=1232$, , modulo , puis , soit en 4 carrés et 1 multiplication — . Déchiffrement: , en 15 produits au lieu de (, 12 bits dont 5 à 1). : se factorise en essayant les premiers jusqu'à , alors qu'un module réel a au moins 2048 bits, soit plus de 600 chiffres décimaux.

Sur quoi repose la sécurité de RSA. Ce que l'on sait: aucun algorithme classique connu ne factorise en temps polynomial en le nombre de bits, le meilleur algorithme général publié est sous-exponentiel, et les records publics portent sur des modules de l'ordre de 800 bits — d'où les recommandations de 2048 bits au minimum, 3072 ou 4096 pour du long terme. Ce que l'on ne sait pas: il n'est pas démontré que factoriser soit difficile, ni que casser RSA exige de factoriser; la sécurité repose donc sur deux conjectures. La factorisation (version décision) est dans $\mathsf{NP}\cap \mathsf{coNP}$ et n'est pas connue $\mathsf{NP}$-complète, de sorte que même $\mathsf{P}\ne \mathsf{NP}$ ne fonderait pas RSA — la cryptographie a besoin de difficulté en moyenne, pas dans le pire cas. L'algorithme de Shor factorise en temps polynomial sur un calculateur quantique de taille suffisante, ce qui motive la cryptographie post-quantique. Enfin le RSA scolaire ne doit jamais être utilisé tel quel: déterministe et algébriquement manipulable, il exige un remplissage aléatoire normalisé; et comme il est lent, on s'en sert pour transporter une clef symétrique, jamais pour chiffrer des données.

Fonction de hachage cryptographique: une empreinte de $\nu$ bits, calculable rapidement, avec trois propriétés distinctes — résistance à la préimage (trouver $m$ tel que $h(m)=y$), à la seconde préimage ($m_2\ne m_1$ de même empreinte, subi) et aux (un couple quelconque, les deux messages choisis), la troisième étant strictement plus forte. Les collisions nécessairement, par le principe des tiroirs; ce qu'on demande est l'infaisabilité pratique.

Borne des anniversaires (théorème 9.6, relation (9.13)), avec $N=2^{\nu }$. Conséquence brutale: la résistance aux collisions d'une empreinte de $\nu$ bits ne vaut que $2^{\nu /2}$. Une empreinte de 64 bits cède à $4,3$ milliards d'essais; 128 bits n'en offrent qu'environ 64 (${\log }_{2}k\approx 64,24$); 160 bits en offrent 80; SHA-256 en offre 128, le même ordre qu'une clef AES-128. : changer un caractère change environ la moitié des bits — sur les deux phrases du cours, 121 bits sur 256, soit .

Usages. Intégrité: comparer $h(m)$ à une référence authentique — une empreinte publiée sur la même page que le fichier ne protège que contre les erreurs de transmission. Mots de passe: on stocke l'empreinte, avec un sel distinct par utilisateur (deux mots de passe identiques donnent alors deux empreintes différentes, et les tables précalculées deviennent inutiles) et une fonction délibérément lente — une fonction rapide est une qualité pour l'intégrité et un défaut pour les mots de passe. Signatures: on signe l'empreinte, jamais le message.

Signature numérique, qui exploite la symétrie $(m^d{)}^e=m^{de}=m^{ed}=(m^e{)}^d$. On signe l'empreinte pour deux raisons: un message plus long que le module ne peut pas être élevé à une puissance en une fois, et une exponentiation sur 2048 bits est bien plus lente qu'un hachage. Une signature valide prouve choses: l'intégrité, le fait que le signataire détenait la clef privée associée à , et la (contrairement à un code d'authentification à clef partagée, que les deux parties peuvent fabriquer). Elle dit qui est le signataire — c'est le rôle du et de la chaîne d'autorités —, ni (il faut un horodatage), ni que la clef n'a pas été volée (d'où révocation, durée de validité, stockage matériel), ni que le signataire a compris ce qu'il signait.

Là où les systèmes cassent vraiment, et ce n'est presque jamais la cryptanalyse: les clefs (générateur faible, clef dans un dépôt de code, jamais renouvelée), les implémentations (canal auxiliaire par le temps ou la consommation, erreur mémoire, bibliothèque obsolète), les protocoles (composition non sûre de briques sûres, négociation vers une version affaiblie, message d'erreur qui renseigne l'adversaire), les personnes. La question utile n'est presque jamais «quel algorithme?» mais «d'où vient cette clef, qui y a accès, comment sait-on que cette clef publique est la bonne, et que se passe-t-il quand quelque chose échoue?».

Chapitre 10 – Réseaux et communication

Commutation de circuits: on réserve à l'avance une part fixe de capacité sur chaque lien, garantie et inutilisable par les autres, la communication étant refusée si la réservation ne peut être honorée. Commutation de paquets: aucune réservation, le message est découpé en paquets portant chacun l'adresse de destination, transmis quand le lien est libre et mis en file sinon, sans aucun état par communication. Sur un lien de 1 Mb/s desservant des usagers à 100 kb/s actifs 10 % du temps (hypothèse de travail, pas une mesure), le circuit admet 10 usagers; le paquet en admet 35, saturé avec la probabilité $\mathbb{P}(X\ge 11)=4,24\cdot 10^{-4}$ pour $X\sim \mathcal{B}(35;0,1)$, soit du temps. — et l'hypothèse d'indépendance est fausse dès qu'un événement synchronise les usagers. Prix des paquets: (la gigue), (une file finie déborde, et c'est le mode normal de signalisation de la saturation), . Le réseau a été rendu simple et non fiable pour pouvoir être grand, la fiabilité étant repoussée aux extrémités.