Factorisation polynomiale dans un champ fini
Le calculateur trouve les facteurs d'un polynôme en utilisant l'algorithme de Cantor-Zassenhaus
Ce contenu est sous License Creative Commons Attribution/Partage à l'Identique 3.0(Unported). Cela signifie que vous pouvez redistribuer ou modifier librement ce contenu avec les mêmes modalités de licence et que vous devez créditer l'auteur original en plaçant un lien hypertexte de votre site vers l'œuvre https://fr.planetcalc.com/8372/. Vous ne pouvez pas modifier (le cas échéant) les références dans le contenu de l'œuvre originale.
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
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
commentaires