TRAVAUX PRATIQUES
TP.XV. Racines de l’unité dans un corps fini
et codes BCH
On se propose, dans ce TP, de passer en revue la théorie des polynômes cyclotomiques sur un corps fini F q . Comme application, on génère des codes BCH
construits, par définition, à partir des polynômes minimaux de puissances d’une
racine primitive de l’unité sur F q . Puis l’on offre une initiation à la théorie des
codes correcteurs d’erreurs : on expose comment coder et décoder un message
dans le cas des codes BCH (ne pas confondre avec la cryptographie dont le propos est d’envoyer un message secret que seul le destinataire puisse décoder) et
l’on teste expérimentalement la capacité de correction du code et la puissance de
l’algorithme de décodage (une variante de l’algorithme d’Euclide étendu, due à
Berlekamp et Massey). Ces méthodes sont fondamentales dans les technologies de
transmission de l’information, d’où de multiples applications dans l’industrie.
Racines de l’unité et polynômes cyclotomiques sur un corps fini F q
Les polynômes cyclotomiques sont, par définition, les
Φ n (x) =
ζ∈Pn
(x − ζ),
où P n ⊂ C désigne l’ensemble des racines primitive n-ièmes de l’unité, constitué
des ζ k = e
2ikπ
n , pgcd(k, n) = 1. Il y en a ϕ(n), où l’on a noté ϕ la fonction
indicatrice d’Euler. La relation
x
n
− 1 =
d|n
Φ d (x)
(XV.1)
permet de calculer les Φ d par récurrence et montre que ces derniers sont à coefficients entiers. On démontre que les Φ d sont irréductibles dans Z[x] en réduisant
TP.XV. Racines de l’unité dans un corps fini
et codes BCH
On se propose, dans ce TP, de passer en revue la théorie des polynômes cyclotomiques sur un corps fini F q . Comme application, on génère des codes BCH
construits, par définition, à partir des polynômes minimaux de puissances d’une
racine primitive de l’unité sur F q . Puis l’on offre une initiation à la théorie des
codes correcteurs d’erreurs : on expose comment coder et décoder un message
dans le cas des codes BCH (ne pas confondre avec la cryptographie dont le propos est d’envoyer un message secret que seul le destinataire puisse décoder) et
l’on teste expérimentalement la capacité de correction du code et la puissance de
l’algorithme de décodage (une variante de l’algorithme d’Euclide étendu, due à
Berlekamp et Massey). Ces méthodes sont fondamentales dans les technologies de
transmission de l’information, d’où de multiples applications dans l’industrie.
Racines de l’unité et polynômes cyclotomiques sur un corps fini F q
Les polynômes cyclotomiques sont, par définition, les
Φ n (x) =
ζ∈Pn
(x − ζ),
où P n ⊂ C désigne l’ensemble des racines primitive n-ièmes de l’unité, constitué
des ζ k = e
2ikπ
n , pgcd(k, n) = 1. Il y en a ϕ(n), où l’on a noté ϕ la fonction
indicatrice d’Euler. La relation
x
n
− 1 =
d|n
Φ d (x)
(XV.1)
permet de calculer les Φ d par récurrence et montre que ces derniers sont à coefficients entiers. On démontre que les Φ d sont irréductibles dans Z[x] en réduisant