Factorización de polinomios sobre cuerpos finitos
# Factorización de polinomios sobre cuerpos finitos

En matemáticas y cálculo simbólico la factorización de un polinomio consiste en descomponerlo en un producto de factores irreducibles. Esta descomposición es teóricamente posible y es única para polinomios con coeficientes en cualquier cuerpo, pero se necesitan restricciones bastante fuertes en el cuerpo de los coeficientes para permitir el cálculo de la factorización mediante un algoritmo. En la práctica, los algoritmos se han diseñado solo para polinomios con coeficientes en un cuerpo finito, en los números racionales o en una extensión de cuerpos de uno de ellos.

Todos los algoritmos de factorización, incluido el caso de los polinomios con múltiples variables sobre los números racionales, reducen el problema a este caso; véase factorización de polinomios. También se utiliza para diversas aplicaciones de cuerpos finitos, como la teoría de códigos (códigos de verificación de redundancia cíclica y el código BCH), criptografía (criptografía asimétrica mediante curvas elípticas) y teoría de números computacional.

Como la reducción de la factorización de polinomios a la de polinomios de una variable no tiene especificidad en el caso de coeficientes en un cuerpo finito, en este artículo solo se consideran polinomios con una variable.

## Antecedentes

### Cuerpo finito

La teoría de cuerpos finitos, cuyos orígenes se remontan a los trabajos de Carl Friedrich Gauss y Évariste Galois, ha jugado un importante papel en varias ramas de las matemáticas. Debido a la aplicabilidad del concepto en otros temas de matemáticas y ciencias como la informática, ha habido un resurgimiento del interés en los cuerpos finitos, lo que se debe en parte a importantes aplicaciones en teoría de códigos y criptografía. Las aplicaciones de cuerpos finitos introducen algunos de estos desarrollos en criptografía, cálculo simbólico y teoría de códigos.

Un cuerpo de Galois o cuerpo finito es un cuerpo con un orden finito (número de elementos). El orden de un cuerpo finito es siempre un número primo o una potencia de un número primo. Para cada potencia prima q = $p^r,$ existe exactamente un cuerpo finito con q elementos, salvo isomorfismo. Este cuerpo se indica como GF(q) o F $_q.$ Si p es primo, GF(p) es la característica de orden p; es el cuerpo de las clases de residuos respecto al módulo p, y sus elementos p se denotan 0, 1, ..., p-1. Así, a = b en GF(p) significa lo mismo que a ≡ b (mod p).

### Polinomios irreducibles

Sea F un cuerpo finito. En cuanto a los cuerpos generales, se dice que un polinomio no constante f en F[x] es irreducible sobre F si no es el producto de dos polinomios de grado positivo. Un polinomio de grado positivo que no es irreducible sobre F se llama reducible sobre F.

Los polinomios irreducibles permiten construir los cuerpos finitos de orden no primo. De hecho, para una potencia primaria q, sea $F_q$ el cuerpo finito con q elementos, únicos salvo por isomorfismos. Un polinomio f de grado n mayor que uno, que es irreducible sobre $F_q,$ define una extensión de cuerpo de grado n que es isomorfo al cuerpo con $q^n$ elementos, que son los polinomios de grado inferior a n; la suma, resta y multiplicación por un elemento de $F_q$ son los de los polinomios; el producto de dos elementos es el resto de la división por f de su producto como polinomios; el inverso de un elemento puede calcularse mediante el algoritmo MCD extendido (véase aritmética de extensiones algebraicas).

De ello se deduce que, para calcular en un cuerpo finito de orden no primo, es necesario generar un polinomio irreducible. Para ello, el método común es tomar un polinomio al azar y probar su irreducibilidad. En aras de la eficiencia de la multiplicación en el cuerpo, es habitual buscar polinomios de la forma $x^n$ + ax + b.

Los polinomios irreducibles sobre cuerpos finitos también son útiles para los generadores de números pseudoaleatorios que utilizan registros de desplazamiento de retroalimentación y logaritmos discretos sobre $F_{2n}.$

El número de polinomios mónicos irreducibles de grado n sobre $F_q$ es el número de collares aperiódicos, dado por la función de conteo de collares de Moreau $M_q(n).$ La función de collar estrechamente relacionada $N_q(n)$ cuenta los polinomios mónicos de grado n que son primarios (una potencia de un irreducible); o, alternativamente, polinomios irreducibles de todos los grados d que dividen a n.

