Accueil > Mots > Combinatoire > Corps finis

Corps finis – Corps de Galois GF(pn)

La page Carrés gréco-latins utilise les corps finis.

Description

Les corps finis ont $p^n$ éléments, où $p$ est un entier naturel premier et $n$ un naturel $n$ > $0$.
Deux corps finis qui ont même nombre d'éléments sont isomorphes. Lorsque $n=1$ le nombre d'éléments est le nombre premier $p$ et dans ce cas le corps $GF(p)$ est isomorphe à $(\Mathbb{Z}_p, +, \times)$, corps des classes résiduelles modulo $p$. L'exemple ci-dessous est celui des restes modulo $p$.

Tables de Fp = GF(p) où p est premier

Corps $GF(p)$ avec $p=$
$+$01234
0$0$$1$$2$$3$$4$
1$1$$2$$3$$4$$0$
2$2$$3$$4$$0$$1$
3$3$$4$$0$$1$$2$
4$4$$0$$1$$2$$3$
$.$01234
0$0$$0$$0$$0$$0$
1$0$$1$$2$$3$$4$
2$0$$2$$4$$1$$3$
3$0$$3$$1$$4$$2$
4$0$$4$$3$$2$$1$

Structure de corps

$.$1234
1$1$$2$$3$$4$
2$2$$4$$1$$3$
3$3$$1$$4$$2$
4$4$$3$$2$$1$
$GF(p^n)$ a une structure de groupe commutatif pour l'addition $+$.
(Comme on peut le voir dans l'exemple ci-dessus, le groupe $GF(p)$ est cyclique lorsque $n=1$, mais cette propriété n'est pas vraie dans le cas général $GF(p^n)$).

L'élément neutre $0$ de l'addition est un élément absorbant pour la multiplication $ \forall x, x \times 0 = 0$
L'ensemble des éléments non nuls a une structure de groupe commutatif dont l'élément neutre est $1$.

Dans tous les cas, le groupe multiplicatif des éléments non nuls de $GF(p^n)$ est un groupe cyclique.
En ordonnant convenablement les éléments de la table du groupe multiplicatif de $GF(p)$, on met en évidence cette propriété de cyclicité.
$.$1243
1$1$$2$$4$$3$
2$2$$4$$3$$1$
4$4$$3$$1$$2$
3$3$$1$$2$$4$

(Pour $p>3$ on peut mettre en évidence cette propriété en ordonnant différemment les éléments).

Tables Fpn = GF(pn) où p est premier et n ≥ 1

L'application utilise des polynômes primitifs précalculés pour construire le corps $GF(p^n)$.
Pour ces polynômes irréductibles de degré $n$ sur le corps $F_p$, le polynôme $x$ est un élément irréductible, (par exemple $1 + x+ x^3$ est irréductible de degré 3, sur $F_2$ et $x^3 = 1 + x$ ).
Les éléments non nuls du corps sont les $x^k$ pour $0\leq k \leq p^n-2$, (on voit ainsi que le groupe multiplicatif est cyclique). À chaque $x^k$ correspond un polynôme de degré strictement inférieur à $n$, l'application ci-dessous donne dans un tableau ces correspondances.
Les éléments du sous-corps isomorphe à $F_p$ sont coloriés en vert, (c'est le cas de tous les éléments lorsque vous calculez $F_{p^1} = GF(p^1)$, mais la numérotation des éléments n'est pas celle de $\mathbb Z_p$, la correspondance est donnée dans la table).

L'application ci-dessous calculera le corps chaque fois qu'un polynôme primitif sera connu. Pour un calcul rapide et un résultat peu encombrant, évitez que $p^n$ ne dépasse la centaine ou à peine plus.

Vous pouvez télécharger un fichier contenant une liste de polynômes, (chaque ligne est de la forme $p$ $n$ suivis des coefficients). La page Primpoly de Wims vous fournira aussi tous les polynômes dont vous pourriez avoir besoin.

En cliquant sur [Calcule] le calcul utilisera le polynôme prédéfini correspondant aux valeurs de $p$ et de $n$.

Si vous préférez utiliser un polynôme particulier, inscrivez ses coefficients dans l'ordre croissant des degrés des monômes (par exemple le polynôme $2+x+x^2$ a pour coefficients 2 1 1) puis cliquez sur [Avec polynôme] .
Le polynôme que vous donnerez sera analysé, veillez à ce que ses coefficients soient inférieurs à $p$, vérifiez que son degré est $n$, que le coefficient de $x^n$ est bien $1$ et que le polynôme est primitif, (sinon essayez de modifier un ou plusieurs coefficients).

$ p = $ et $ n = $      

Si vous désirez proposer un polynôme primitif particulier, donnez les coefficients dans l'ordre croissant des degrés, par exemple 2 1 1 pour $2+X+X^2$
Coefficients :   


