Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 13/11/2022

M'écrire

Brèves de Maths

 

INDEX

 

Polynômes 

Arithmétique et algèbre

POLYNÔMES

Introduction

Propriétés

Division

Divisibilité

Unitaire

Exercices

Ex. de divisions

 

Polynômes irréductibles

 

Faites un double-clic pour un retour en haut de page

 

 

Polynômes irréductibles sur Fp

Corps finis

 

Où il est question de factorisation des polynômes comme on réalise la factorisation des  nombres entiers. Comme il existe des nombres premiers, il existe des polynômes "premiers" dits polynômes irréductibles.

Les applications sont nombreuses notamment en cryptologie. On s'intéresse alors à certains polynômes définis dans un certain cadre dit corps de Galois ou corps finis.

Comme avec les congruences, on transforme le monde infini des nombres en un monde fini, avec ces mêmes congruences on crée un monde fini de polynômes.

 

 

Sommaire de cette page

>>> Approche

>>> Polynômes dans F2

>>> Polynômes irréductibles dans F2 

>>> Exercice

>>> Formule de Gauss

>>> Irréductibles sur F3

 

Débutants

Technique de base

de l'algèbre

 

Glossaire

Polynômes

Anglais: irreductible polynomial: a polynomial that cannot be factored into the product of two non-constant polynomials.

 

 

Approche – Factorisations

haut

 

La factorisation du polynôme x² + 1 n'est pas réalisable dans le domaine des nombres réels car il n'existe pas de nombres réels tels que (x – a) (x – b) = x² + 1.

 

Elle est possible dans le domaine des complexes et les racines sont +i et –i . C'est d'ailleurs un des intérêts des nombres complexes.

 

Dans le domaine F2 , on a cette égalité inattendue: x² + 1 = (x + 1)².
Dans ce domaine F2, où on compte en binaire, on a, en effet: 2 = 0.

 

Exemple

 

 

 

D'une manière générale

 

 

*      Les polynômes du premier degré sont toujours irréductibles.

*      Dans seuls les polynômes du premier degré sont irréductibles

*      Dans , les polynômes irréductibles sont les polynômes du premier degré et les polynômes du deuxième degré de discriminant strictement négatif.

 

Domaine F2

À ce niveau d'explications, sachons seulement que ce domaine F2 concerne les polynômes dont les coefficients sont 0 ou 1, seulement (des polynômes dont les coefficients sont calculés en mod 2).

En présence d'opérations sur ces coefficients, on les traitera comme en binaire sur un seul bit.   Ainsi:     1 + 1 = 0.

La définition de ces domaines en F2, F3, Fp (avec p premier) viendra plus loin.

 

 

Polynômes dans F2 ou GF[2]

haut

 

Premier degré

Avec des coefficients 0 ou 1, le coefficient de x étant nécessairement 1 (premier degré), on a  deux polynômes du premier degré dans F2 :

 

x et x + 1

 

Deuxième degré

Avec le même principe, le tableau montre l'existence de quatre polynômes du deuxième degré dans F2 :

 

x², x² + 1, x² + x et x² + x + 1

 

Troisième degré

Dans ce cas, ils sont huit (8 = 23).

Il y en aura seize pour le quatrième degré (16 = 24).

Etc.

 

 

Factorisation dans F2

haut

 

Méthode

L'idée consiste à lister les polynômes un par un et à éliminer tous ceux qui sont des produits de polynômes.

 

Prenons l'exemple paradoxal de

x² + 1 = (x + 1)² dans F2.

 

Les racines possibles sont 0 ou 1. On teste simplement si la fonction prend la valeur 0  pour une de ces valeurs.

Si oui, cette valeur est une racine.

 

Si la racine est nulle, la factorisation est évidente.

Sinon le polynôme facteur est (x + 1). L'autre  polynôme résulte de la division.

 

 

 

Recherche de racines

Avec x = 0 => x² + 1 = 0 + 1 = 1 => ce n'est pas une racine.

Avec x = 1 => x² + 1 = 1 + 1 = 2 = 0 => c'est une racine.

 

Factorisation

On divise x² + 1 par x + 1 et on trouve x + 1.

