Corps finis avec xcas
par
Les corps finis sont de cardinal avec premier, soit , 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 , , le pgcd de et est le même que celui de et car tout diviseur commun à et à l’est aussi forcément à . Qui plus est, si on connait et tels que , alors , 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 est multiple de , 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 et un élément qui est un certain , de retrouver la puissance en question. C’est le problème du logarithme discret.
En effet, pour mettre à la puissance un élément, il suffit au pire de multiplications et non pas :
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 :
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 pour premier, puis les anneaux quotients où est un polynôme irréductible de degré .
Remarquons qu’il y a polynômes différents dans l’anneau quotient , car il y a coefficients différents en chaque degré, tandis que les fonctions en caractéristique sont de cardinal . Contrairement au cas de caractéristique nulle, il n’y a donc pas injection des polynômes dans les fonctions.
Si est irréductible, il n’y a pas de diviseur de zéro dans l’anneau quotient , qui est donc un corps, de cardinal , où .
Réciproquement, dans un corps fini , le sous-groupe additif engendré par l’élément neutre de la multiplication (noté 1) est isomorphe à un sous-corps premier et est donc la caractéristique du corps. Le corps est ainsi muni d’une structure de -espace vectoriel, qui est donc de cardinal pour la dimension de cet espace vectoriel.
D’après le théorème de Lagrange, l’ordre d’un élément (le plus petit tel que ) divise l’ordre (le cardinal) du groupe , donc le polynôme a tous les éléments de comme racines et a ses racines qui sont simples (sa dérivée vaut ), chacun des éléments de . 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 est de cardinal la puissance d’un nombre premier, et il existe à isomorphisme près un unique corps fini d’un tel cardinal donné.
De plus, les éléments de sont racines distinctes de donc l’exposant du groupe multiplicatif, le plus petit commun multiple des ordres de ses éléments, est donc . 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 d’un corps fini est cyclique.
En considérant qui divise si , on montre que
un sous-corps d’un corps de cardinal ( premier) a pour cardinal où , et pour tout diviseur de le corps de cardinal contient un unique sous-corps de cardinal ;
En remarquant qu’en caractéristique , les nombres de combinaison intermédiaires , sont tous nuls, on obtient en développant que
l’application de Frobénius est un automorphisme du corps , corps fini de caractéristique .
En appliquant Frobénius à un élément primitif , on construit le corps comme isomorphe à où scindé à racines distinctes, irréductible dans . On obtient également , tout en restant cependant premier avec d’autres diviseurs de celui-ci, les pour . 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
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 polynômes de degré inférieur à dans en les codant par des entiers écrits en base :
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;
}:;
n | 2 | 3 | 4 |
---|---|---|---|
p=2 | , | , , | |
p=3 | , , | , ... | , ... |
p=5 | , ... | , ... | , ... |
Tables de lois
Une fois un polynôme irréductible de degré trouvé dans , on dresse la table des lois en utilisant rem(A*B,P). On dresse également la table des exponentiels pour chaque élément pour reconnaitre les primitifs : ils contiennent tous un en dernière position, conformément au théorème de Lagrange, mais seuls les primitifs n’en ont qu’un seul.
,
Remarquez que n’est pas primitif, il ne l’est jamais dans .
et sont tous les deux primitifs et leur échange est un endomorphisme de corps.
Désormais, on tait la ligne et la colonne de titre.
Seuls 3 et -2=5 sont primitifs :
, , , , ,
Tous les éléments (différents de 0 et 1) sont primitifs. Le polynôme n’est pas le seul irreductible de degré 3 dans , il y a aussi . L’endomorphisme de corps associé est , .
, , , , , ,
1 n’est bien-sûr pas primitif, mais et non plus car, comme , .
Commentaires