Corps fini

Wikipédia:Bons articles Vous lisez un «  bon article ».
Les défauts de gravure, l'usure, la poussière que l'on observe à la surface d'un disque compact nécessitent un codage redondant de l'information, qui permet de corriger les erreurs de lecture. Ce code correcteur d'erreur utilise des codes de Reed-Solomon sur le corps fini à 256 éléments [1].

En mathématiques et plus précisément en algèbre, un corps fini est un corps commutatif qui est par ailleurs fini. À isomorphisme près, un corps fini est entièrement déterminé par son cardinal, qui est toujours une puissance d'un nombre premier, ce nombre premier étant sa caractéristique. Pour tout nombre premier p et tout entier non nul n, il existe un corps de cardinal pn, qui se présente comme l'unique extension de degré n du corps premier Z/pZ.

Les corps finis sont utilisés en théorie algébrique des nombres, où ils apparaissent comme une structure essentielle à la géométrie arithmétique. Cette branche a permis, entre autres, de démontrer le dernier théorème de Fermat.

Les corps finis ont trouvé de nouvelles applications avec le développement de l' informatique. En théorie des codes, ils permettent par exemple de déterminer des codes correcteurs efficaces. Ils interviennent également en cryptographie, dans la conception des chiffrements à clé secrète comme le standard AES, ainsi que dans celle des chiffrement à clé publique, à travers, entre autres, le problème du logarithme discret.

Remarque sur la terminologie : une convention courante en français est de considérer qu'un corps n'est pas nécessairement commutatif. Dans le cas des corps finis, la convention est en fait de peu d'importance car, d'après le théorème de Wedderburn, tout corps fini est commutatif, et, dans cet article les corps seront supposés d'emblée commutatifs.

Les corps finis sont (ou ont été) appelés également corps de Galois, ou plus rarement champs de Galois [2]. Ils ont été en effet étudiés par Évariste Galois dans un article publié en 1830 qui est à l'origine de la théorie. En fait, Carl Friedrich Gauss avait déjà découvert les résultats de Galois à la fin du XVIIIe siècle mais n'en fit pas état ; ses travaux ne furent connus qu'après sa mort et n'eurent pas l'influence de ceux de Galois.

Le corps fini de cardinal q (nécessairement puissance d'un nombre premier) est noté Fq (de l'anglais field qui signifie corps commutatif) ou GF(q) (Galois field).

Construction de corps finis

L'outil qui permet la construction des corps finis est la relation de congruence, congruence sur les entiers pour les corps finis premiers, congruence sur les polynômes à coefficients dans un corps fini premier pour le cas général.

Le plus petit corps

Le plus petit corps fini est noté F2. Il est composé de deux éléments distincts, 0 qui est l'élément neutre pour l'addition, et 1 qui est élément neutre pour la multiplication. Ceci détermine les tables de ces deux opérations en dehors de 1+1 qui ne peut alors être que 0, car 1 doit avoir un opposé. On vérifie alors qu'elles définissent bien un corps commutatif.

+ 0 1
0 0 1
1 1 0
. 0 1
0 0 0
1 0 1

