Corps finis avec xcas

mercredi 2 mars 2011
par  Christian Mercat

Les corps finis sont de cardinal p^n avec p premier, soit 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29..., et pour tout tel nombre de la sorte, il existe un corps fini de ce cardinal, unique à isomorphisme près. Nous allons les construire avec xcas et dresser la table des lois des premiers corps.

Prise en main, algèbres de polynômes

Les corps finis s’appuient sur l’arithmétique modulaire des polynômes. Xcas a toutes les fonctions requises pour les manipuler mais nous allons nous reposer sur les plus simples seulement, la division euclidienne d’un polynôme par un autre, et reprogrammer les fonctions évoluées pour les comprendre de l’intérieur.

Commençons par calculer le Plus Grand Commun Diviseur de deux éléments, en s’appuyant sur l’algorithme d’Euclide étendu, qui donne les couples de Bézout. Procédons sur deux entiers, puis sur deux polynômes en s’autorisant simplement la division euclidienne qui donne le quotient et le reste par la commande quorem.

Si a=b\times q+r, 0\leq r<b, le pgcd d de a et b est le même que celui de b et r car tout diviseur commun à a et à b l’est aussi forcément à r. Qui plus est, si on connait u et v tels que u\times b+v\times r=d, alors v\times a + (u-q\times v)\times b = d, ce qui nous donne l’algorithme d’Euclide étendu, remontant récursivement les éléments de Bézout, avec le cas d’arrêt trivial si a est multiple de b, qui est donc leur pgcd.

Commencez un nouveau programme sous xcas par Prg>Nouveau Programme.

ibezout(A,B):={ // Pour les entiers
local Q,R,U,V;
[Q,R]:=iquorem(A,B);
if (R==0) return [0,1];
[U,V]:=ibezout(B,R);
return [V, U-Q*V];
}
:;

ipgcd(A,B):={
local U,V;
[U,V]:=ibezout(A,B);
return A*U+B*V;
}:;

Qu’on teste en ouvrant une nouvelle entrée CAS>Nouvelle entrée

ibezout(12,9)

qui donne [1,-1] et effectivement, 12-9=3 leur pgcd. La seule différence avec le programme pour les polynômes est le i en moins dans la fonction iquorem qui devient quorem et la nécessité de simplifier les expressions polynomiales par simplify(U-Q*V) et simplify(A*U+B*V). N’hésitez pas à sélectionner un mot et taper F1 pour avoir l’aide. Remarquez l’indéterminée implicite "x" et non pas "X" avec xcas :

bezout((x+1)*(x^2+1),(x+1)*(x^2+x+1)) donne [x+1, -x] et

simplify((x+1)*(x+1)*(x^2+1)-x*(x+1)*(x^2+x+1))

donne x+1, le pgcd des polynômes de départ.

La propriété fondamentale qui rend le calcul modulaire utile, particulièrement en cryptographie, est qu’il est facile de calculer la puissance d’un élément tandis qu’il est réputé difficile, étant donnés un générateur \alpha et un élément qui est un certain \alpha^k, de retrouver la puissance k en question. C’est le problème du logarithme discret.

En effet, pour mettre à la puissance k un élément, il suffit au pire de 2 \log_2(k) multiplications et non pas k :

rapide(A,n):={
 // puissance rapide A^n en décomposant n en binaire
 local B;
 if (n==0) return 1;
 if (n==1) return A;
 B:=rapide(A, iquo(n,2)); // appel récursif pour calculer A^(n/2)
 if(irem(n,2)==0) { // n est pair
     return simplify(B*B); // A^(2k) = (A^(k))^2
   } else { // n est impair
     return simplify(A*B*B); // A^(2k+1) = (A^(k))^2*A
   }
}:;

qu’on teste pour calculer des puissances d’entiers ou de polynômes (l’algorithme fonctionne sans modification pour n’importe quel groupe multiplicatif dont 1 est le neutre), puis qu’on adapte pour le calcul modulaire polynomial en prenant le reste dans la division euclidienne par P :