### Ejemplo

El polinomio P = $x^4$ + 1 es irreducible sobre Q pero no sobre ningún cuerpo finito.

* En cualquier extensión de cuerpo de $F_2,$ P = (x + $1)^4.$
* En todos los demás cuerpos finitos, al menos uno de −1, 2 y −2 es un cuadrado, porque el producto de dos no cuadrados es un cuadrado, por lo que se tiene que
* Si $-1=a^{2},$ entonces $P=(x^{2}+a)(x^{2}-a).$
* Si $2=b^{2},$ entonces $P=(x^{2}+bx+1)(x^{2}-bx+1).$
* Si $-2=c^{2},$ entonces $P=(x^{2}+cx-1)(x^{2}-cx-1).$

### Complejidad

Los algoritmos de factorización polinomial utilizan operaciones polinomiales básicas como productos, divisiones, máximo común divisor (mcd), potencias de un polinomio con otro módulo, etc. Una multiplicación de dos polinomios de grado n como máximo se puede realizar en operaciones $O(n^2)$ en $F_q$ usando aritmética clásica, o en O con las operaciones (nlog(n) log (log (n))) en $F_q$ usando aritmética rápida. Se puede realizar una división euclídea (división con resto) en períodos de tiempo similares. La dificultad de obtener un máximo común divisor polinómico entre dos polinomios de grado como máximo n se puede tomar como operaciones $O(n^2)$ en $F_q$ usando métodos clásicos, o como $O(nlog^2(n)$ log(log(n))) operaciones en $F_q$ usando métodos rápidos. Para dos polinomios h y g de grado como máximo n, la exponenciación $h^q$ mod g se puede hacer con O(log(q)) productos polinómicos, usando el método de exponenciación binaria, es decir $O(n^2log(q))$ operaciones en $F_q$ usando métodos clásicos, o O(nlog(q) log(n) log(log (n))) operaciones en $F_q$ usando métodos rápidos.

En los algoritmos que siguen, las complejidades se expresan en términos de número de operaciones aritméticas en $F_q,$ utilizando algoritmos clásicos para la aritmética de polinomios.

## Algoritmos de factorización

Muchos algoritmos para factorizar polinomios sobre cuerpos finitos incluyen las siguientes tres etapas:

* Factorización libre de cuadrados
* Factorización en grados distintos
* Factorización de igual grado

Una excepción importante es el algoritmo de Berlekamp, que combina las etapas 2 y 3.

### Algoritmo de Berlekamp

El algoritmo de Berlekamp es históricamente importante por ser el primer algoritmo de factorización, que funciona bien en la práctica. Sin embargo, contiene un bucle en los elementos del cuerpo subyacente, lo que implica que es practicable solo en pequeños cuerpos finitos. Para un cuerpo subyacente fijo, su complejidad temporal es polinomial, pero, para cuerpos subyacentes generales, la complejidad es exponencial según el tamaño del cuerpo.

### Factorización libre de cuadrados

El algoritmo determina una factorización libre de cuadrados para polinomios cuyos coeficientes provienen del cuerpo finito $F_q$ de orden q = $p^m$ con p primo. Este algoritmo determina primero la derivada y luego calcula el mcd del polinomio y su derivada. Si no es uno, el mcd vuelve a dividir el polinomio original, siempre que la derivada no sea cero (un caso que existe para polinomios no constantes definidos sobre cuerpos finitos).

Este algoritmo utiliza el hecho de que, si la derivada de un polinomio es cero, entonces es un polinomio en $x^p,$ que es, si los coeficientes pertenecen a $F_p,$ la p potencia del polinomio obtenido al sustituir x por $x^{1/p}.$ Si los coeficientes no pertenecen a $F_p,$ la raíz p-ésima de un polinomio con derivada cero se obtiene mediante la misma sustitución en x, completada aplicando el inverso del automorfismo de Frobenius a los coeficientes.

Este algoritmo funciona también sobre un cuerpo de característica cero, con la única diferencia de que nunca entra en los bloques de instrucciones donde se calculan las p raíces. Sin embargo, en este caso, el algoritmo de Yun es mucho más eficiente porque calcula los máximos divisores comunes de polinomios de grados inferiores. Una consecuencia es que, al factorizar un polinomio sobre los enteros, no se utiliza el algoritmo que sigue: primero se calcula la factorización libre de cuadrados sobre los enteros, y para factorizar los polinomios resultantes, se elige un p tal que permanecen libres de cuadrados de módulo p.

