Factorisation de polynômes

Le calculateur trouve tous les facteurs d'un polynôme avec des coefficients rationnels

Le calculateur ci-dessous trouve tous les facteurs irréductibles d'un polynôme avec des coefficients rationnels. Pour mieux comprendre comment il fonctionne, activez 'Montrer les détails' et lisez la description du calculateur.

PLANETCALC, Factorisation polynomiale avec des coefficients rationnels

Factorisation polynomiale avec des coefficients rationnels

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.

Procédure de factorisation de polynômes rationnels1

  • Convertir le polynôme saisi en Q[x] en un polynôme primitif en Z[x]
  • Trouver tous les facteurs carrés en utilisant l'Algorithme de factorisation sans carré de Yun
  • Pour chaque facteur sans carré de degré supérieur à 1, faire les étapes suivantes
    • Si le coefficient directeur n'est pas égal à 1, alors le transformer en monique, en utilisant la formule :
      v = a_n^{n-1}u(y/a_n)=\sum_{i=0}^{n-1} a_n^{n-1-i}a_iy^i+y^n, où
      v(y) - polynôme monique transformé,
      u(x) - polynôme d'origine,
      an - coefficient directeur de u(x),
      x = any
    • Trouver les facteurs irréductibles de v(y)=v1v2...vr dans un champ fini Fp[x]
      • Trouver le nombre premier minimal qui n'est pas un diviseur du discriminant v(y)
    • Utiliser le levage de Hensel pour élever l'odrre de champ fini de la factorisation à la limite supérieure
      • Déterminer la limite supérieur des coefficients des facteurs cibles avec la formule :
        B=2^n\sqrt{n+i}||v||, où
        ||v||=max({|a_n|,...,|a_0|}) - valeur absolue maximale des coefficients polynomiaux (hauteur polynômiale)
      • Réaliser le levade de Hensel k\geq \frac{ln(2B)}{ln(p)} fois
    • Vérifier les facteurs en divisant v(y)/vi dans Z[x], éliminer les facteurs invalides
    • Inverser la transformation polynômiale monique en utilisant la formule :
      u(x)=pp(v_1(a_nx))pp(v_2(a_nx))...pp(v_r(a_nx))
      pp - fonction à partie primitive, qui élimine une forme contenue d'un polynôme saisi

  1. Joel S. Cohen, Algèbre informatique et calcul symbolique : Méthodes Mathématiques, par. 9. Factorisation de polynômes 

  2. Donald Knuth, L'art de la programmation informatique vol.2, par. 4.6.2 Factorisation de polynômes 

URL copiée dans le presse-papiers
PLANETCALC, Factorisation de polynômes

commentaires