rapide(A,n,P):={
 // puissance rapide mod P un polynome
 local B;
 if (n==0) return 1;
 if (n==1) return rem(A, P);
 B:=rapide(A, iquo(n,2),P); // Appel récursif A^k, k=n/2
 B:=rem(B*B, P); // rem appelle simplify
 if (irem(n,2)==0) {return B;} // (A^k)^2 pour n = 2k
 else return rem(A*B, P); // A*(A^k)^2 pour n = 2k+1
}:;

Propriétés

Les corps finis sont d’abord les corps premiers \mathbb{Z}/p\mathb{Z} pour p premier, puis les anneaux quotients \mathbb{Z}/p\mathb{Z}[X]/PP est un polynôme irréductible de degré n.

Remarquons qu’il y a p^n polynômes différents dans l’anneau quotient \mathbb{Z}/p\mathb{Z}[X]/X^n, car il y a p coefficients différents en chaque degré, tandis que les fonctions en caractéristique p sont de cardinal p!. Contrairement au cas de caractéristique nulle, il n’y a donc pas injection des polynômes dans les fonctions.

Si P est irréductible, il n’y a pas de diviseur de zéro dans l’anneau quotient \mathbb{Z}/p\mathb{Z}[X]/P, qui est donc un corps, de cardinal p^n, où n=\deg(P).

Réciproquement, dans un corps fini K, le sous-groupe additif engendré par l’élément neutre de la multiplication (noté 1) est isomorphe à un sous-corps premier \mathbb{Z}/p\mathb{Z} et p est donc la caractéristique du corps. Le corps K est ainsi muni d’une structure de \mathbb{Z}/p\mathb{Z}-espace vectoriel, qui est donc de cardinal p^n pour n la dimension de cet espace vectoriel.

D’après le théorème de Lagrange, l’ordre d’un élément (le plus petit k tel que x^k=1) divise l’ordre (le cardinal) du groupe |K^*|=p^n -1, donc le polynôme X^{p^n-1}-1 a tous les éléments de K^* comme racines et X^{p^n}-X=\prod_{\alpha\in K}(X-\alpha) a ses p^n racines qui sont simples (sa dérivée vaut -1), chacun des éléments de K. C’est donc son corps de décomposition. Un autre corps de même cardinal lui sera donc égal, à réarrangement des racines près (théorie de Galois).

Pour résumer, nous avons donc montré la propriété fondamentale des corps finis :
- tout corps fini K est de cardinal |K|=p^n la puissance d’un nombre premier, et il existe à isomorphisme près un unique corps fini d’un tel cardinal donné.

De plus, les p^n-1 éléments de K^* sont racines distinctes de X^{p^n-1}-1 donc l’exposant du groupe multiplicatif, le plus petit commun multiple des ordres de ses éléments, est donc p^n-1. Or dans un groupe fini commutatif, l’exposant du groupe est toujours ordre d’un de ses éléments qui est donc primitif (ou générateur). On en déduit que
- le groupe multiplicatif K^*=K\setminus\{0\} d’un corps fini est cyclique.

En considérant X^{p^d}-X qui divise X^{p^n}-X si d|n, on montre que
- un sous-corps d’un corps de cardinal p^n (p premier) a pour cardinal p^dd|n, et pour tout diviseur d de n le corps de cardinal p^n contient un unique sous-corps de cardinal p^d ;

En remarquant qu’en caractéristique p, les nombres de combinaison intermédiaires C_p^k, 0<k<p sont tous nuls, on obtient en développant (a+b)^p=a^p+b^p que
- l’application de Frobénius x\mapsto x^p est un automorphisme du corps K, corps fini de caractéristique p.