La idea es identificar el producto de todos los factores irreducibles de f con la misma multiplicidad. Esto se hace en dos pasos. El primer paso usa la derivada formal de f para encontrar todos los factores con multiplicidad no divisible por p. El segundo paso identifica los factores restantes. Como todos los factores restantes tienen multiplicidad divisible por p, lo que significa que son potencias de p, simplemente se puede tomar la raíz cuadrada de p y aplicar la recursividad.

**Ejemplo de factorización libre de cuadrados**

Sea

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

que se desea factorizar sobre el cuerpo con tres elementos.

El algoritmo calcula primero

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

Dado que la derivada no es cero, se tiene que w = f/c = $x^2$ + 2 y se entra en el ciclo mientras. Después de un bucle se tiene que y = x + 2, z = x + 1 y R = x + 1 con actualizaciones i = 2, w = x + 2 y c = $x^8$ + $x^7$ + $x^6$ + $x^2+x+1.$ La segunda vez a través del ciclo resulta y = x + 2, z = 1, R = x + 1, con actualizaciones i = 3, w = x + 2 y c = $x^7$ + $2x^6$ + x + 2. La tercera vez a través del bucle tampoco cambia R. Pasando por cuarta vez a través del bucle se obtiene y = 1, z = x + 2, R = (x + 1)(x + $2)^4,$ con actualizaciones i = 5, w = 1 y c = $x^6$ + 1. Dado que w = 1, se sale del bucle mientras. Dado que c ≠ 1, debe ser un cubo perfecto, la raíz cúbica de c, obtenida al reemplazar $x^3$ por x es $x^2$ + 1, y llamar al procedimiento sin cuadrados determina de forma recursiva que el resultado está libre de cuadrados. Por lo tanto, dividirlo en un cubo y combinarlo con el valor de R hasta ese punto da la descomposición sin cuadrados

    $f=(x+1)(x^{2}+1)^{3}(x+2)^{4}.$

### Factorización de grados distintos

Este algoritmo divide un polinomio libre de cuadrados en un producto de polinomios cuyos factores irreducibles tienen todos el mismo grado. Sea f ∈ $F_q[x]$ de grado n el polinomio a factorizar.

La corrección del algoritmo se basa en lo siguiente:

       $x^{q^{i}}-x\in \mathbf {F} _{q}[x]$

A primera vista, este procedimiento no es eficiente, ya que implica calcular el MCD de polinomios de un grado que es exponencial con el grado del polinomio de entrada. Sin embargo

    $g={\text{mcd }}\left(f^{*},x^{q^{i}}-x\right)$

puede ser reemplazado por

    $g={\text{mcd }}\left(f^{*},\left(x^{q^{i}}-x\mod f^{*}\right)\right).$

Por lo tanto, se tiene que calcular:

    $x^{q^{i}}-x\mod f^{*},$

hay dos métodos:

       $x^{q^{i-1}}\mod f^{*}$
   calculado en el paso anterior y para calcular el módulo de la q-ésima potencia del nuevo f*, usando el método de exponenciación binaria. Para esto se necesitan
       $O\left(\log(q)\deg(f)^{2}\right)$
   operaciones aritméticas en $F_q$ en cada paso, y así
       $O\left(\log(q)\deg(f)^{3}\right)$
       $O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)$
   operaciones. Luego, en cada iteración del ciclo, se calcula el producto de una matriz por un vector (con $O(deg(f)^2$ operaciones). Esto induce un número total de operaciones en $F_q$ que es
       $O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).$

### Factorización de igual grado

**Algoritmo de Cantor-Zassenhaus**

En esta sección, se considera la factorización de un polinomio mónico de una variante libre de cuadrados f, de grado n, sobre un cuerpo finito $F_q,$ que tiene r ≥ 2 factores irreducibles distintos por pares $f_{1},\ldots ,f_{r}$ cada uno de grado d.

