En matemáticas e álxebra informática a factorización dun polinomio consiste en descompoñelo nun produto de factores irredutíbeis. Esta descomposición é teoricamente posíbel e é única para polinomios con coeficientes en calquera corpo, pero son necesarias restricións fortes no corpo dos coeficientes para permitir o cálculo da factorización por medio dun algoritmo. Na práctica, os algoritmos foron deseñados só para polinomios con coeficientes nun corpo finito, no corpo dos racionais ou nunha extensión dun corpo finitamente xerada dun deles.

Todos os algoritmos de factorización, incluído o caso de polinomios multivariados sobre os números racionais, reducen o problema a este caso; ver factorización polinómica. Tamén se usa para varias aplicacións de corpos finitos, como a teoría da codificación (códigos de redundancia cíclica e códigos BCH), a criptografía (criptografía de clave pública mediante curvas elípticas) e a teoría computacional de números.

Como a redución da factorización de polinomios multivariados á de polinomios univariados non ten ningunha especificidade no caso dos coeficientes nun corpo finito, neste artigo só se consideran polinomios cunha variábel.

Fondo

Corpo finito Un corpo finito ou corpo de Galois é un corpo cunha orde finita (número de elementos). A orde dun corpo finito é sempre un primo ou unha potencia de primo. Para cada potencia de primo , existe exactamente un corpo finito con q elementos, ata isomorfismo. Este corpo denomínase GF(q) ou Fq. Se p é primo, GF(p) é o corpo primo de orde p; é o corpo das clases de residuos módulo p, e os seus p elementos denotanse 0, 1, ... , p -1.

Así, en GF(p) significa o mesmo que .

Polinomios irredutíbeis Sexa F un corpo finito. En canto aos corpos xerais, dise que un polinomio f non constante en F[x] é irredutíbel sobre F se non é o produto de dous polinomios de grao positivo. Un polinomio de grao positivo que non é irredutíbel sobre F chámase reducíbel sobre F.

Exemplo O polinomio é irredutíbel sobre Q mais non sobre calquera corpo finito.

En calquera extensión de corpo de F2, (ten eses catro factores e por tanto é reducíbel). En calquera outro corpo finito, polo menos un de −1, 2 e −2 é un cadrado, porque o produto de dous non cadrados é un cadrado e así temos

Se entón Se entón Se entón

Complexidade Nos algoritmos que seguen, as complexidades exprésanse en termos de número de operacións aritméticas en Fq, utilizando algoritmos clásicos para a aritmética de polinomios.

Algoritmos de factorización Moitos algoritmos para factorizar polinomios sobre corpos finitos inclúen as seguintes tres etapas:

Factorización libre de cadrados Factorización de graos distintos Factorización de igual grao

Unha excepción importante é o algoritmo de Berlekamp, que combina as etapas 2 e 3.

Factorización libre de cadrados O algoritmo determina unha factorización sen cadrados para polinomios cuxos coeficientes proveñen do corpo finito Fq de orde con p un primo. Este algoritmo determina primeiro a derivada e despois calcula o mcd do polinomio e a súa derivada. Se non é un, entón o mcd divíde de novo ao polinomio orixinal, sempre que a derivada non sexa cero (un caso que existe para polinomios non constantes definidos sobre corpos finitos).

Este algoritmo utiliza o feito de que, se a derivada dun polinomio é cero, entón é un polinomio en xp, que é, se os coeficientes pertencen a Fp, a p-ésima potencia do polinomio que se obtén substituíndo x por x1/ p. Se os coeficientes non pertencen a Fp, a raíz p-ésima dun polinomio de derivada cero obtense mediante a mesma substitución en x, completada aplicando aos coeficientes a inversa do automorfismo de Frobenius . Algoritmo : SFF (factorización libre de cadrados) Entrada : Un polinomio mónico f en Fq[x] onde q = pm Saída : factorización sen cadrados de f R ← 1

# Fai que w sexa o produto (sen multiplicidade) de todos os factores de f que teñen # multiplicidade non divisíbel por p c ← mcd (f, f′) w ← f/c

# Paso 1: Identifica todos os factores en w i ← 1 while w ≠ 1 do y ← mcd (w, c) fac ← w/y R ← R·faci w ← y; c ← c/y; i ← i + 1 end while # c é agora o produto (con multiplicidade) dos restantes factores de f