En effet: (x + 1)² = x² + 2x + 1 = x² + 0x + 1 = x² + 1

Car dans F2 (monde binaire): 1 + 1 = 2 = 0.

(on dit aussi: 2 mod 2 = 0)

 

Division posée

 

 

 

Polynômes irréductibles sur F2

haut

 

 

Degré 1, 2 et 3

Le tableau montre, en colonne 1, la liste de tous les polynômes du premier, deuxième et troisième degré dans F2.

 

La colonne 2 indique les possibilités de racines (oui, si f(x) = 0).

 

La colonne 3 donne la factorisation lorsqu'elle est possible.

 

Trouver la factorisation par x est assez immédiate.

 

Dans le cas où ni f(0) ni f(1) n'est nul, alors le polynôme est irréductible.

 

Il y a un seul polynôme irréductible pour le deuxième degré et deux pour le troisième.

 

 

 

 

 

 

Degré 4

Le tableau montre les trois polynômes irréductibles dans F2.

 

Les treize autres sont  réductibles ou factorisables.

 

Avec le quatrième degré, il est possible que les deux facteurs soient du deuxième degré. Le test avec f(1) ne suffit plus.

 

C'est le cas pour x4 + x2 + 1.

 

 

Exercice

haut

 

Problème

Montrer que ce polynôme est irréductible dans F2.

 

 

avec

 

 

Calculs préliminaires utiles

 

Solution

S'agissant d'un polynôme du troisième degré, les polynômes facteurs seront du premier et du deuxième degré.

 

 

Avec un facteur du premier degré, il suffit de montrer que f(x) n'est pas nul pour chacune des valeurs possibles.

 

Ce qui est le cas. La fonction f(x) est irréductible dans F2.

 

 

 


 

 

 

 

Corps finis

Le domaine en F2, généralisé en Fp (avec p premier) est un corps fini ou corps de Galois (finite field or Galois field) , noté aussi GF(p).

L'ensemble GF(p) comprend tous les polynômes dont les coefficients sont calculés mod p.

Dans GF(2) le polynôme x² + x + 1 est irréductible, alors que x² + 1 l'est.
En effet: (x + 1) (x + 1) = x² + 2x + 1 ≡ x² + 1 mod 2.

Le nombre premier p est nommé caractéristique du corps.

 

 

Formule de Gauss

haut

 

Formule

Gauss a trouvé une belle formule pour donner la quantité de polynômes irréductibles.

 

Il s'agit d'un corps fini de p éléments.

Pour les polynômes de degré n.

      d sont tous les diviseurs de n.

 et µ  est la fonction de Moebius.

 

 

Exemple

Dans F2 pour le quatrième degré.

On a trouvé trois polynômes irréductibles.

 

Le calcul de la formule confirme cette valeur.

 

 

 

 

 

Irréductibles sur F3 ou GF[3]

haut

 

 

 

Premier degré

 

 

 

 

Deuxième degré

 

En général, seuls les polynômes de coefficients 1 pour x² sont considérés (polynômes unaires).

 

Dans le cas d'un coefficient autre pour x², un polynôme avec ce coefficient en facteur est considéré comme réductible.  

 

 

 

Calcul

Dans F3 pour le deuxième degré.

On a trouvé trois polynômes irréductibles unaires (Tableau du haut).

 

Le calcul de la formule confirme cette valeur.

 

 

 

 

 

 

 

 

Haut de page (ou double-clic)

 

 

Voir

*      PolynômesIndex

*      Factorisation du polynôme du second degré

*       Théorème de Kronecker sur les polynômes unitaires

Sites

*       Arithmétique dans K[X] – Cours d'université Bordeaux – 2004

*       Arithmétique sur K[X] – Pierre-Alain Fouque – 2020

*       Arithmétique des polynômes – Éric Jourdain

*       Corps finis – Wikipédia

*       Finite field – Wolfram MathWorld

*       Irreductible polynomial – Wikipedia

*       Primitive Polynomials for the Field GF(3) – Degree 2 to 11 – Peter Maurer – Liste

Cette page

http://villemin.gerard.free.fr/aMaths/Polynome/PolyIrre.htm