Primero se describe un algoritmo de Cantor y Zassenhaus (1981) y luego una variante que tiene una complejidad ligeramente mejor. Ambos son algoritmos probabilísticos cuyo tiempo de ejecución depende de elecciones aleatorias (algoritmo de Las Vegas) y tienen un buen tiempo de ejecución medio. En la siguiente sección se describe un algoritmo de Shoup (1990), que también es un algoritmo de factorización de igual grado, pero es determinista. Todos estos algoritmos requieren un orden impar q del cuerpo de coeficientes. Para obtener más algoritmos de factorización, consúltese por ejemplo el libro de Knuth The Art of Computer Programming volumen 2.

La exactitud de este algoritmo se basa en el hecho de que el anillo $F_q[x]/f$ es un producto directo de los cuerpos $F_q[x]/f_i$ donde $f_i$ se ejecuta en los factores irreductibles de f. Como todos estos cuerpos tienen $q^d$ elementos, el componente de g en cualquiera de estos cuerpos es cero con probabilidad

    ${\frac {q^{d}-1}{2q^{d}}}\sim {\tfrac {1}{2}}.$

Esto implica que el polinomio mcd (g, u) es el producto de los factores de g para los cuales el componente de g es cero.

Se ha demostrado que el número medio de iteraciones del bucle mientras del algoritmo es menor que $2.5\log _{2}r$, lo que da un número medio de operaciones aritméticas en $F_q$ que es $O(dn^{2}\log(r)\log(q))$.

En el caso típico cuando d log (q) > n, esta complejidad puede reducirse a

    $O(n^{2}(\log(r)\log(q)+n))$

eligiendo h en el núcleo de la aplicación lineal

    $v\to v^{q}-v{\pmod {f}}$

y reemplazando la instrucción

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

por

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

La prueba de validez es la misma que la anterior, reemplazando el producto directo de los cuerpos $F_q[x]/f_i$ por el producto directo de sus subcuerpos con q elementos. La complejidad se descompone en $O(n^{2}\log(r)\log(q))$ para el algoritmo en sí, $O(n^{2}(\log(q)+n))$ para el cálculo de la matriz de la aplicación lineal (que puede estar ya calculado en la factorización libre de cuadrados) y $O(n^3)$ para computar su núcleo. Cabe señalar que este algoritmo también funciona si los factores no tienen el mismo grado (en este caso, el número "r" de factores, necesario para detener el ciclo mientras, se encuentra como la dimensión del núcleo). Sin embargo, la complejidad es ligeramente mejor si se realiza la factorización sin cuadrados antes de usar este algoritmo (dado que n puede disminuir con la factorización sin cuadrados, esto reduce la complejidad de los pasos críticos).

**Algoritmo de Victor Shoup**

Como los algoritmos de la sección anterior, el algoritmo de Victor Shoup es un algoritmo de factorización de igual grado. A diferencia de ellos, es un algoritmo determinista. Sin embargo, es menos eficiente, en la práctica, que los algoritmos de la sección anterior. Para el algoritmo de Shoup, la entrada está restringida a polinomios sobre cuerpos primos F $_p.$

El peor caso de complejidad temporal del algoritmo de Shoup tiene un factor ${\sqrt {p}}.$. Aunque exponencial, esta complejidad es mucho mejor que la de los algoritmos deterministas anteriores (algoritmo de Berlekamp) que tienen como factor p. Sin embargo, hay muy pocos polinomios para los cuales el tiempo de cálculo es exponencial y la complejidad de tiempo promedio del algoritmo es polinomial en $d\log(p),$ donde d es el grado del polinomio y p es el número de elementos del cuerpo subyacente.

Sea g = $g_1$ ... $g_k$ la factorización deseada, donde $g_i$ son polinomios mónicos irreducibles distintos de grado d. Sea n = deg(g) = kd. Considérese el anillo R = $F_q[x]/g$ y se denota también por x la imagen de x en R. El anillo R es el producto directo de los cuerpos $R_i$ = $F_q[x]/g_i,$ y se denota por $p_i$ el homomorfismo natural de R sobre $R_i.$ El grupo de Galois de $R_i$ sobre $F_q$ es cíclico de orden d, generado por el automorfismo u → $u^p.$ De ello se deduce que las raíces de $g_i$ en $R_i$ son

    $p_{i}(x),p_{i}(x^{q}),p_{i}\left(x^{q^{2}}\right),p_{i}\left(x^{q^{d-1}}\right).$

