Factorització dels polinomis: diferència entre les revisions
Contingut suprimit Contingut afegit
m Corregit: segons las [[fórmules > segons les [[fórmules |
m Corregit: - és possible ja + és possible, ja |
||
Línia 141:
En el cas dels polinomis amb coeficients a cossos finits, per a un polinomi fixat, no existeix més que un nombre finit de divisors potencials, els polinomis de grau inferior. Un algorisme ingenu consisteix doncs a factoritzar un polinomi provant la seva divisibilitat pels polinomis de grau inferior, de manera anàloga a l'algorisme ingenu de divisió dels enters. Tanmateix, existeixen algorismes força més eficaços. Han estat descoberts entre la fi dels anys 1960 i el començament dels anys 1980, i són de complexitat polinòmica, determinista o probabilista, per exemple l'[[algorisme de Berlekamp]], o el de [[algorisme de Cantor-Zassenhaus|Cantor-Zassenhaus]].
De la factorització polinomis amb coeficients als cossos finits es dedueixen dels algorismes de factorització en altres dominis. En principi per als polinomis dels quals els coeficients són [[nombres p-adics]], amb la restricció, com en el cas dels coeficients reals i complexos, que no es pot obtenir en tant que finit més que un nombre finit de termes d'un desenvolupament p-adic (els factors irreductibles poden ser de qualsevol grau, i no només de grau 1 o 2 com en els casos reals i complexos). Això es pot fer gràcies a una versió algorísmica del [[lema de Hensel]]. Llavors, per als polinomis amb coeficients racionals, o en cossos de nombres. El pas d'una factorització en l'àmbit dels coeficients p-adics a una factorització amb coeficients racionals és possible, ja que la segona s'obté reagrupant convenientment els factors de la primera. És possible de provar totes aquestes combinacions, el que pot ser de complexitat algorítmica exponencial, o bé transformr aquest problema a un problema algorísmic d'àlgebra lineal de tipus [[problema de la motxilla]]. Aquests algorismes encara estan sent millorats als començaments dels anys 2000 (veure [[algorisme de Van Hoeij]]).
Finalment, aconseguir la factorització dels polinomis amb coeficients sencers és equivalent algorísmicament a aconseguir conjuntament factoritzar els enters i els polinomis amb coeficients racionals.
| |||