Factorisation polynomiale modulo p

Ce calculateur trouve les facteur irréductibles d'un polynôme donné modulo p en utilisant l'algorithme d'Elwyn Berlekamp. La description de l'algorithme est juste en dessous du calculateur.

Factorisation polynomiale de Berlekamp

Coefficients polynomiaux entiers

Module

Calculer

Polynôme saisi

$x^{9}+7x^{8}+x^{7}+7x^{6}+10x^{5}+2x^{4}+6x^{2}+9x+4$

Solution

$\displaystyle{\left(x+7\right)\left(x^{3}+8x^{2}+4x+12\right)\left(x^{4}+2x^{3}+3x^{2}+4x+6\right)\left(x+3\right)}$

Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.

Télécharger 



Facteurs

Facteur	Exposant
$x+7$	1
$x^{3}+8x^{2}+4x+12$	1
$x^{4}+2x^{3}+3x^{2}+4x+6$	1
$x+3$	1
objets par page: 5102050100200500100010K100Ktout 1 - 4 sur 4

 Lien  sauvegarder  Widget

Algorithme de factorisation de Berlekamp

L'algorithme décrit ici est une compilation compacte de l'algorithme de factorisation décrit dans TAOCP vol 2 de D.Knuth ¹.

Données initiales

• u(x) - polynôme de degré, n>=2
• p - nombre premier du module

Etapes de préparation

• Vérifier que le polynôme est monique, sinon diviser tous les coefficients polynomiaux par le coefficient u_n
  du plus haut degré
• Vérifier que le polynôme est sans carré en utilisant la Factorisation Polynomiale sans carré en champ fini
• Pour chaque facteur polynomial sans carré de degré 2 ou plus, lancer l'algorithme ci-dessous

L'algorithme

• Trouver la matrice Q (n * n ), où n est un degré polynomial suivant la procédure ci-dessous:
  • Initialiser un vecteur A (a₀, a₁ ... a_n-1) = 1,0...0
  • Initialiser la première ligne de la matrice Q (q_0,0, q_0,1 ... q_0,n-1) avec 0,0...0
  • La boucle sur i = 1..n-1 réalise l'action suivante
    • La boucle sur k = 1..n-1 réalise l'action suivante
      • Définir = a_n-1
      • La boucle sur j = n-1 .. 0 réalise l'action suivante
        • a_j=a_j-1-t*u_j, suppose que a_-1 = 0
    • Fixer la ligne i de la ligne Q au vecteur A
    • Soustraire 1 de l'élément q_i,i de la matrice Q
• Trouver les vecteurs linéaires indépendants v^[1] ... v^[r], tels que v^[1] Q = v^[2] Q = ... v^[r] Q = (0,0...0)
  • Fixer tous les éléments du vecteurs C de n éléments à -1 : c₀ = c₁ = .. = c_{n-1 = -1}
  • Fixer r = 0
  • La boucle sur k = 0 ... n-1 réalise l'action suivante
    • La boucle j = 0 ... n-1 réalise l'action suivante
      • if q_k,j ≠ 0 and c_j<0
        • Fixer a = q_k,j
        • Multiplier la colonne j de la matrice Q par -1/a
        • Ajouter la colone (i ≠ j) j fois q_k,i à chaque autre colonne
      • sinon (si q_k,j=0 ou c_j égal à 0 ou supérieur à 0)
        • Fixer r = r + 1
        • Fixer chaque élément i d'un nouveau vecteur v^[r] de n éléments à l'une des trois valeurs suivantes :
          • a_k,s, si s élément s trouvés dans le vecteur C, tels que c_s = i
          • 1, si i = k
          • 0 - sinon
• Trouver les facteurs r du polynôme u(x) en utilisant les vecteurs v^[2] ... v^[r]
  • Trouver tous les w_i = gcd(u(x),v^[2]-s) ≠ 1 pour chaque s = 0 ... p
  • Si le nombre de w < r réaliser l'action suivante
  • La boucle sur j=3 ... r opère jusqu'à ce que w < r
    • Remplacer w_i par les facteurs trouvés par le pgcd (v^[j]-s,w_i) ≠ 1 pour chaque s = 0 ... p