En appliquant Frobénius à un élément primitif \alpha, on construit le corps K comme isomorphe à \mathbb{Z}/p\mathb{Z}[X]/PP=\prod_{k=0}^{n-1}(X-\alpha^{p^k}) scindé à n racines distinctes, irréductible dans \mathbb{Z}/p\mathb{Z}[X]. On obtient également P|X^{p^n}-X, tout en restant cependant premier avec d’autres diviseurs de celui-ci, les X^{p^d}-X pour d|n. Ce critère nécessaire d’irréducibilité est en fait suffisant et permet de trouver des polynômes irréductibles en tout degré. Les polynômes cyclotomiques sont également d’une grande aide.

Nous verrons des exemples de ces propriétés.

Polynômes irréductibles de \mathbb{Z}/p\mathb{Z}[X]

On teste l’irréductibilité avec xcas :

est_irred(P,p):={
 // teste si P est irreductible dans Z/pZ[X]
 // en calculant le pgcd de P avec X^(p^k)-X
 // pour k diviseur de deg(P), qui doit donner 1
 local m,k,Xpk,X, divs;
 m := iquo(degree(P),2);
 divs := divisors(degree(P));
 X:= (x)%p; // C'est x dans Z/pZ[x]
 Xpk:= X; // Va augmenter
 for (k:=1;k<=m;k++){
   // X^(p^k) mod P
   Xpk:=rapide(Xpk, p, P);
   if (contains(divs, k) && degree(pgcd(Xpk-X,P))>0) return 0; // Ils ont un facteur commun non trivial
 }
 return 1; // Aucun facteur commun, P est donc irréductible
}:;

On teste tout bêtement un par un les p^n polynômes de degré inférieur à n dans \mathbb{Z}/p\mathbb{Z}[X] en les codant par des entiers écrits en base p :

irreds(p,m):={
 // calcul tous les polynomes irreductibles
 // de degré m dans Z/pZ[X]
 local n,irr,mini,pm,j,li;
 if (!isprime(p)) return p+" non premier!";
 pm:=p^m;
 li:=[];
 // essai systematique de tous les poly.
 // Il y en a p^m, qu'on code par un nombre en base p
 for (n:=1;n<=pm;n++){
   irr:=op(convert(n,base,p)); // Chaque chiffre de l'écriture en base p est le coef d'un x^j
   irr:=(x^m+sum(irr[j]*x^(size(irr)-j-1),j,0, size(irr)-1))% p;
   if (est_irred(irr,p)) li:=append(li, irr);
 }
 return li;
}:;
n234
p=2 X^2+X+1 X^3+X+1, X^3+X^2+1 X^4+X+1, X^4+X^3+1, X^4+X^3+X^2+X+1
p=3 X^2+X-1, X^2-X-1, X^2+1 X^3-X+1, ... X^4+X-1, ...
p=5 X^2+2, ... X^3+X+1, ... X^4+2, ...

Tables de lois

Une fois un polynôme irréductible P de degré n trouvé dans \mathbb{Z}/p\mathbb{Z}[X], on dresse la table des lois en utilisant rem(A*B,P). On dresse également la table des exponentiels g^k pour chaque élément g pour reconnaitre les primitifs : ils contiennent tous un 1 en dernière position, conformément au théorème de Lagrange, mais seuls les primitifs n’en ont qu’un seul.

- \mathbb{F}_2=\mathbb{Z}/2\mathbb{Z}

\left(\begin{array}{c|cc}
+&0&1\\
\hline
0&0 & 1 \\
1&1 & 0
\end{array}\right) ,
\left(\begin{array}{c|cc}
*&0&1\\
\hline
0&0 & 0 \\
1&0 & 1
\end{array}\right)

Remarquez que -1 n’est pas primitif, il ne l’est jamais dans \mathbb{Z}/p\mathbb{Z}.

- \mathbb{F}_3=\mathbb{Z}/3\mathbb{Z}

\left(\begin{array}{c|ccc}
+&0&1&-1\\
\hline
0&0 & 1 & -1 \\
1&1 & -1 & 0 \\
-1&-1 & 0 & 1
\end{array}\right)

