--------------------------------------------------------------------- page 47 : juste après le deuxième exemple, les coefficients de Bézout sont mauvais, il faut lire : 46 x 522 - 53 x 453 = 3, d'où d=3, x=46 et y=-53 alors que -151 x 522 + 174 x 453 = 0 --------------------------------------------------------------------- page 50 : dans l'énoncé du théorème chinois l'inégalité est stricte : il existe une unique solution $0 \leq x < N$. --------------------------------------------------------------------- page 56 : Algorithme 6, "probablement premier" et "composé" ainsi que "!=" et "=" ont été inversés. Il faut lire : Entrée : Un entier $n\ge 4$. Sortie : Soit $n$ est composé, soit il est probablement premier. Soient $s$ et $t$ tels que $n-1=t2^s$ Soit $a$ un nombre entier aléatoire entre $0$ et $n-1$. Soit $q \leftarrow a^t\mod n$ Si {$q=1$ ou $q=n-1$} Renvoyer "$n$ est probablement premier" Appliquer $s$ fois $q\leftarrow q*q\mod n$, et à chaque étape Si {$q=n-1$} Renvoyer "$n$ est probablement premier" Renvoyer "$n$ est composé". --------------------------------------------------------------------- Page 61 : Preuve de la proposition 1, le paragraphe Réciproquement doit être remplacé par : Réciproquement, soit $P$ un diviseur irréductible de $X^{p^d}-X$ de degré $r$. Alors on a $X^{p^d}=X \mod P$. Maintenant, soit $G(X)=\sum a_i X^i$ d'ordre maximal $p^r -1$ dans le groupe des inversibles du corps $\F_p[X]/P$ (il en existe toujours au moins un, voir page 68). On applique alors l'équation (1.8), $d$ fois, pour obtenir $G^{p^d} = \sum a_i (X^{p^d})^i \mod p$. Or $X^{p^d}=X \mod P$, et donc $G^{p^d}=G \mod P$, ou encore $G^{p^d-1}=1 \mod P$. Ainsi, $p^d-1$ est forcément un multiple de $p^r-1$, l'ordre de $G$. Le lemme permet de conclure que $r$ divise bien $s$. --------------------------------------------------------------------- Pages 94 et 95 : définition du polynôme Pi, les indices et les signes des coefficients du polynôme sont inversés. Il faut lire : $\Pi(X)=\Pi_dX^d+\Pi_{d-1}X^{d-1}+\Pi_{d-2}X^{d-2}+...+\Pi_0$. Page 95 : Algorithme 13, ligne 13, dans le deuxième "Sinon", le polynôme Pi a été écrasé à la ligne précédente, ce qui n'est pas correct. Il faut donc introduire un polynôme temporaire pour faire le calcul : Sinon temp <-- Pi - d/b X^e Psi Psi <-- Pi Pi <-- temp ... Ligne 19, le "Retourner Pi(X)" doit etre en dehors de la boucle Pour, c'est-à-dire après le "Fin Pour". --------------------------------------------------------------------- Page 100 : Algorithme 15, ligne 6, dans le "Tant que", il faut lire : Tant que (p == 1) Faire --------------------------------------------------------------------- Page 127 : le code du fax, les "Terminating White Codes" sont les nombres compris entre 0 et 63. [...] contient le code de tous les nombres entre 0 et 63. [...] il existe un grand nombre m dans la table, tel que 0<= n-m < 64 [...] Les nombres compris entre 0 et 63 sont appel~s Terminating White Codes --------------------------------------------------------------------- Page 103 : Algorithme 16, ligne 3, la première parenthèse est mal placée, il faut lire : Calculer $l \leftarrow 2(s^{r-2} \mod r)s-1$. --------------------------------------------------------------------- Page 139 : avant dernière ligne, il faut lire : [...] une matrice contenant les hautes fréquences en BAS à droite et les basses fréquences en HAUT à gauche. --------------------------------------------------------------------- Page 168 : la troisième ligne est fausse : [...] La S-box de l'AES possède en fait un point fixe inverse : S(73) = 8F ; S(8F) = 73 --------------------------------------------------------------------- Page 257 : Preuve du corollaire 5 Page 96 : avant dernière ligne La complexité de l'algorithme d'Euclide pour le pgcd de polynôme est O(r log²(r) ) et non O(r log(r) ). --------------------------------------------------------------------- Page 280 : Exercice 1.8, il faut lire: On trouve une entropie de 0,46899 (à comparer avec l'entropie de la source équiprobable 1). --------------------------------------------------------------------- Page 282 : Exercice 1.14, dernière ligne un signe - est manquant : Soit, y=44-45.2 mod 55 = -46 mod 55 = 9 mod 55. --------------------------------------------------------------------- Page 282 : Exercice 1.16, 1., la preuve doit être remplacée par : Le seul diviseur premier de $p^k$ est $p$. Donc les nombres non premiers avec $p^k$ sont les multiples de $p$. Ces nombres sont de la forme $ap$ avec $1 \leq a < p^{k-1}$. Il y en a donc $p^{k-1}-1$ et on en conclut que $\varphi(p^k) = (p^k -1) - (p^{k-1} -1)$ $ =p^k - p^{k-1} = (p-1)p^{k-1}$. --------------------------------------------------------------------- Page 290 : Solution de l'exercice 2.4, 1. et 2., il faut lire : 1. H(dé non pipé)=$log_2(6) \approx 2.5850$ ; Pour celui-ci : $2.5611$. 2. (et toujours plus que $log_2(6)/log_2(3) \approx 1.5850$) --------------------------------------------------------------------- Page 318 : Solution de l'exercice 4.13, les phrases sont dans le désordre, il faut lire : On suppose donc les mots de $C$ stockés dans un tableau $C[1..|V|^k]$. Chaque mot $C[i]$ est un tableau $[1..k+r]$ de chiffres de $V$. On peut alors calculer la distance minimale entre deux mots de code quelconques. En les énumérant, il y a $|V|^k$ mots qui sont codés avec $n=k+r$ chiffres. Pour calculer la distance on effectue le calcul de la distance entre tous les couples possibles de mots. L'algorithme 36, page 320, nécessite alors $O(\frac{|V|^{k}\cdot(|V|^k+1)}{2})$ comparaisons. Chaque comparaison s'effectue sur $n=k+r$ bits et le coût total de l'algorithme est donc en $O(n\cdot |V|^{2k})$, ce qui est impraticable pour $|V|=2$ dès que $k$ et $n$ sont plus grands que 15. --------------------------------------------------------------------- Page 329 : Exercice C.1, 1. (b) iv, la matrice n'a pas 248 lignes : Le code est (255,249,7). La matrice génératrice a 249 lignes et 255 colonnes. Elle s'écrit sous la forme g_6 & g_5 & ... & g_0 & 0 & ... & ... & 0 0 & g_6 & g_5 & ... & g_0 & 0 & ... & 0 0 & 0 & g_6 & ... --------------------------------------------------------------------- Merci à : Eric Bourre, Rodney Coleman, Mélanie Favre, Françoise Jung, Madeline Lambert, Marie-Aude Steineur, Antoine Taveneaux, Romain Xu.