# Paso 2: identifica todos os factores restantes mediante a recursividade # Teña en conta que estes son os factores de f que teñen multiplicidade divisíbel por p if c ≠ 1 then c ← c1/p R ← R·SFF(c)p end if

Saída (R)

Exemplo de factorización sen cadrados Temos que factorizar

sobre o corpo con tres elementos.

O algoritmo calcula primeiro

Dado que a derivada é distinta de cero, temos e entramos no bucle while.

Despois dun bucle temos , e con actualizacións , e .

A segunda vez a través do bucle dá , , , con actualizacións , e .

A terceira vez a través do bucle tampouco non muda . Por cuarta vez a través do bucle obtemos , , , con actualizacións , e .

Dado que w = 1, saímos do bucle while. Dado que , debe ser un cubo perfecto. A raíz cúbica de , obtida ao substituír por é , e chamar recursivamente ao procedemento libre de cadrados determina que é libre de cadrados. Polo tanto, elevándoo ao cubo e combinándoo co valor de ata ese punto dáse a descomposición sen cadrados.

Factorización de graos distintos Este algoritmo separa un polinomio libre de cadrados nun produto de polinomios cuxos factores irredutíbeis teñen todos o mesmo grao. Sexa de grao o polinomio a factorizar. Algoritmo Factorización de graos distintos (DDF) Entrada : un polinomio mónico libre de cadrados Saída : o conxunto de todos os pares , tal que ten un factor irredutíbel de grao e é o produto de todos os factores irredutíbeis mónicos de de grao . Begin

while do

if then

end if

end while; if , entón ; if , entón devolve , else return End

Factorización de igual grao

Algoritmo de Cantor-Zassenhaus Nesta sección, consideramos a factorización dun polinomio univariado mónico libre de cadrados f, de grao n, sobre un corpo finito Fq, que ten factores irredutíbeis distintos por pares. cada un de grao d.

Describimos primeiro un algoritmo de Cantor e Zassenhaus (1981) e despois unha variante que ten unha complexidade lixeiramente mellor.

Ambos os dous son algoritmos probabilísticos cuxo tempo de execución depende de opcións aleatorias (algoritmos Las Vegas) e teñen un bo tempo medio de execución. Na seguinte sección describimos un algoritmo de Shoup (1990), que tamén é un algoritmo de factorización de igual grao, pero é determinista. Todos estes algoritmos requiren unha orde impar q para o corpo dos coeficientes. Para máis algoritmos de factorización consulte, por exemplo, o libro de Knuth The Art of Computer Programming, volume 2. Algoritmo Algoritmo Cantor–Zassenhaus. Entrada: un corpo finito Fq de orde impar q. Un polinomio libre de cadrados mónico f en Fq[x] de grao n = rd, que ten r ≥ 2 factores irredutíbeis cada un de grao d Saída: O conxunto de factores irredutíbeis mónicos de f.

Factores := {f}; while Tamaño(Factores) < r do, Escolle h en Fq[x] con deg( h ) < n ao chou;

for each u in Factores con deg(u) > d do if mcd(g, u) ≠ 1 e mcd(g, u) ≠ u then Factores:= Factorizar ; endif endwhile

return Factores Demostrouse que o número medio de iteracións do bucle while do algoritmo é menor que , dando un número medio de operacións aritméticas en Fq que é .

No caso típico onde d log( q ) > n, esta complexidade pódese reducir a

escollendo h no kernel do mapa linear

e substituíndo a instrución

por

Algoritmo de Victor Shoup Como os algoritmos da sección anterior, o algoritmo de Victor Shoup é un algoritmo de factorización de igual grao. A diferenza deles, é un algoritmo determinista. No entanto, é menos eficiente, na práctica, que os algoritmos da sección anterior. Para o algoritmo de Shoup, a entrada está restrinxida a polinomios sobre corpos primos Fp.

Sexa g = g1 ... gk a factorización desexada, onde os gi son polinomios mónicos irredutíbeis distintos de grao d . Sexa n = deg( g ) = kd. Consideramos o anel R = Fq[x]/g e denotamos tamén por x a imaxe de x en R.

