Corps fini - Définition
La liste des auteurs de cet article est disponible ici.
Applications
Équation diophantienne
Une équation diophantienne est une équation à coefficients entiers où des solutions entières sont recherchées. Pierre de Fermat s'est longuement penché sur des équations de cette nature.
Le petit théorème de Fermat stipule que, si p est premier, alors tout entier à la puissance p est congru modulo p à cet entier. Dans le contexte des corps finis, cela revient à indiquer que les points fixes de l'automorphisme de Frobenius sont les éléments du corps premier, ou que le groupe multiplicatif de ce dernier est cyclique d'ordre p - 1.
Fermat remarque que les seuls nombres premiers, somme de deux carrés, sont ceux dont la division par quatre donne un pour reste. Il remarque en effet que:
Il propose l'équation suivante a 2 + b 2 = p avec p premier dans une lettre écrite à Marin Mersenne, datée du 25 décembre 1640.
Richard Dedekind propose une démonstration dont la première partie consiste à étudier l'équation sur le corps Fp. Il utilise les propriétés du groupe multiplicatif et celles des polynômes à coefficients dans un corps. L'équation devient a 2 + b 2 = 0. Si b est égal à 0 alors a l'est aussi et la solution est triviale. Dans le cas contraire. Il est possible de diviser par b car la structure sous-jacente est celle d'un corps, l'équation devient alors X 2 + 1 = 0. En multipliant le polynôme précédent par X 2 - 1 = 0, il obtient l'équation suivante : X 4 - 1 = 0. Les propriétés du groupe multiplicatif donne une condition nécessaire et suffisante sur p, il doit être congru à un modulo quatre. La fin de la démonstration n'utilise pas les corps finis, elle est donnée dans l'article associé.
Cette méthode, consistant à réduire l'équation dans le corps premier est fréquente. Le corps dispose d'une structure plus forte et de nombreux théorèmes pour conclure.
Code correcteur
Les codes correcteurs ont leur source dans un problème très concret lié à la transmission de données. Dans certains cas, une transmission de données se fait en utilisant une voie de communication qui n'est pas entièrement fiable. Autrement dit, les données, lorsqu'elles circulent sur cette voie, sont susceptible d'être altérées. L'objectif d'un code correcteur est l'apport d'une redondance de l'information de telle manière à ce que l'erreur puisse être détectée et même corrigée.
Un message est une suite finie de lettres, qui dans le cas d'un code linéaire sont considérées comme des éléments d'un corps fini. Un message m apparaît comme un élément d'un espace vectoriel E sur un corps fini de dimension k. L'apport de la redondance est le résultat d'une application linéaire injective φ de E dans un espace F appelé code et de dimension n supérieur à k. Le mot du code transmis est l'élément φ(m). L'intérêt de transmettre φ(m) à la place de m est illustré par la figure suivante :
Si le message m est transmis, et si la transmission l'altère, alors le message reçu est erroné (comme illustré sur la figure de gauche) et le récepteur ne dispose d'aucun moyen pour repérer ou corriger l'erreur. Si l'application φ est astucieusement choisie, chaque point du code diffère des autres points du code par au moins d coordonnées. Cette situation est illustrée sur la figure de droite. Les points du code sont illustrés en vert, la modification d'une coordonnée est symbolisée par un segment du quadrillage. On remarque sur la figure que les points du code diffèrent tous par au moins d = 3 coordonnées. Si, par exemple, l'altération porte sur une unique coordonnée, la transmission correspond à un point rouge. Le récepteur peut alors corriger l'erreur, car il n'existe qu'un seul point du code (en vert) à une distance de 1 du message reçu.
L'application qui, à deux points de F, associe le nombre de coordonnées distinctes est une distance au sens mathématique, appelée distance de Hamming. Si la distance de Hamming minimale entre deux points du code est égale à d, alors le code est à même de corriger t altérations où t est le plus grand entier strictement plus petit que d/2. Sur la figure ci-dessus, on remarque des points noirs. Ils correspondent à des redondances inutiles. Ils sont en effet à une distance de deux des points du code, or une telle distance n'est pas traitable dans le cas de la figure.
L'ensemble des points corrigeables est donné par la réunion de toutes les boules de centre un point du code et de rayon t. La configuration idéale est celle où ces boules forment une partition de F. Il n'existe alors aucune redondance inutile. Cette situation est illustrée par la figure de droite. Les points du code sont illustrés en vert, la distance minimale d est égale à 5. Les boules de centre les points du code et de rayon 2 forment une partition de F. Les points à distance 1 du code sont illustrés en bleu, ceux à distance 2 en rouge. Tout message contenant au plus deux altérations peut être corrigé. Un tel code est dit parfait.
La théorie des corps finis permet de construire des codes parfaits. L'espace F est muni de la structure d'anneau Fd[X]/P(X) où P(X) = Xn - 1 avec n = d a - 1 et a est un entier strictement positif. F correspond à l'ensemble des polynômes prenant des valeurs distinctes sur le corps Fn+1. Si φ(E) est l'idéal engendré par le polynôme G(X) à coefficients dans Fd ayant pour racines α, α2, ..., αd-1, alors le code est de distance minimale d. G(X) est le produit de polynômes cyclotomiques. Le code BCH ou le code de Reed-Solomon utilise cette technique pour construire des codes parfaits. Si k est l'entier tel que n - k est égal au degré de G(X), alors l'application φ associe au message M(X) le polynôme M(X).Xk - R(X) où R(X) est le reste de la division euclidienne de M(X).Xk par G(X). Les détails et démonstrations sont donnés dans l'article code cyclique.
