Factorización de polinomios sobre corpos finitos

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
 Ligazóns externas 
 Algúns polinomios irredutíbeis 
 Teoria de corpos e de Galois
 corpo de Galois 
  factorización de polinomios sobre corpos finitos 

Categoría:Criptografía
Categoría:Álxebra
Categoría:Polinomios
Categoría:Wikipedia:Páxinas con traducións non revisadas