Factorisation polynomiale dans un champ fini

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.

Factorisation polynomiale Cantor-Zassenhaus dans un champ fini

Coefficients polynomiaux entiers

Module

Montrer les détails

Calculer

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.

Télécharger 

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