O anel R é o produto directo dos corpos Ri = Fq [x]/gi, e denotamos por pi o homomorfismo natural de R en Ri. O grupo de Galois de Ri sobre Fq é cíclico de orde d, xerado polo automorfismo de corpos u → up. Dedúcese que as raíces de gi en Ri son

Como no algoritmo anterior, este algoritmo usa a mesma subálxebra B de R que o algoritmo de Berlekamp, ás veces chamada "subálxebra de Berlekamp" e definida como

Un subconxunto S de B dise conxunto separador se, para cada 1 ≤ i < j ≤ k existe s ∈ S tal que . No algoritmo anterior, constrúese un conxunto separador escollendo ao azar os elementos de S. No algoritmo de Shoup, o conxunto separador constrúese do seguinte xeito. Sexa s en R [Y ] tal que

Daquela é un conxunto separador porque para i = 1,... , k (os dous polinomios mónicos teñen as mesmas raíces). Como os gi son distintos por pares, para cada par de índices distintos (i, j), polo menos un dos coeficientes sh satisfará

Tendo un conxunto separador, o algoritmo de Shoup procede como o último algoritmo da sección anterior, simplemente substituíndo a instrución "escolle h aleatoriamente no kernel do mapa linear". " por "escolla h + i con h en S e i en {1, ..., k −1}".

Test de irredutibilidade de Rabin Do mesmo xeito que o algoritmo de factorización de graos distintos, o algoritmo de Rabin baséase no lema indicado anteriormente. O algoritmo de factorización de graos distintos proba todo d non superior á metade do grao do polinomio de entrada. O algoritmo de Rabin aproveita que os factores non son necesarios para considerar menos d. En caso contrario, é semellante ao algoritmo de factorización de graos distintos. Baséase no seguinte feito.

Sexan p1 ,... , pk, todos os divisores primos de n, e denotamos , para 1 ≤ i ≤ k polinomio f en Fq[x] de grao n é irredutibel en Fq[x] se e só se , para 1 ≤ i ≤ k, e f divide . De feito, se f ten un factor de grao que non divide n, entón f non divide ; se f ten un factor de grao que divide n, entón este factor divide polo menos un dos Algoritmo test de Irredutibilidade de Rabin Entrada : un polinomio mónico f en Fq[x] de grao n, p1 ,... , pk todos os divisores primos distintos de n. Saída : "f é irredutíbel" ou " f é reducíbel".

for j = 1 to k do

for i = 1 to k do

g := mcd( f, h ); if g ≠ 1 then return "f é reducíbel" e FIN; end for;

if g = 0, then return "f é irredutíbel", else return "f é reducíbel" A idea básica deste algoritmo é calcular comezando polo máis pequeno mediante o cadrado repetido ou usando o automorfismo de Frobenius, e despois tomar o mcd correspondente. Usando a aritmética polinómica elemental, o cálculo da matriz do automorfismo de Frobenius precisa operacións en Fq, o cálculo de

precisa O (n3) operacións adicionais, e o propio algoritmo precisa O (kn2) operacións, dando un total de operacións en Fq.

Notas

Véxase tamén

Bibliografía Kempfert, H (1969) On the Factorization of Polynomials Department of Mathematics, The Ohio State University, Columbus, Ohio 43210 Shoup, Victor (1996) Smoothness and Factoring Polynomials over Finite Fields Computer Science Department University of Toronto Von Zur Gathen, J.; Panario, D. (2001). Factoring Polynomials Over Finite Fields: A Survey. Journal of Symbolic Computation, Volume 31, Issues 1–2, January 2001, 3--17. Gao Shuhong, Panario Daniel,Test and Construction of Irreducible Polynomials over Finite Fields Department of mathematical Sciences, Clemson University, South Carolina, 29634–1907, USA. and Department of computer science University of Toronto, Canada M5S-1A4 Shoup, Victor (1989) New Algorithms for Finding Irreducible Polynomials over Finite Fields Computer Science Department University of Wisconsin–Madison Geddes, Keith O.; Czapor, Stephen R.; Labahn, George (1992). Algorithms for computer algebra. Boston, MA: Kluwer Academic Publishers. pp. xxii+585. .

Outros artigos Factorización de polinomios