Nombres premiers et polynômes irréductibles de $F_2[X]$

Le problème d’irréductibilité d’un polynôme de $Z[X]$ est difficile. Il plus difficile que le problème de la primalité dans $Z$ puisque ce dernier est un sous-problème du premier! Il existe des algorithmes (Lenstra) de factorisation dans $Z[X]$ basés sur LLL dont on parlera peut être plus tard.

Par contre pour les questions d’irréductibilité et de factorisation dans $F_2[X]$ on dispose de bons algorithmes.

On peut reprendre le problème précédent mais cette fois dans $F_2[X]$. Le critère d’irréductibilité de Cohn n’est plus vrai !
Regardons comment les choses se présentent.

On se donne un nombre premier et son développement binaire
\[p=a_0+a_12+ \dots + a_r2^r.\]
On lui associe canoniquement un polynôme binaire de $F_2[X]$:
\[A_p(X)= a_0+a_1X+\dots +a_rX^r\]
Ce polynôme n’est pas toujours irréductible dans \(F_2[X]\). Voici les premiers exemples :
\[\begin{array}{llll}
p & A_p & Irr & Raison \\
\hline
2 & X &oui\\
3 & 1+X &oui\\
5 & 1+ X^2 &non & =(1+X)^2\\
7 & 1+X+X^2 &oui\\
11 & 1+X+X^3 &oui \\
13 & 1+X^2+X^3 &oui \\
17 & 1+X^{4} &non & =(1+X)^4
\end{array}\]
La suite des nombres premiers correspondant à des polynômes irréductibles de $F_2[X]$ se trouve dans l’encyclopédie OEIS sous l’index : A091206 = 2, 3, 7, 11, 13, 19, 31, 37, 41, 47, 59, 61,…
Dans le même ordre d’idée une autre suite intéressante est celle des nombres associés à tous les polynômes irréductibles de \(F_2[X]\) par la méthode ci-dessus : elle a l’index A014580 = 2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, …
La première liste est simplement l’intersection de A091206 avec la liste des nombres premiers.

On peut étudier quelques cas. Prenons par exemple les nombres premiers de $16\leq p\leq 31$ :

Pour $p=17$ le polynôme de $F_2[X]$ correspondant est $1+X^4=(1+X)^4$ et donc n’est pas irréductible.

Pour 19 le polynôme associé est $1+X+X^4$ qui est irréductible dans $F_2[X]$.

Le polynôme réciproque $1+X^3+X^4$ est donc irréductible, mais qui correspond à 25 qui n’est pas premier!

Pour 23 , le polynôme correspondant est $P(X)=1+X+X^2+X^4$. Ce polynôme comporte 4 termes donc $X=1$ est une racine.
Il n’est pas irréductible.

Son polynôme réciproque $Q(X)= 1+X^2+X^3+X^4$ correspond à 29 et n’est pas irréductible non plus.

Enfin 31 correspond à $1+X+X^2+X^3+X^4$ qui est irréductible car correspondant aux racines 5-ièmes de l’unité qui se trouvent dans $F_{2^4}=F_{16}$.

Réduction mod 2

Soit $Z[X]\rightarrow F_2[X]$ l’homomorphisme naturel d’anneaux, qui à tout $P\in Z[X]$ associe $\overline{P} \in F_2[X]$ par réduction mod 2 des coefficients.

Malheureusement $P\in Z[X]$ est irréductible alors $\overline P$ n’est pas forcément irréductible.

Inversement, tout polynôme de $F_2[X]$ qui est irréductible a son image réciproque « canonique » (à coefficients 0 ou 1) qui est irréductible (en raisonnant par l’absurde).

Si on étudie cette liste les cas de 5 et 17 sont clairs par Frobenius. Mais d’autres cas sont plus complexes.

Ainsi 23 correspond au polynôme \( P= 1+X+X^2+X^4\). D’après le résultat de Cohn \(P\) est irréductible dans $Z[X]$.
Mais $\phi(P)$ n’est pas irréductible dans $F_2[X]$ puisque 1 est une racine :
\[P=(1+X)(1+X^2+X^3).\]

De même 29 correspond au polynôme réciproque de $Q= 1+X^2+X^3+X^4$. Ce polynôme se décompose dans \(F_2[X]\) :
\[Q=(1+X)(1+X+X^3).\]