Polynômes primitifs

Rappel : on a l'entier $p$ est premier, l'exposant entier $n\ge 1$ de $p^n$, le corps $\displaystyle F_{p^n}=GF(p^n)$. Il existe dans $\displaystyle F_p[X]$, des polynômes $P(X)$ de degré $n$ à coefficients dans $\displaystyle F_p$, irréductibles, tels que $X$ soit d'ordre $\displaystyle p^n-1$ dans le groupe multiplicatif $\displaystyle F_p[X]/P$.

Les polynômes $\displaystyle P$ sont des diviseurs $n$ dans $\displaystyle F_p[X]$ de {p^n}-X$ et pour tout $k \lt p^n$ ne sont pas des diviseurs de $X^k-X$.
Dit autrement, ce sont les facteurs de degrés $n$, dans $\displaystyle F_{p}[X]$, du $\displaystyle p^n-1$-ième polynôme cyclotomique $\displaystyle \Phi_{p^n-1}(X)$.

Le nombre de ces polynômes primitifs est $\displaystyle \frac{\phi(p^n-1)} n$. Pour le connaître, complétez ci-dessous :

$p=$  $n=$ 


Les polynômes cyclotomiques jusqu'à $\Phi_{50}(X)$ sont écrits sur la page du site Polynômes cyclotomiques. Un fichier texte contenant ces polynômes jusqu'à à $\Phi_{500}(X)$ est disponible sur le site en cliquant ici : Fichier des polynômes cyclotomiques.

Exemple 1 : $p=2$, $n=4$, $p^n=16$.
Dans $\mathbb Q[X]$ on a la factorisation
$\displaystyle X^{16}-X = $ $X\times(X-1)$ $(X^2 + X+ 1)$ $(X^4+X^3+X^2+X+1)$ $(X^8-X^7+X^5-X^4+X^3-X+1)$,
comme $15=3\times 5$, on reconnaît les polynômes cyclotomiques $\Phi_3(X)=X^2+X+1$, $\displaystyle \Phi_5(X)=X^4+X^3+X^2+X+1$, (faciles à retrouver car $3$ et $5$ sont premiers), et enfin $\displaystyle \Phi_{15}=X^8 - X^7 + X^5 - X^4 + X^3 - X + 1$, (que l'on peut retrouver en divisant $\displaystyle X^{16} -X$ par $X$, $\displaystyle \Phi_1(x)=X-1$, $\displaystyle \Phi_3(x)$ et $\displaystyle \Phi_5(X)$).

Dans $\displaystyle F_2[X]$, le polynôme $\displaystyle \Phi_{15}(X)$ s'écrit $\displaystyle X^8 + X^7 + X^5 + X^4 + X^3 + X + 1$, son degré est 8 et il se factorise en un produit de $\displaystyle 2 = \frac 8 4 $ polynômes $f(X)$ et $g(X)$ de degrés $4$.
Les polynômes $f(X)=x^4+aX^3+bX^2+cX+1$ et $g(X)=X^4+cX^3+bX^2+aX+1$ sont symétriques car on pourrrait montrer que toute racine $X$ de l'un correspond à l'inverse d'une racine de l'autre, (ce qu'on montrer en déterminant les racines $\omega^\nu$ de ces polynômes). En identifiant le produit $f(X)g(X)$ à $\displaystyle \Phi_{15}(X)$ on obtient les valeurs des coefficients $a$, $b$, $c$ et donc $f(x)=x^4+X^3+1$ et $g(X)=X^4+X+1$ (interchangeables).
Cliquez sur $1+X^3+X^4$ ou sur $1+X+X^4$ pour lancer l'application et vérifier que le polynôme permet de construire le corps $F_{16}$.

Exemple 2 : $p=3$, $n=4$, $p^n=81$, $\displaystyle \Phi_{80}(X)=X^{32}-X^{24}+X^6-X^8+1$ se factorise dans $\displaystyle F_3[X]$ en huit facteurs $X^4+X+2$, $X^4+2X+2$, $X^4+X^3+2$, $X^4+X^3+X^2+2X+2$, $X^4+X^3+2X^2+2X+1$, $X^4+2X^3+2$, $X^4+2X^3+X^2+X+2$, $X^4+2X^3+2X^2+X+2$.
Cliquez sur l'un ou l'autre de ces huit facteurs pour lancer l'application et vérifier que ce polynôme permet bien de construire le corps $F_{81}$.

Exemple 3 : $p=5$, $n=2$, $p^n=25$, $\displaystyle \Phi_{24}(X)=X^8-X^4+1$ dont les facteurs dans $F_5[X]$ sont $X^2 + X + 2$, $X^2+2X+3$, $X^2 + 3X+ 3$, $X^2 + 4X+2$.
Cliquez sur l'un ou l'autre de ces facteurs pour lancer l'application.
















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014