Factorisation polynomiale modulo p

Le calculateur trouve les facteurs polynomiaux modulo p en utilisant l'algorithme d'Elwyn Berlekamp

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.

PLANETCALC, Factorisation polynomiale de Berlekamp

Factorisation polynomiale de Berlekamp

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

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 1.

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 un
    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 (a0, a1 ... an-1) = 1,0...0
    • Initialiser la première ligne de la matrice Q (q0,0, q0,1 ... q0,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 = an-1
        • La boucle sur j = n-1 .. 0 réalise l'action suivante
          • aj=aj-1-t*uj, suppose que a-1 = 0
      • Fixer la ligne i de la ligne Q au vecteur A
      • Soustraire 1 de l'élément qi,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 : c0 = c1 = .. = cn-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 qk,j ≠ 0 and cj<0
          • Fixer a = qk,j
          • Multiplier la colonne j de la matrice Q par -1/a
          • Ajouter la colone (i ≠ j) j fois qk,i à chaque autre colonne
        • sinon (si qk,j=0 ou cj é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 :
            • ak,s, si s élément s trouvés dans le vecteur C, tels que cs = 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 wi = 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 wi par les facteurs trouvés par le pgcd (v[j]-s,wi) ≠ 1 pour chaque s = 0 ... p


  1. D.Knuth L'art de la programmation informatique vol 2, par. 4.6.2 Factorisation des Polynômes 

URL copiée dans le presse-papiers
PLANETCALC, Factorisation polynomiale modulo p

commentaires