\left(\begin{array}{c|ccc}
*&0&1&-1\\
\hline
0&0 & 0 & 0 \\
1&0 & 1 & -1 \\
-1&0 & -1 & 1
\end{array}\right)

- \mathbb{F}_4=\mathbb{Z}/2\mathbb{Z}[x]/(x^2+x+1)

\left(\begin{array}{c|cccc}
+&0&1&x&x+1\\
\hline
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
\end{array}\right)

\left(\begin{array}{c|cccc}
*&0&1&x&x+1\\
\hline
0 &0 & 0 & 0 & 0 \\
1&0 & 1 & x & x+1 \\
x&0 & x & x+1 & 1 \\
x+1&0 & x+1 & 1 & x
\end{array}\right)

x et x+1 sont tous les deux primitifs et leur échange est un endomorphisme de corps.

- \mathbb{F}_5=\mathbb{Z}/5\mathbb{Z} Désormais, on tait la ligne et la colonne de titre.

\left(\begin{array}{ccccc}
0 & 1 & 2 & -2 & -1 \\
1 & 2 & -2 & -1 & 0 \\
2 & -2 & -1 & 0 & 1 \\
-2 & -1 & 0 & 1 & 2 \\
-1 & 0 & 1 & 2 & -2
\end{array}\right)

\left(\begin{array}{ccccc}
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 2 & -2 & -1 \\
0 & 2 & -1 & 1 & -2 \\
0 & -2 & 1 & -1 & 2 \\
0 & -1 & -2 & 2 & 1
\end{array}\right)

- \mathbb{F}_7=\mathbb{Z}/7\mathbb{Z}

\left(\begin{array}{ccccccc}
0 & 1 & 2 & 3 & -3 & -2 & -1 \\
1 & 2 & 3 & -3 & -2 & -1 & 0 \\
2 & 3 & -3 & -2 & -1 & 0 & 1 \\
3 & -3 & -2 & -1 & 0 & 1 & 2 \\
-3 & -2 & -1 & 0 & 1 & 2 & 3 \\
-2 & -1 & 0 & 1 & 2 & 3 & -3 \\
-1 & 0 & 1 & 2 & 3 & -3 & -2
\end{array}\right)

