Factorisation polynomiale dans un champ fini

Le calculateur trouve les facteurs d'un polynôme en utilisant l'algorithme de Cantor-Zassenhaus

Ce calculateur trouve les facteurs irréductibles d'un polynôme univarié dans un champ fini en utilisant l'algorithme de Cantor-Zassenhaus. Initialement, il réalisé la Factorisation de degré distinct pour trouver les facteurs qui peuvent être décomposés davantage. Finalement, si nécessaire, il applique un algorithme de factorisation de degré égal décrit juste en-dessous du calculateur.

PLANETCALC, Factorisation polynomiale Cantor-Zassenhaus dans un champ fini

Factorisation polynomiale Cantor-Zassenhaus dans un champ fini

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

Algorithme de factorisation de Cantor-Zassenhaus

Cet algorithme a généralement de meilleures caractéristiques pour les grands modules que l'algorithme de factorisation de Berlecamp similaire.

  • Vérifier si le polynôme est sans carré
  • Trouver tous les facteurs pour les degrés distincts
  • Appliquer l'algorithme de décomposition de degré égal, décrit ci-dessous, pour chaque facteur avec un degré supérieur au degré distinct obtenu dans l'étape précédente

Algorithme de factorisation de degré égale

// u(x) - Input polynomial of degree rd 
//    qui a r facteurs chacun
//    de degré d dans le champ Fp
// p - ordre impair des champs
// d - degré des facteurs cibles
// r - nombre de facteurs cibles
s⟵ { u }
loop while size(s) less than r
        h ⟵ random polynomial 
                  of degree less than 2d
        g ⟵ h^(p^d-1/2) -1 mod u
        for each a in s do 
              if deg(a) greater than d 
                    and gcd(g, a) ≠ 1 
                    and gcd(g, a) ≠ a then
                       remove a from s
                       add gcd(g,a) to s
                       add a/gcd(g,a) to s
              end if
         end do
end loop
output s
URL copiée dans le presse-papiers
PLANETCALC, Factorisation polynomiale dans un champ fini

commentaires