Como en el algoritmo anterior, este algoritmo usa la misma subálgebra B sobre R que el algoritmo de Berlekamp, a veces denominada subálgebra de Berlekamp y definida como

    ${\begin{aligned}B&=\left\{\alpha \in R\ :\ p_{1}(\alpha ),\cdots ,p_{k}(\alpha )\in \mathbf {F} _{q}\right\}\\&=\{u\in R\ :\ u^{q}=u\}\end{aligned}}$

Un subconjunto S de B se dice un conjunto con separación si, por cada 1 ≤ i < j ≤ k existe un s ∈ S tal que $p_{i}(s)\neq p_{j}(s)$. En el algoritmo anterior, se construye un conjunto con separación eligiendo al azar los elementos de S. En el algoritmo de Shoup, el conjunto con separación se construye de la siguiente manera. Sea s en R[Y] tal que

    ${\begin{aligned}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{aligned}}$

Entonces $\{s_{0},\dots ,s_{d-1}\}$ es un conjunto con separación porque $p_{i}(s)=g_{i}$ para i = 1, ..., k (los dos polinomios mónicos tienen las mismas raíces). Como los $g_i$ son distintos por pares, para cada par de índices distintos (i, j), al menos uno de los coeficientes $s_h$ satisfará $p_{i}(s_{h})\neq p_{j}(s_{h}).$

Teniendo un conjunto con separación, el algoritmo de Shoup procede como el último algoritmo de la sección anterior, simplemente reemplazando la instrucción "elegir al azar h en el núcleo de la aplicación lineal $v\to v^{q}-v{\pmod {f}}$" por "elegir (h + i) con h en S e i en {1, ...,k - 1}".

## Complejidad temporal

Como se describió en secciones anteriores, para la factorización sobre cuerpos finitos, existen algoritmos probabilistas (por ejemplo, el algoritmo de Cantor-Zassenhaus), lo que condiciona su complejidad temporal. También existen algoritmos deterministas con una complejidad media polinomial (por ejemplo, el algoritmo de Shoup).

La existencia de un algoritmo determinista con una complejidad polinomial en el peor de los casos sigue siendo un problema abierto.

## Prueba de irreducibilidad de Rabin

Al igual que el algoritmo de factorización de distintos grados, el algoritmo de Rabin se basa en el Lema mencionado anteriormente. El algoritmo de factorización de grados distintos prueba cada d no mayor que la mitad del grado del polinomio de entrada. El algoritmo de Rabin aprovecha que los factores no son necesarios para considerar al menos d. De lo contrario, es similar al algoritmo de factorización de distintos grados. Se basa en el siguiente hecho.

Sean $p_1,$ ..., $p_k,$ todos los divisores primos de n, y sea $n/p_{i}=n_{i}$, para 1 ≤ i ≤ k un polinomio f en $F_q[x]$ de grado n irreducible en $F_q[x]$ si y solo si $\gcd \left(f,x^{q^{n_{i}}}-x\right)=1$, para 1 ≤ i ≤ k, y f divide a $x^{q^{n}}-x$. De hecho, si f tiene un factor de grado que no divide a n, entonces f no divide a $x^{q^{n}}-x$; si f tiene un factor de grado que divide a n, entonces este factor divide al menos uno de los $x^{q^{n_{i}}}-x.$

La idea básica de este algoritmo es calcular $x^{q^{n_{i}}}{\bmod {f}}$ a partir del $n_{1},\ldots ,n_{k}$ más pequeño mediante cuadratura repetida o usando el automorfismo de Frobenius, y luego tomar el mcd correspondiente. Usando la aritmética polinómica elemental, el cálculo de la matriz del automorfismo de Frobenius necesita $O(n^{2}(n+\log q))$ operaciones en $F_q,$ el cálculo de

    $x^{q^{n_{i}}}-x{\pmod {f}}$

necesita $O(n^3)$ operaciones adicionales, y el algoritmo mismo necesita $O(kn^2)$ operaciones, dando un total de $O(n^{2}(n+\log q))$ operaciones en $F_q.$ Usando aritmética rápida (de complejidad $O(n\log n)$ para la multiplicación y la división, y $O(n(\log n)^{2})$ operaciones para el cálculo del MCD), el cálculo de $x^{q^{n_{i}}}-x{\bmod {f}}$ por cuadratura repetida es de complejidad $O(n^{2}\log n\log q)$, y el algoritmo en sí es $O(kn(\log n)^{2})$, dando un total de $O(n^{2}\log n\log q)$ operaciones en $F_q.$