\left(\begin{array}{ccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 2 & 3 & -3 & -2 & -1 \\
0 & 2 & -3 & -1 & 1 & 3 & -2 \\
0 & 3 & -1 & 2 & -2 & 1 & -3 \\
0 & -3 & 1 & -2 & 2 & -1 & 3 \\
0 & -2 & 3 & 1 & -1 & -3 & 2 \\
0 & -1 & -2 & -3 & 3 & 2 & 1
\end{array}\right)

Seuls 3 et -2=5 sont primitifs :

\left(\begin{array}{c|cccccc}
g&1 & 2 & 3 & -3 & -2 & -1 \\
g^2&1 & -3 & 2 & 2 & -3 & 1 \\
g^3&1 & 1 & -1 & 1 & -1 & -1 \\
g^4&1 & 2 & -3 & -3 & 2 & 1 \\
g^5&1 & -3 & -2 & 2 & 3 & -1 \\
g^6&1 & 1 & 1 & 1 & 1 & 1
\end{array}\right)

- \mathbb{F}_8=\mathbb{Z}/2\mathbb{Z}[x]/(x^3+x+1)

2=x, 3=x+1, 4=x^2, 5=x^2+1, 6=x^2+x, 7=x^2+x+1

\left(\begin{array}{cccccccc}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
1 & 0 & 3 & 2 & 5 & 4 & 7 & 6 \\
2 & 3 & 0 & 1 & 6 & 7 & 4 & 5 \\
3 & 2 & 1 & 0 & 7 & 6 & 5 & 4 \\
4 & 5 & 6 & 7 & 0 & 1 & 2 & 3 \\
5 & 4 & 7 & 6 & 1 & 0 & 3 & 2 \\
6 & 7 & 4 & 5 & 2 & 3 & 0 & 1 \\
7 & 6 & 5 & 4 & 3 & 2 & 1 & 0
\end{array}\right)

\left(\begin{array}{cccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
0 & 2 & 4 & 6 & 3 & 1 & 7 & 5 \\
0 & 3 & 6 & 5 & 7 & 4 & 1 & 2 \\
0 & 4 & 3 & 7 & 6 & 2 & 5 & 1 \\
0 & 5 & 1 & 4 & 2 & 7 & 3 & 6 \\
0 & 6 & 7 & 1 & 5 & 3 & 2 & 4 \\
0 & 7 & 5 & 2 & 1 & 6 & 4 & 3
\end{array}\right)

Tous les éléments (différents de 0 et 1) sont primitifs. Le polynôme x^3+x+1 n’est pas le seul irreductible de degré 3 dans \mathbb{Z}/2\mathbb{Z}[x], il y a aussi x^3+x+1. L’endomorphisme de corps associé est x\leftrightarrow x+1, x^2\leftrightarrow x^2+1.

- \mathbb{F}_9=\mathbb{Z}/3\mathbb{Z}[x]/(x^2+1)

2=-1, 3=x, 4=x+1, 5=x-1, 6=-x, 7=-x+1, 8=-x-1

\left(\begin{array}{ccccccccc}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
1 & 2 & 0 & 4 & 5 & 3 & 7 & 8 & 6 \\
2 & 0 & 1 & 5 & 3 & 4 & 8 & 6 & 7 \\
3 & 4 & 5 & 6 & 7 & 8 & 0 & 1 & 2 \\
4 & 5 & 3 & 7 & 8 & 6 & 1 & 2 & 0 \\
5 & 3 & 4 & 8 & 6 & 7 & 2 & 0 & 1 \\
6 & 7 & 8 & 0 & 1 & 2 & 3 & 4 & 5 \\
7 & 8 & 6 & 1 & 2 & 0 & 4 & 5 & 3 \\
8 & 6 & 7 & 2 & 0 & 1 & 5 & 3 & 4
\end{array}\right)

\left(\begin{array}{ccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
0 & 2 & 1 & 6 & 8 & 7 & 3 & 5 & 4 \\
0 & 3 & 6 & 2 & 5 & 8 & 1 & 4 & 7 \\
0 & 4 & 8 & 5 & 6 & 1 & 7 & 2 & 3 \\
0 & 5 & 7 & 8 & 1 & 3 & 4 & 6 & 2 \\
0 & 6 & 3 & 1 & 7 & 4 & 2 & 8 & 5 \\
0 & 7 & 5 & 4 & 2 & 6 & 8 & 3 & 1 \\
0 & 8 & 4 & 7 & 3 & 2 & 5 & 1 & 6
\end{array}\right)

- 1 n’est bien-sûr pas primitif, mais x et -x non plus car, comme x^2=-1, x^4=1.


Documents joints

Groupes Finis pour l'agrégation interne avec (...)
Groupes Finis pour l'agrégation interne avec (...)
Adapté de Parisse

Commentaires

Navigation

Brèves

12 juillet 2021 - MOOC Entrée dans l’enseignement supérieur

L’école polytechnique propose une série de cours massifs en ligne à prendre comme un "cahier de (...)

18 octobre 2015 - Questionnaires de la CII Université

L’objectif est de collecter de nouvelles réponses pour mieux mesurer l’impact de la réforme du (...)

27 janvier 2010 - Travailler par compétences et avec le socle commun

Conférence le 10 février au CRDP de Lyon de 9 h à 12 h, avec Jean Michel Zarkhartchouk

13 novembre 2008 - Probabilités en 3e

Texte issu d’une formation aux probabilités pour les professeurs de troisième faite par Y. Ducel (...)

Sur le Web