Le corps F2 peut s'interpréter diversement. C'est l' anneau Z/2Z, les entiers pris modulo 2, c'est-à-dire que 0 représente les entiers pairs, 1 les entiers impairs (c'est le reste de leur division par 2), et les opérations se déduisent de celles sur Z.

C'est aussi l'ensemble des valeurs de vérité classiques, 0 pour le faux, et 1 pour le vrai. L'addition est le « ou exclusif » (xor), la multiplication le « et » [3].

Les fonctions de (F2)n dans F2 sont appelées fonctions booléennes [4]. La disjonction (inclusive) et la négation se définissent ainsi :

x ou y = x + y + xy ; non x = 1 + x.

Plus généralement on déduit du théorème d'interpolation de Lagrange que toutes les fonctions booléennes sont polynomiales (c'est une propriété qui passe à n'importe quel corps fini).

Article détaillé : fonction booléenne.

Corps premiers finis

Une généralisation naturelle de F2 = Z/2Z est, pour p premier, le corps Z/pZ à p éléments, noté aussi Fp :

Proposition. — L' anneau Z/nZ est un corps si et seulement si n est un nombre premier.

En effet, p est premier équivaut à ce que 0 ne soit pas produit de deux entiers non nuls modulo p, par le lemme d'Euclide. Il faut donc que p soit premier pour que Z/pZ soit un corps. De plus, ceci assure que si p est premier, Z/pZ est intègre et partant, comme il est fini, un corps. L' identité de Bézout assure directement l'existence d'un inverse, et un calcul efficace de celui-ci par l' algorithme d'Euclide étendu.

Le groupe multiplicatif de Z/pZ (p premier) est d'ordre p – 1 ce qui conduit au petit théorème de Fermat par le théorème de Lagrange. On montre que ce groupe est cyclique (la démonstration est la même que dans le cas général, traité au paragraphe Groupe multiplicatif et conséquences) [5].

On verra que pour tout nombre premier p, Z/pZ est à isomorphisme près le seul corps de cardinal p, et qu'il ne contient pas d'autre sous-corps que lui-même. Un tel corps est appelé corps premier, et les Z/pZ, p premier, sont les seuls corps premiers finis.

Articles détaillés : Congruence sur les entiers et Anneau ℤ/nℤ.

Quotient par un polynôme irréductible

Pour construire de nouveaux corps finis, on utilise la structure d' anneau euclidien de Fp[X] de la même façon que l'on a utilisé celle de Z pour construire les corps premiers. Les polynômes irréductibles jouent le rôle des nombres premiers. Deux polynômes sont équivalents modulo le polynôme P s'ils ont même reste par division par celui-ci. Le quotient par la relation d'équivalence obtenue est noté Fp[X]/(P), la structure induite par quotient est encore celle d'un anneau [6].

On a de façon strictement analogue au cas des entiers :

Proposition. — L'anneau Fp[X]/(P) est un corps si et seulement si P est un polynôme irréductible.

Soit n le degré de P. La propriété d'unicité du reste de la division polynomiale se traduit par le fait que chaque élément de Fp[X]/(P) est représenté par un unique polynôme de degré < n. Le cardinal de Fp[X]/(P) est donc pn. Pour construire un corps fini de cardinal pn, il suffit donc de trouver un polynôme irréductible de degré n dans Fp[X].

Si P est irréductible, le quotient K = Fp[X]/(P) est alors un corps de rupture du polynôme P, car la classe de X est une racine de P dans K.

Pour ces constructions il est indispensable que les polynômes soient des polynômes formels, et non des fonctions polynômes. Il existe en effet des polynômes non-nuls dont les fonctions polynômes associées sont identiquement nulles sur Fp (par exemple X + X2 sur F2). Une autre manière de se rendre compte de la différence est qu'il ne peut exister qu'un nombre fini de fonctions de Fp dans Fp et donc de fonctions polynômes, alors qu'il existe un nombre infini de polynômes formels.

Exemple : les corps à p2 éléments

On peut donc construire les corps à p2 éléments, en montrant qu'il existe un polynôme irréductible P de degré 2 dans Fp[X]. Le corps Fp[X]/(P), possède p2 éléments, et c'est une extension quadratique de Fp. On verra plus loin que le corps à p2 éléments est unique (à isomorphisme près) et on le notera Fp2. En particulier, le corps que nous allons construire est en fait indépendant du choix du polynôme irréductible P de degré 2 utilisé pour le quotient. Cette extension quadratique de Fp est l'analogue de l' (unique) extension quadratique du corps des nombres réels, qui donne le corps des nombres complexes.

  • Pour p = 2, le polynôme 1 + X + X2 est irréductible dans F2[X] (c'est d'ailleurs le seul polynôme irréductible de degré 2 sur F2). L'extension correspondante est un corps noté F4. Ce corps a exactement 4 éléments qui sont 0, 1, et les deux racines x et x + 1 de 1 + X + X2. Ses lois sont alors :
+ 0 1 x x+1
0 0 1 x x+1
1 1 0 x+1 x
x x x+1 0 1
x+1 x+1 x 1 0
. 0 1 x x+1
0   0   0 0 0
1 0 1 x x+1
x 0 x x+1 1
x+1 0 x+1 1 x

Le groupe multiplicatif des inversibles de F4* est engendré par les puissances de la classe de x : x2 = x + 1, x3 = 1. La table de multiplication est facile à écrire en termes de ce groupe cyclique, mais c'est alors l'addition qui est moins commode.

  • Quand p est premier impair, un polynôme de la forme X2a est irréductible si et seulement si a n'est pas un carré. Or pour p différent de 2, il existe dans Fp des éléments non carrés. En effet, les carrés des p – 1 éléments non nuls de Fp sont au nombre de (p – 1)/2 (chaque carré non nul est le carré d'exactement deux éléments, opposés l'un de l'autre), donc il reste (p – 1)/2 éléments non carrés, parmi lesquels on peut choisir a. Pour p congru à 3 modulo 4, on peut même choisir simplement a = -1 (voir l'article Théorème des deux carrés de Fermat ou l'article Loi de réciprocité quadratique), si bien que Fp2 est isomorphe à Z [ i ] / (p).
Other Languages
العربية: حقل منته
беларуская: Канечнае поле
български: Крайно поле
català: Cos finit
English: Finite field
español: Cuerpo finito
עברית: שדה סופי
italiano: Campo finito
日本語: 有限体
한국어: 유한체
português: Corpo finito
română: Corp finit
Simple English: Galois field
српски / srpski: Коначно поље
svenska: Ändlig kropp
Türkçe: Sonlu alan
українська: Поле Галуа
中文: 有限域
粵語: 有限體