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  (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 **F***q*. 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 **F**2,   (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 -1=a^2, entón P=(x^2+a)(x^2-a).
# Se 2=b^2, entón P=(x^2+bx+1)(x^2-bx+1).
# Se -2=c^2, entón P=(x^2+cx-1)(x^2-cx-1).

### Complexidade 
Nos algoritmos que seguen, as complexidades exprésanse en termos de número de operacións aritméticas en **F***q*, 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 **F***q* 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 *x**p*, que é, se os coeficientes pertencen a **F***p*, a *p*-ésima potencia do polinomio que se obtén substituíndo *x* por *x*1/ *p*. Se os coeficientes non pertencen a **F***p*, 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 **F***q*[*x*] onde *q* = *p**m*
   **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*&#x2032;)
   *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*·*fac**i*
     *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* ← *c*1/*p*
     *R* ← *R*·**SFF**(*c*)*p*
   **end if** 
   
   **Saída** (*R*)

#### Exemplo de factorización sen cadrados 
Temos que factorizar

:  f = x^{11} + 2 x^9 + 2x^8 + x^6 + x^5 + 2x^3 + 2x^2 +1 \in \mathbf{F}_3[x],

sobre o corpo con tres elementos.

O algoritmo calcula primeiro

:  c = \gcd(f, f') = x^9 + 2x^6 + x^3 + 2.

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.

:  f= (x+1)(x^2+1)^3(x+2)^4.

### 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**
     i:=1;\qquad S:=\emptyset,\qquad f^*:=f;
     **while** \deg f^*\ge 2i **do** 
       g=\gcd(f^*, x^{q^i}-x)
       **if**  **then**
         S:=S\cup\{(g,i)\} ;
         f^*:=f^*/g
       **end if**
       
     **end while**;
     **if** f^*\ne 1, **entón** S:= S\cup\{(f^*,\deg f^*)\} ;
     **if** S=\emptyset, **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 **F***q*, que ten  factores irredutíbeis distintos por pares.  f_1,\ldots,f_r 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 **F***q* de orde impar *q*.
       Un polinomio libre de cadrados mónico *f* en **F***q*[*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) *q*[*x*] con deg( *h* ) g:=h^{\frac{q^d-1}{2}}- 1 \pmod f
     **for each** *u* i**n** Factores con deg(*u*) > *d* **do**
       **if** mcd(*g*, *u*) ≠ 1 e mcd(*g*, *u*) ≠ *u* **then**
         Factores:= Factorizar   \,\setminus\, \{u\}\cup\{(\gcd(g,u),u/\gcd(g,u))\};
       **endif**
   **endwhile**
 
   **return Factores**
Demostrouse que o número medio de iteracións do bucle while do algoritmo é menor que 2.5 \log_2 r, dando un número medio de operacións aritméticas en **F***q* que é O(dn^2\log(r)\log(q)).

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

: O(n^2(\log(r)\log(q)+n))

escollendo *h* no kernel do mapa linear

:  v \to v^q-v \pmod f

e substituíndo a instrución

: g:=h^{\frac{q^d-1}{2}}- 1 \pmod f

por

: g:=h^{\frac{q-1}{2}}- 1 \pmod f.

#### 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 **F***p*.

Sexa *g* = *g*1 ... *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* = **F***q*[*x*]/*g* e denotamos tamén por *x* a imaxe de *x* en *R*. 

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

:  p_i(x), p_i(x^q), p_i \left (x^{q^2} \right ), \ldots, p_i \left (x^{q^{d-1}} \right ).

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

: \begin{align}
B &= \left \{\alpha \in R \ : \ p_1(\alpha), \cdots, p_k(\alpha) \in \mathbf{F}_q \right \} \\
&= \{u\in R \ : \ u^q=u\}
\end{align}

Un subconxunto *S* de *B* dise conxunto separador se, para cada 1 ≤ *i* p_i(s) \ne p_j(s). 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

: \begin{align}
s&=(Y-x) \left (Y-x^q \right )\cdots \left (Y-x^{q^{d-1}} \right ) \\
&=s_0+\cdots+s_{d-1}Y^{d-1}+Y^d
\end{align}.

Daquela \{s_0,\dots ,s_{d-1}\} é un conxunto separador porque p_i(s)=g_i 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á p_i(s_h)\ne p_j(s_h).

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".  v \to v^q-v \pmod f " 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 *p*1 ,... , *pk*,  todos os divisores primos de *n*, e denotamos n/p_i=n_i, para 1 ≤ *i* ≤ *k* polinomio *f* en **F***q*[*x*] de grao *n* é irredutibel en **F***q*[*x*] se e só se  \gcd \left (f,x^{q^{n_i}}-x \right )=1, para 1 ≤ *i* ≤ *k*, e *f* divide x^{q^n}-x. De feito, se *f* ten un factor de grao que non divide *n*, entón *f* non divide x^{q^n}-x; se *f* ten un factor de grao que divide *n*, entón este factor divide polo menos un dos x^{q^{n_i}}-x.
 **Algoritmo** test de Irredutibilidade de Rabin
   **Entrada** : un polinomio mónico *f* en **F***q*[*x*] de grao *n*, 
     *p*1 ,... , *pk* todos os divisores primos distintos de *n*.
   **Saída** : "*f* é irredutíbel" ou " *f* é reducíbel".
 
   **for**  *j* = 1 **to** *k* **do** 
     n_j=n/p_j;
   **for** *i* = 1 **to** *k* **do** 
     h:=x^{q^{n_i}}-x \bmod f;
     *g* := mcd( *f*, *h* );
     **if** *g* ≠ 1 **then return** "*f* é reducíbel" **e FIN**;
   **end for**;
   g:= x^{q^{n}}-x \bmod f;
   **if** *g* = 0, **then return** "*f* é irredutíbel", 
     **else return** "*f* é reducíbel"
A idea básica deste algoritmo é calcular  x^{q^{n_i}} \bmod f comezando polo máis pequeno  n_1,\ldots,n_k 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 O(n^2 (n+\log q)) operacións en **F***q*, o cálculo de

: x^{q^{n_i}}-x \pmod f

precisa *O* (*n*3) operacións adicionais, e o propio algoritmo precisa *O* (*kn*2) operacións, dando un total de O(n^2 (n+\log q)) operacións en **F***q*.

## 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&ndash;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