Corps fini | polynômes irréductibles

Polynômes irréductibles

Un critère d'irréductibilité

Si deux polynômes P et Q de K[X] possèdent une racine commune dans une extension L de K, et si P est irréductible, alors P divise Q. En effet, sinon ces polynômes seraient premiers entre eux ce qui passerait à L par l'identité de Bézout[15]. Ce résultat préliminaire est utile pour établir :

Proposition. — Soient Fq un corps fini à q éléments et n un entier strictement positif. Dans Fq[X], le polynôme X qn – X est égal au produit de tous les polynômes unitaires irréductibles de degré divisant n.

En notant md(q) le nombre de polynômes unitaires irréductibles de degré d sur Fq, l'égalité des degrés, dans l'égalité polynomiale de la proposition, donne :

Cette proposition permet donc de montrer l'existence de polynômes irréductibles de degré n quelconque dans Fq[X] via l'encadrement suivant[16] :

Elle a été établie sans supposer l'existence d'un corps fini de cardinal qn et la minoration (appliquée à q premier) fournit donc une autre démonstration de ce résultat[16].

Une évaluation plus précise est possible, en inversant par la fonction de Möbius (notée μ)[17] :

La proposition fournit également une caractérisation des polynômes irréductibles qui peut être exploitée algorithmiquement[16] :

Un polynôme P de degré n > 0 sur Fq est irréductible si et seulement si

  • P divise X qn – X
  • P est premier avec les X qr – X, où r = n/d, d diviseur premier de n.

Le nombre d'éléments de Fqn n'appartenant à aucun de ses sous-corps stricts maximaux (les Fqr pour de tels r) est donc nmn(q).

Polynôme minimal

Dans un corps fini Fq, tout élément α est algébrique sur son sous-corps premier Fp (sur n'importe quel sous-corps en fait), c'est-à-dire qu'il existe un polynôme à coefficients dans Fp qui annule α (les puissances successives de α ne peuvent être indépendantes). Le polynôme unitaire à coefficients dans Fp de plus petit degré qui annule α est appelé polynôme minimal de α sur Fp[18]. Il est nécessairement irréductible et engendre l'idéal des polynômes annulateurs de α. Les coefficients du polynôme étant invariants par l'automorphisme de Frobenius et ses itérés, les αpi sont également des racines de ce polynôme. On montre qu'il n'y en a pas d'autre.

Proposition. — Soit P polynôme minimal de degré r sur Fp de α élément d'un corps Fq de caractéristique p. Alors toutes les racines de P sont simples et ce sont exactement :

α, αp, αp 2..., αp r – 1.

Il suffit de montrer que ces r racines sont distinctes. Soient 0 < ij < r et αpi = αpj, alors, en élévant à la puissance idoine, αpr–j+i = α, donc P divise Xpr–j+i – X (résultat préliminaire du paragraphe précédent), donc (proposition précédente) r divise r – j + i, donc i = j[19].

Tout polynôme unitaire P irréductible sur Fp est le polynôme minimal de la classe de X dans son corps de rupture Fp[X]/(P), qui contient donc toutes les racines de P. La démonstration vaut pour n'importe quel corps fini (pas nécessairement premier), c'est-à-dire que

Proposition. — Le corps de rupture d'un polynôme irréductible sur un corps fini est aussi son corps de décomposition.

Les α, αp, αp2, ..., αpr–1, les éléments ayant même polynôme minimal sur Fp que α, sont appelés conjugués de α par rapport à Fp[20]. Ce sont aussi les images de α par les n automorphismes de Fq. Ces images sont distinctes si et seulement si le degré r du polynôme minimal de α égale le degré n de l'extension Fq de Fp.

Le polynôme minimal d'un élément primitif (au sens racine primitive de l'unité) de Fq est appelé polynôme primitif[21], c'est nécessairement un polynôme irréductible de degré n dont les racines sont les n conjugués (distincts) d'une racine particulière α, soit α, αp, αp2, ..., αpn–1.

On va voir dans la section suivante que les polynômes primitifs sur Fp sont aussi les facteurs irréductibles du polynôme cyclotomique d'indice pn – 1 sur ce même corps.

Polynômes primitifs et polynômes cyclotomiques

Illustration graphique du groupe multiplicatif de F4.

Soit p un nombre premier, n un entier strictement positif et q = pn. On a déduit du théorème de Lagrange que tout élément non nul de Fq est racine de l'unité, et donc racine du polynôme Xq-1 - 1. Cette propriété est illustrée sur la figure de droite, les trois éléments non nuls de F4 sont les trois racines de l'unité.

Les polynômes cyclotomiques étant à coefficients entiers, ils s'interprètent aussi dans les corps finis[22], mais alors qu'ils sont irréductibles dans Q, ils ne le sont plus forcément dans un sous-corps premier Fp[23] (voir la section Exemples). Dans Z[X], Xq–1 – 1 est le produit des polynômes cyclotomiques dont l'indice divise q – 1, et ceci passe à Fp. Par ailleurs un polynôme irréductible P de degré strictement supérieur à 1 est tel que Fp[X]/(P) est un corps fini, et P, polynôme minimal d'un élément de ce corps, divise Xq–1 – 1, donc[24] :

  • Tout polynôme irréductible de Fp[X] autre que X divise un polynôme cyclotomique.

Si φ désigne la fonction indicatrice d'Euler il existe exactement φ(q – 1) éléments primitifs dans Fq. Comme par définition ces éléments ne sont pas racines de Xd – 1, donc de Φd pour d < q – 1, ce sont les racines du polynôme cyclotomique Φq – 1. Les polynômes primitifs, qui sont les polynôme minimaux (sur Fp) de ces éléments primitifs, divisent donc Φq – 1.

