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 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}\) ?

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}\).
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\).

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\) ?

Suites récurrentes

On étudie les suites récurrentes linéaires à coefficients dans un corps fini.

1. Ecrire une fonction termes(R,u,n) qui calcule les n premiers termes d’une suite donnée par une relation de récurrence d’ordre \(d\)

   \[\forall n\geq 0, \sum_{i=0}^d u_{n+i}r_i = 0\]

   dont on donne l’annulateur \(R(x)=\sum_{i=0}^d r_i x^i\) et les valeurs initiales \(u=(u_0,\dots u_{d-1})\).

2. On considère des suites binaires d’ordre \(4\). En faisant varier \(R\) et \(u\), vérifier que la suite est toujours périodique. Quelle est la période maximale ? démontrer ce fait.

3. Pour quels polynômes obtient-on une période maximale ? Construire une suite récurrente de période \(127\).

On munit l’espace des suites \(\F_p^{\N}\) d’une structure de \(\F_p[x]\)-module via l’opérateur de décalage \(x.(u_n)=(u_{n+1})\).

1. Montrer qu’une suite admet \(\ell\) pour période si et seulement si son polynôme minimal divise \(x^l-1\). Démontrer la caractérisation des suites de période maximale.
2. Montrer qu’un annulateur d’une suite de degré \(d\) est déterminé par les \(2d\) premiers termes de la suite. Retrouver l’annulateur de la suite de période \(127\) à partir des premiers termes de la suite.