Corps finis

Construction

On représentera un corps fini de caractéristique \(p\) sous la forme d’une \(\F_p\)-algèbre \(\F_p[x]/(f(x))\simeq \F_p[\alpha]\) via \(\alpha=x\mod f(x)\), où \(f\) est un polynôme irréductible sur \(\F_p\).

1. Construire le corps \(\F_4\), donner la liste de ses éléments et calculer sa table de multiplication.

   solution ⇲ ⇱ solution

   On cherche un irréductible de degré \(2\) sur \(\F_2\), il n’y a que \(x^2+x+1\). On définit le générateur \(a = x\mod x^2+x+1\).

   a = Mod(x,Mod(1,2)*(x^2+x+1))
   L = [ 0, 1, a, a+1]
   lift(lift(matrix(#L,#L,i,j,L[i]*L[j])))
   

   solution xcas ⇲ ⇱ solution xcas

   C’est assez pénible, il faut sans cesse réduire modulo \(P\) à la main.

   P := x^2+x+1 % 2
   a := x
   L := [ 0, 1, a, a+1 ]
   M := matrix(4,4,(k,j)->(L[k]*L[j] % P) % 0)
   

2. Combien y a-t-il de manières de construire \(\F_4\) ? \(\F_8\) ? \(\F_{16}\) ?

   solution ⇲ ⇱ solution

   Pour \(\F_4\), il n’y a qu’une solution puisqu’il y a un unique irréductible de degré \(2\).

   Pour \(F_8\), les irréductibles de degré \(3\) sont les polynômes sans racine, il y en a 2 : \(x^3+x^a+1\) avec \(1\leq a\leq 2\).

   Enfin les irréductibles de degré 4 sont ceux qui n’ont pas de racines, desquels on ôte le carré du seul irréductible de degré \(2\). Cela fait \(4-1=3\) polynômes.

3. Soit \(a\) tel que \(\F_4=\F_2[a]\). Montrer que si \(b\) vérifie \(b^2=b+a\), on a \(\F_8=\F_4[b]\). Quel est le polynôme minimal de \(b\) sur \(\F_2\) ?

4. Montrer que pour \(p\) impair, on peut toujours construire \(\F_{p^2}\) comme \(\F_p[a]/(a^2-b)\), avec \(b\in\F_p\). Quel est le nombre de manières de le faire ?

Polynômes irréductibles

1. Calculer le nombre de racines de P:=x^11+x^5+2x+1 dans \(\F_{7^3}\).

   solution xcas ⇲ ⇱ solution xcas

   P := x^11+x^5+2*x+1
   

2. Par un calcul de pgcd, montrer que \(P\) possède un facteur irréductible de degré \(8\). (sans faire appel à la fonction factor)

3. Construire \(\F_{7^8}\), et construire les huit racines de \(P\) dans ce corps. Vérifier le résultat en factorisant P.

4. Prendre un élément au hasard et calculer son polynôme minimal.

5. Construire \(\F_{7^3}\) de deux manières différentes, et expliciter l’isomorphisme entre les deux représentations

6. Construire une extension de \(\F_2\) dans laquelle le polynôme \(x^{15}-1\) est scindé. Même question avec une extension de \(\F_7\).

7. Construire une racine \(45\)-ième de l’unité \(a\) dans une extension de \(\F_4\).

Factorisation : algorithme de Berlekamp

Pour les exemples, on considère le polynôme P:=x^10-x-1 (la théorie vaut pour un polynôme quelconque sans facteur carré modulo \(p\)).

1. Montrer que pour tout premier \(p<100\), \(P\) est à racines simples dans \(\F_p\).

   solution ⇲ ⇱ solution

   On calcule le discriminant de \(P\), et on vérifie qu’il n’a pas de petit facteur.

2. Factoriser \(P\) dans \(\F_p\) pour \(p\in\set{2,3,5,7,11,13,17,19}\) à l’aide d’Xcas.

   solution ⇲ ⇱ solution

   apply(p->factors(x^10-x-1 % p) % 0,[2,3,5,7,11,13,17,19]);
   

Soit \(p\) premier tel que \(P\) est à racines simples dans \(\F_p\). On considère l’algèbre quotient \(A_p=\F_p[x]/(P)\), et l’endormorphisme de Frobenius \(\phi:x\mapsto x^p\).

1. Écrire une fonction mat_phi(P,p) qui renvoie la matrice \(M_p\) de l’endomorphisme \(\phi\) sur la base \(1,x\dots x^{n-1}\) de \(A_p\) (où \(n\) est le degré de \(P\)).
2. Calculer les rangs des matrices \(M_p-I_n\), et les comparer aux factorisations de \(P\). Que constate-t-on ?
3. Montrer que \(A_2\simeq \F_{8}\times \F_{128}\). Quels sont les éléments de \(A_2\) qui vérifient \(x^2=x\) ?
4. On note \(K_p=\ker(\phi_p-\Id)\subset A_p\). Montrer que c’est une sous-algèbre dont la dimension est le nombre de facteurs irréductibles de \(P\).
5. Montrer que pour tout \(f\in K_p\), \(P\mid \prod_{a\in\F_p} (f-a)\)
6. Montrer que pour tout \(f\in K_p\), \(P = \prod_{a\in\F_p} \pgcd(P,f-a)\)
7. Ecrire un algorithme de factorisation des polynômes utilisant cette idée : en parcourant les vecteurs \(f\) du noyau \(K_p\) et les éléments \(a\) de \(\F_p\), calculer les \(\pgcd(P,f-a)\) jusqu’à en obtenir un non-trivial.

Polynômes primitifs

On dit qu’un polynôme \(P\) irréductible de degré \(d\) sur \(\F_q\) est primitif si \(x \mod P\) est un générateur de \(\F_{p^d}^\ast\), c’est-à-dire une racine primitive \(p^d-1\)-ième de l’unité.

1. Ecrire une fonction primitif(p,d) qui renvoie un polynôme primitif de degré \(d\) sur \(\F_p\).
2. Quels sont les polynômes primitifs de degré \(5\) sur \(\F_2\) ?