Polynôme irréductible dans un corps fini

jool

Bonjour

Pourriez-vous m'aider sur une ou des méthodes pour factoriser  un polynôme quelconque en produit de polynômes irréductibles sur un corps fini ?

Par ailleurs comment peut-on connaître le degré des polynômes irréductibles sur un corps fini ou savoir s'il est réductible ?

GaBuZoMeu

Bonjour

Tu peux commencer par regarder "algorithme de Berlekamp" ou "algorithme de Cantor-Zassenhaus" sur wikipedia.

Sur un corps fini, il y a des polynômes irréductibles en n'importe quel degré.

noix de totos

Un critère de base dans $\mathbb{F}_p[X]$ :

$P$ de degré $n$ est irréductible dans $\mathbb{F}_p[X]$ si et seulement si $P$ divise $X^{p^n}-X$ dans $\mathbb{F}_p[X]$ et, pour tout diviseur premier $q$ de $n$, $\textrm{pgcd} \left( P, X^{p^{n/q}} - X \right) = 1$.

jool

Bonjour

Quelqu'un voudrait-il m'expliquer cette affirmation ?

Un polynôme irréductible de degré 4 sur $\Bbb{F}_2$ a une racine dans $\Bbb{F}_{16}$. Donc il se décompose en un produit de deux polynômes irréductibles dans $\Bbb{F}_4$ (car $\Bbb{F}_{16}$ est une extension de degré 2 de $\Bbb{F}_{4}$).

Merci

Poirot

Considérons le corps de rupture $\mathbb F_2[X]/(P)$ de notre polynôme irréductible de degré $4$. C'est un corps à $16$ éléments, il est donc isomorphe à $\mathbb F_{16}$, et donc $P$ admet bien une racine dans $\mathbb F_{16}$ (en l’occurrence, l'image de la classe de $X$ dans le quotient (ainsi que les images de $X^2, X^4$ et $X^8$ mais passons)).

Voyons maintenant $P$ comme un élément de $\mathbb F_4[X]$. $P$ n'a pas de racine dans $\mathbb F_4$, sinon il admettrait sur $\mathbb F_2$ un facteur de degré $2$ (le polynôme minimal sur $\mathbb F_2$ de l'un de ses supposées racines). Ainsi, il est soit irréductible, soit produit de deux facteurs de degré $2$. Mais le même raisonnement que juste au-dessus nous dit que $P$ est divisible par un polynôme de degré $2$ dans $\mathbb F_4[X]$, CQFD.

jool

Merci Poirot !

Je dois encore approfondir tes explications mais ça commence à s"éclaircir.

Petite question subsidiaire : dans une extension d'un corps fini de degré n est-ce que tous les polynômes irréductibles des éléments de l’extension sont forcément de degré n aussi ?

jool

Pourrais-tu m'expliquer plus ce que tu affirmes qui m intéresse aussi ?

(en l’occurrence, l'image de la classe de X dans le quotient (ainsi que les images de X^2,X^4 et X^8 mais passons)).

Pourquoi X^2/X^4 ET X^8 ?

jool

merci noix de totos !

JLapin

jool a dit :

petite question subsidiaire: dans une extension d'un corps fini de degré n est ce que tous les polynômes irréductibles des éléments de l’extension sont forcément de degré n aussi ?

Sauf si je n'ai rien compris à ta question, la réponse est non car n'importe quel polynôme de degré 1 est irréductible.

PS : merci de ne pas modifier le message car c'est une courte citation et ça rend la double/triple discussion de ce fil plus facile à suivre.

raoul.S

@JLapin il s'agit des polynômes minimaux je pense, car il dit les polynômes irréductibles des éléments de l’extension. Donc c'est oui.
D'ailleurs pas besoin de supposer le corps fini.
Je raconte des salades... je vais me coucher.
Bon on peut dire au moins que le degré de tels polynômes divise $n$...

df

Le théorème implicitement utilisé pour démontrer le critère de base est le suivant.

Soit $K$ un corps fini et $L$ une clôture algébrique de $K$. Si $P$ et $Q$ sont deux polynômes de $K[X]$ qui ont une racine commune dans $L$ et si $P$ est irréductible alors $P$ divise $Q$.

Si $P \in F_p[X]$ est un polynôme irréductible de degré $n$, $\mathbf{F}_p[X]/(P)$ est un corps à $p^n$ éléments. Donc $x^{p^n}=x$ pour tout $x \in \mathbf{F}_p[X]/(P)$. Une racine de $P$ est aussi une racine de $X^{p^n}-X$.
D’après le théorème précédent, $P$ divise $X^{p^n}-X$.

jool

Super df !

Je ne connaissais pas ce théorème,

mais d'après cela $X^{p^n}-X$ devrait diviser tous les polynômes irréductibles et pas seulement ceux de degré diviseur de $n$ ?!

parisse

La première chose à faire pour factoriser, c'est d'éliminer les facteurs multiples en utilisant le pgcd du polynôme et de sa dérivée (si la dérivée est nulle, écrire P comme une puissance p-ième et recommencer): algorithmes de Yun (ou Musser pour sa version moins efficace mais plus simple). Ensuite on calcule la distinct degree factorization de P avec le pgcd de P avec x^(p^k)-x mod P,p  pour k croissant ce qui donne le produit des facteurs de P de degré k exactement (une fois éliminé ceux de degré plus petits). Et enfin on casse les produits de facteurs de même degré avec Berlekamp ou Cantor-Zassenhauss.
Le déroulement partiel de cet algorithme donne une variante effective du critère d'irréductibilité donné par noix de totos : on calcule le pgcd de P avec x^(p^k)-x modulo P,p pour k croissant jusqu'à (degré de P)/2 et on doit trouver 1.