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

 

Solution

 

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

Télécharger 

 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