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

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

Solution

$\displaystyle{\left(x+3\right)\left(x+7\right)\left(x^{3}+8x^{2}+4x+12\right)\left(x^{4}+2x^{3}+3x^{2}+4x+6\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+3$	1
$x+7$	1
$x^{3}+8x^{2}+4x+12$	1
$x^{4}+2x^{3}+3x^{2}+4x+6$	1
objets par page: 5102050100200500100010K100Ktout 1 - 4 sur 4

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

Télécharger 



Détails

Description	Détails mathématiques

 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