La relation « avoir même polynôme minimal sur Fp » est une relation d'équivalence, dont chaque classe possède pour cardinal le degré du polynôme irréductible associé (voir la section #Polynôme minimal, ou plus simplement dans le cas particulier des polynômes primitifs la section #Groupe multiplicatif et conséquences). On a donc :

  • le polynôme cyclotomique d'indice pn – 1 est le produit des polynômes primitifs de degré n sur Fp.
  • Il existe exactement φ(q – 1) éléments primitifs dans Fq, correspondant à φ(q – 1)/n polynômes primitifs sur son corps premier Fp.

On déduit en particulier de l'existence d'un corps fini de cardinal pn pour tout entier n, que le polynôme cyclotomique d'indice pn – 1 est toujours le produit de polynômes irréductibles de même degré n sur Fp. Ce résultat peut se démontrer directement, en utilisant seulement l'existence du corps de rupture d'un polynôme, et alors on a une autre preuve d'existence d'un corps fini de cardinal pn (qui suppose connus les résultats de base sur les polynômes cyclotomiques usuels)[25]. En fait tout polynôme cyclotomique se décompose sur Fp en facteurs irréductibles de même degré[26].

Il peut y avoir d'autres polynômes irréductibles de degré n que les polynômes primitifs. Par exemple dans F9, on a

X8 – 1 = (X – 1)(X + 1)(X2 + 1)(X2 + X + 2)(X2 + 2X + 2),

et X2 + 1, bien qu'irréductible, n'est le polynôme minimal d'aucun des 4 éléments primitifs (voir aussi ci-dessous l'exemple de F16).

Remarque : on peut définir directement le polynôme cyclotomique d'indice r sur un corps fini K de caractéristique p pour r qui n'est pas un multiple de p, à partir des racines r-ième de l'unité dans une extension de KXr - 1 est scindé. Leur étude se mène alors de la même façon que celle des polynômes cyclotomiques usuels sur Q[27].

Article détaillé : Polynôme cyclotomique.

Exemples

Caractéristique deux

Il existe sur F2 exactement deux polynômes de degré 1, dont l'un — le polynôme cyclotomique d'indice 1 sur F2 — est primitif :

Les racines du (ou des) polynôme(s) de degré 2 irréductibles sur F2 sont les éléments de F22 = F4 qui n'appartiennent pas à F2. Ce sont donc les 2 générateurs du groupe multiplicatif F4* à trois éléments. Par conséquent, il existe en fait un unique polynôme irréductible de degré 2 sur F2, il est primitif, et c'est le polynôme cyclotomique d'indice trois :

Les racines des polynômes de degré 3 irréductibles sur F2 sont les éléments de F23 = F8 qui n'appartiennent pas à son unique sous-corps F2. Ce sont donc les 6 générateurs du groupe multiplicatif F8* à sept éléments. Par conséquent, il existe exactement 6/3 = 2 polynômes irréductibles de degré 3 sur F2, ils sont primitifs, et leur produit est le polynôme cyclotomique d'indice sept. Ce sont donc les deux facteurs de :

Les racines des polynômes de degré 4 irréductibles sur F2 sont les éléments de F24 = F16 qui n'appartiennent pas au sous-corps intermédiaire F4. Ce sont donc, dans le groupe multiplicatif F16* à quinze éléments, les 12 dont le cube n'est pas 1. Par conséquent, il existe exactement 12/4 = 3 polynômes irréductibles de degré 4 sur F2. Parmi leurs 12 racines, 8 sont d'ordre quinze (i.e. sont des générateurs du groupe) car φ(15) = 8, donc parmi ces trois polynômes, deux seulement sont primitifs et leur produit est le polynôme cyclotomique d'indice quinze. Ce sont donc les deux facteurs de :

Les 4 racines restantes sont d'ordre cinq, donc le polynôme irréductible de degré 4 non primitif est le polynôme cyclotomique d'indice cinq :

Caractéristique trois

Il existe sur F3 trois polynômes unitaires de degré un, dont deux sont les polynômes cyclotomiques d'indices un et deux :

L'extension d'ordre neuf contient six éléments hors du corps premier ; elle est de dimension deux, il existe donc exactement trois polynômes irréductibles. Le groupe multiplicatif est d'ordre huit et contient quatre éléments générateurs. Deux des polynômes irréductibles sont primitifs, le dernier est le polynôme cyclotomique d'ordre quatre.

L'extension d'ordre vingt-sept contient un unique sous-corps : le corps premier. Il existe donc 24 éléments hors de tout sous-corps et 24/3 = 8 polynômes irréductibles de degré 3. Le groupe multiplicatif contient vingt-six éléments dont 12 générateurs. Par conséquent, parmi les huit polynômes irréductibles de degré 3, 12/3=4 sont primitifs et ce sont les quatre facteurs de :

Les quatre polynômes irréductibles de degré 3 non primitifs sont polynômes minimaux des 12 éléments d'ordre treize du groupe multiplicatif. Ce sont donc les 12/3 = 4 facteurs de :

Dans d'autres langues
العربية: حقل منته
беларуская: Канечнае поле
български: Крайно поле
català: Cos finit
English: Finite field
español: Cuerpo finito
עברית: שדה סופי
italiano: Campo finito
日本語: 有限体
한국어: 유한체
português: Corpo finito
română: Corp finit
Simple English: Galois field
српски / srpski: Коначно поље
svenska: Ändlig kropp
Türkçe: Sonlu alan
українська: Поле Галуа
中文: 有限域
粵語: 有限體