Factorización de polinomios sobre cuerpos finitos

En matemáticas y álgebra computacional, la factorización de un polinomio consiste en descomponerlo en un producto de factores irreducibles . Esta descomposición es teóricamente posible y única para polinomios con coeficientes en cualquier cuerpo , pero se requieren restricciones bastante estrictas sobre 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 únicamente para polinomios con coeficientes en un cuerpo finito , en el cuerpo de los racionales o en una extensión finitamente generada de alguno de ellos.

Todos los algoritmos de factorización, incluido el caso de polinomios multivariados sobre los números racionales, reducen el problema a este caso; véase factorización de polinomios . También se utiliza en diversas aplicaciones de campos finitos, como la teoría de la codificación ( códigos de redundancia cíclica y códigos BCH ), la criptografía ( criptografía de clave pública mediante curvas elípticas ) y la teoría computacional de números .

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

Fondo

Campo finito

La teoría de los campos finitos, cuyos orígenes se remontan a los trabajos de Gauss y Galois , ha desempeñado un papel importante en diversas ramas de las matemáticas. Debido a la aplicabilidad del concepto en otros campos de las matemáticas y ciencias como la informática, se ha producido un resurgimiento del interés en los campos finitos, en parte gracias a sus importantes aplicaciones en la teoría de la codificación y la criptografía . Las aplicaciones de los campos finitos introducen algunos de estos avances en criptografía , álgebra computacional y teoría de la codificación .

Un cuerpo finito o cuerpo de Galois 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 de un número primo q = p ^r , existe exactamente un cuerpo finito con q elementos, salvo isomorfismo. Este cuerpo se denota GF ( q ) o F _q . Si p es primo, GF ( p ) es el cuerpo primo de orden p ; es el cuerpo de clases de residuos módulo p , y sus p elementos se denotan 0, 1, ..., p −1. Por lo tanto , a = b en GF ( p ) significa lo mismo que a ≡ b (mod p ) .

Polinomios irreducibles

Sea F un cuerpo finito. Como en los cuerpos generales, un polinomio no constante f en F [ x ] se dice 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 nos permiten construir cuerpos finitos de orden no primo. De hecho, para una potencia prima q , sea F _q el cuerpo finito con q elementos, único salvo isomorfismo. 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 isomorfa al cuerpo con q ⁿ elementos: los elementos de esta extensión son los polinomios de grado menor que n ; la suma, la resta y la multiplicación por un elemento de F _q son las 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 habitual consiste en tomar un polinomio al azar y comprobar su irreducibilidad. Para optimizar la multiplicación en el cuerpo, se suelen buscar polinomios de la forma x ⁿ + ax + b . ^[¹^]

Los polinomios irreducibles sobre cuerpos finitos también son útiles para generadores de números pseudoaleatorios que utilizan registros de desplazamiento con retroalimentación y logaritmo discreto sobre F _{2 ⁿ} .

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, los polinomios irreducibles de todos los grados d que dividen a n. ^{[ 2 ]}

Ejemplo

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

En cualquier extensión de campo de F ₂ , P = ( x + 1) ⁴ .
En cualquier otro cuerpo finito, al menos uno de −1, 2 y −2 es un cuadrado, porque el producto de dos números que no son cuadrados es un cuadrado y por lo tanto tenemos

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 de polinomios utilizan operaciones básicas con polinomios, como productos, divisiones, mcd, potencias de un polinomio módulo otro, etc. Una multiplicación de dos polinomios de grado como máximo n se puede realizar en O ( n ² ) operaciones en F _q usando aritmética "clásica", o en O ( n log( n ) log(log( n )) ) operaciones en F _q usando aritmética "rápida" . Una división euclidiana (división con resto) se puede realizar dentro de los mismos límites de tiempo. El costo de un máximo común divisor polinomial entre dos polinomios de grado como máximo n se puede tomar como O ( n ² ) operaciones en F _q usando métodos clásicos, o como O ( n log ² ( n ) log(log( n )) ) operaciones en F _q usando métodos rápidos. Para polinomios h , g de grado como máximo n , la exponenciación h ^q mod g se puede realizar con O (log( q )) productos polinomiales, utilizando el método de exponenciación por cuadratura , es decir, O ( n ² log( q )) operaciones en F _q utilizando métodos clásicos, o O ( n log( q )log( n ) log(log( n ))) operaciones en F _q utilizando métodos rápidos.

En los algoritmos que siguen, las complejidades se expresan en términos del 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 sin cuadrados
Factorización de grado distinto
Factorización de igual grado

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

El 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 sobre los elementos del campo base, lo que implica que solo es practicable sobre campos finitos pequeños. Para un campo base fijo, su complejidad temporal es polinómica, pero para campos base generales, la complejidad es exponencial con respecto al tamaño del campo base.

factorización sin 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 , donde p es un número primo. Este algoritmo primero determina la derivada y luego calcula el máximo común divisor (MCD) del polinomio y su derivada. Si el MCD no es uno, se divide nuevamente entre el polinomio original, siempre que la derivada no sea cero (un caso que se presenta 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 -ésima potencia del polinomio obtenido al sustituir x por x ^{1/ p} . Si los coeficientes no pertenecen a F _p , la p -ésima raíz 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 también funciona sobre un campo de característica cero, con la única diferencia de que nunca entra en los bloques de instrucciones donde se calculan las raíces p -ésimas. Sin embargo, en este caso, el algoritmo de Yun es mucho más eficiente porque calcula los máximos comunes divisores 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 permanezcan libres de cuadrados módulo p .

Algoritmo : SFF (Factorización sin cuadrados) Entrada : Un polinomio mónico f en F _q [ x ] donde q = p ^m Salida : Factorización sin cuadrados de f R ← 1 # Sea w el producto (sin multiplicidad) de todos los factores de f que tienen # multiplicidad no divisible por p c ← mcd ( f , f ′ ) w ← f / c # Paso 1: Identificar todos los factores en w i ← 1 mientras w ≠ 1 hacer y ← mcd ( w , c ) fac ← w / y R ← R · fac ⁱ w ← y ; c ← c / y ; i ← i + 1 fin mientras # c es ahora el producto (con multiplicidad) de los factores restantes de f # Paso 2: Identificar todos los factores restantes mediante recursión. # Nótese que estos son los factores de f que tienen multiplicidad divisible por p si c ≠ 1 entonces c ← c ^{1/ p} R ← R · SFF ( c ) ^p fin siSalida ( R )

La idea es identificar el producto de todos los factores irreducibles de f con la misma multiplicidad. Esto se realiza en dos pasos. El primer paso utiliza la derivada formal de f para hallar todos los factores cuya multiplicidad no sea divisible por p . El segundo paso identifica los factores restantes. Como todos los factores restantes tienen multiplicidad divisible por p , es decir, son potencias de p , basta con calcular la raíz p -ésima y aplicar la recursión.

Ejemplo de factorización sin cuadrados

Dejar

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

ser factorizado sobre el campo con tres elementos.

El algoritmo calcula primero

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

Como la derivada es distinta de cero, tenemos $w = f / c = x 2 + 2$ y entramos en el bucle while . Después de un bucle, tenemos $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 que pasa el bucle, obtenemos $y = x + 2$ , $z = 1$ , $R = x + 1$ , con actualizaciones $i = 3$ , $w = x + 2$ y $c = x 7 + 2 x 6 + x + 2.$ La tercera vez que pasa el bucle tampoco cambia $R.$ Para la cuarta vez que pasa el bucle, obtenemos $y = 1$ , $z = x + 2$ , $R = (x + 1)(x + 2) 4$ , con actualizaciones $i = 5$ , $w = 1$ y $c = x 6 + 1.$ Como w = 1, salimos del bucle while. Dado que $c \neq 1$ , debe ser un cubo perfecto. La raíz cúbica de $c$ , obtenida al reemplazar $x³$ por $x,$ $es$ x² $+ 1$ , y al llamar recursivamente al procedimiento libre de cuadrados se determina que es libre de cuadrados. Por lo tanto, al elevarlo al cubo y combinarlo con el valor de $R$ hasta ese punto se obtiene la descomposición libre de cuadrados $.$

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

Factorización de grado distinto

Este algoritmo divide un polinomio libre de cuadrados en un producto de polinomios cuyos factores irreducibles tienen todos el mismo grado. Sea $f \in F q [x]$ de grado $n$ el polinomio que se va a factorizar.

Algoritmo de factorización de grado distinto (DDF) Entrada : Un polinomio mónico libre de cuadrados  $f \in F q [x]$ Salida : El conjunto de todos los pares  $(g, d)$  , tales que  $f$  tiene un factor irreducible de grado  $d$  y  $g$  es el producto de todos los factores irreducibles mónicos de  $f$  de grado  $d$  . Inicio $i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;$ mientras $\deg f^{*}\geq 2i$ hacer $g=\gcd(f^{*},x^{q^{i}}-x)$ si  $g \neq 1$  , entonces $S:=S\cup \{(g,i)\}$ ;  $f^{*}:=f^{*}/g$ fin si  $i := i + 1;$ fin mientras ; si $f^{*}\neq 1$ , entonces $S:=S\cup \{(f^{*},\deg f^{*})\}$ ; si $S=\emptyset$ , entonces devuelve  ${(f, 1)}$  , de lo contrario devuelve  $S$  Fin

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

Lema. Para i ≥ 1 el polinomio
$x^{q^{i}}-x\in \mathbf {F} _{q}[x]$
es el producto de todos los polinomios irreducibles mónicos en F _q [ x ] cuyo grado divide a i .

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

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

puede ser reemplazado por

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

Por lo tanto, tenemos que calcular:

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

Existen dos métodos:

Método I. Comience desde el valor de
$x^{q^{i-1}}\mod f^{*}$
calculado en el paso anterior y para calcular su q -ésima potencia módulo el nuevo f* , utilizando el método de exponenciación por cuadratura . Esto requiere
$O\left(\log(q)\deg(f)^{2}\right)$
operaciones aritméticas en F _q en cada paso, y por lo tanto
$O\left(\log(q)\deg(f)^{3}\right)$
operaciones aritméticas para todo el algoritmo.

Método II. Utilizando el hecho de que la q -ésima potencia es una aplicación lineal sobre F _q podemos calcular su matriz con
$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)$
operaciones. Luego, en cada iteración del bucle, se calcula el producto de una matriz por un vector (con O (deg( f ) ² ) operaciones). Esto induce un número total de operaciones en F _q que es
$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).$
Por lo tanto, este segundo método es más eficiente y suele ser el preferido. Además, la matriz que se calcula con este método se utiliza, en la mayoría de los algoritmos, para la factorización de grado igual (véase más adelante); así, su uso para la factorización de grado distinto ahorra tiempo de cálculo.

Factorización de igual grado

Algoritmo de Cantor-Zassenhaus

En esta sección, consideramos la factorización de un polinomio univariado mónico libre de cuadrados f , de grado n , sobre un cuerpo finito F _q , que tiene $r \geq 2$ factores irreducibles distintos por pares. $f_{1},\ldots ,f_{r}$ cada uno de grado d .

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

Algoritmo Algoritmo de Cantor-Zassenhaus. Entrada: Un campo finito F _q de orden impar q . Un polinomio mónico libre de cuadrados f en F _q [ x ] de grado n = rd , que tiene r ≥ 2 factores irreducibles cada uno de grado d Salida: El conjunto de factores irreducibles mónicos de f . Factores := { f }; mientras Tamaño(Factores) < r hacer , Elija h en F _q [ x ] con deg( h ) < n al azar;  $g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}$ para cada u en Factors con deg( u ) > d hacer si mcd( g , u ) ≠ 1 y mcd( g , u ) ≠ u , entonces Factors:= Factors $\,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}$ ; fin si fin mientrasFactores de retorno

La corrección de este algoritmo se basa en el hecho de que el anillo F _q [ x ]/ f es un producto directo de los campos F _q [ x ]/ f _i donde f _i recorre los factores irreducibles de f . Como todos estos campos tienen q ^d elementos, la componente de g en cualquiera de estos campos 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 promedio de iteraciones del bucle while del algoritmo es menor que $2.5\log _{2}r$ , lo que da un número promedio de operaciones aritméticas en F _q que es $O(dn^{2}\log(r)\log(q))$ . ^{[ 3 ]}

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

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

al elegir h en el núcleo del mapa 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 campos F _q [ x ]/ f _i por el producto directo de sus subcampos 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 del mapeo lineal (que puede estar ya calculada en la factorización sin cuadrados) y O ( n³ ) para el cálculo de su núcleo. Cabe destacar que este algoritmo también funciona si los factores no tienen el mismo grado (en este caso, el número ^rde factores, necesario para detener el bucle while, se obtiene 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 (ya que n puede disminuir con la factorización sin cuadrados, lo que reduce la complejidad de los pasos críticos).

El algoritmo de Victor Shoup

Al igual que los algoritmos de la sección anterior, el algoritmo de Victor Shoup es un algoritmo de factorización de grado igual. ^{[ 4 ]} A diferencia de ellos, es un algoritmo determinista . Sin embargo, en la práctica es menos eficiente que los algoritmos de la sección anterior. Para el algoritmo de Shoup, la entrada se restringe a polinomios sobre cuerpos primos F _p .

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

Sea g = g ₁ ... g _k la factorización deseada, donde los g _i son polinomios irreducibles mónicos distintos de grado d . Sea n = deg( g ) = kd . Consideramos el anillo R = F _q [ x ]/ g y denotamos 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 denotamos 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 de cuerpos 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),\ldots ,p_{i}\left(x^{q^{d-1}}\right).

Al igual que en el algoritmo anterior, este algoritmo utiliza la misma subálgebra B de R que el algoritmo de Berlekamp , a veces llamada "subálgebra de Berlekamp" y definida como

{\displaystyle {\begin{aligned}B&=\left\{\alpha \in R\

Se dice que un subconjunto S de B es un conjunto separador si, para cada 1 ≤ i < j ≤ k existe s ∈ S tal que $p_{i}(s)\neq p_{j}(s)$ En el algoritmo anterior, se construye un conjunto separador eligiendo al azar los elementos de S. En el algoritmo de Shoup, el conjunto separador 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 separador 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 entre sí, 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}).$

Al disponer de un conjunto separador, el algoritmo de Shoup procede como el último algoritmo de la sección anterior, simplemente reemplazando la instrucción "elegir aleatoriamente h en el núcleo del mapa lineal". $v\to v^{q}-v{\pmod {f}}$ " eligiendo 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 aleatorios con complejidad temporal polinómica (por ejemplo, el algoritmo de Cantor-Zassenhaus). También existen algoritmos deterministas con una complejidad media polinómica (por ejemplo, el algoritmo de Shoup).

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

Prueba de irreductibilidad de Rabin

Al igual que el algoritmo de factorización de grado distinto, el algoritmo de Rabin ^{[ 5 ]} se basa en el lema mencionado anteriormente. El algoritmo de factorización de grado distinto prueba cada d que no sea mayor que la mitad del grado del polinomio de entrada. El algoritmo de Rabin aprovecha que no se necesitan factores para considerar menos d . Por lo demás, es similar al algoritmo de factorización de grado distinto. Se basa en el siguiente hecho.

Sean p ₁ , ..., p _k , todos los divisores primos de n , y denotemos $n/p_{i}=n_{i}$ , para 1 ≤ i ≤ k, un polinomio f en F _q [ x ] de grado n es 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 $x^{q^{n}}-x$ . De hecho, si f tiene un factor de grado que no divide a n , entonces f no divide. $x^{q^{n}}-x$ ; si f tiene un factor de grado que divide a n , entonces este factor divide al menos a uno de los $x^{q^{n_{i}}}-x.$

Algoritmo de prueba de irreducibilidad de Rabin Entrada : Un polinomio mónico f en F _q [ x ] de grado n , p ₁ , ..., p _k todos los divisores primos distintos de n . Salida : O bien " f es irreducible" o bien " f es reducible". para j = 1 a k hacer $n_{j}=n/p_{j}$ ; para i = 1 a k hacer $h:=x^{q^{n_{i}}}-x{\bmod {f}}$ ; g := mcd( f , h ); si g ≠ 1, entonces devolver " f es reducible" y DETENER ; fin del bucle ;  $g:=x^{q^{n}}-x{\bmod {f}}$ ; si g = 0, entonces devuelve " f es irreducible", de lo contrario devuelve " f es reducible"

La idea básica de este algoritmo es calcular $x^{q^{n_{i}}}{\bmod {f}}$ comenzando por el más pequeño $n_{1},\ldots ,n_{k}$ mediante la elevación al cuadrado repetida o utilizando el automorfismo de Frobenius , y luego para tomar el mcd correspondiente. Utilizando 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}}

necesidades $O(n^{3})$ operaciones adicionales, y el algoritmo en sí necesita $O(kn^{2})$ operaciones, dando un total de $O(n^{2}(n+\log q))$ operaciones en F _q . Usando aritmética rápida (complejidad $O(n\log n)$ para la multiplicación y la división, y $O(n(\log n)^{2})$ para el cálculo del MCD), el cálculo del $x^{q^{n_{i}}}-x{\bmod {f}}$ mediante elevación al cuadrado repetida es $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 .

Véase también

Referencias

KEMPFERT, H (1969) Sobre la factorización de polinomios Departamento de Matemáticas, Universidad Estatal de Ohio, Columbus, Ohio 43210
Shoup, Victor (1996) Suavidad y factorización de polinomios sobre cuerpos finitos. Departamento de Ciencias de la Computación, Universidad de Toronto.
Von Zur Gathen, J. ; Panario, D. (2001). Factorización de polinomios sobre cuerpos finitos: una revisión . Journal of Symbolic Computation , Volumen 31, Números 1–2, enero de 2001, 3–17.
Gao Shuhong, Panario Daniel, Prueba y construcción de polinomios irreducibles sobre cuerpos finitos. Departamento de Ciencias Matemáticas, Universidad de Clemson, Carolina del Sur, 29634–1907, EE. UU. y Departamento de Ciencias de la Computación, Universidad de Toronto, Canadá M5S-1A4.
Shoup, Victor (1989) Nuevos algoritmos para encontrar polinomios irreducibles sobre cuerpos finitos. Departamento de Ciencias de la Computación, Universidad de Wisconsin - Madison.
Geddes, Keith O .; Czapor, Stephen R.; Labahn, George (1992). Algoritmos para álgebra computacional . Boston, MA: Kluwer Academic Publishers. pp. xxii+585. ISBN 0-7923-9259-0.

Notas

↑ "¿Reducibilidad sobre $\mathbb{Z}_2$?" . Mathematics Stack Exchange . Consultado el 10 de septiembre de 2023 .
↑ Christophe Reutenauer, Mots circulaires et polinomes irreductibles , Ann. Ciencia. matemáticas Quebec, vol 12, no 2, págs. 275-285
↑ Flajolet, Philippe; Steayaert, Jean-Marc (1982), Autómatas, lenguajes y programación , Lecture Notes in Comput. Sci., vol. 140, Aarhus: Springer, pp. 239–251 , doi : 10.1007/BFb0012773 , ISBN 978-3-540-11576-2
↑ Victor Shoup, Sobre la complejidad determinista de la factorización de polinomios sobre cuerpos finitos , Information Processing Letters 33:261-267, 1990
^ Rabin, Michael (1980). "Algoritmos probabilísticos en campos finitos". Revista SIAM de Computación . 9 (2): 273– 280. CiteSeerX 10.1.1.17.5653 . doi : 10.1137/0209024 .

[1] "¿Reducibilidad sobre $\mathbb{Z}_2$?" . Mathematics Stack Exchange . Consultado el 10 de septiembre de 2023 .

[2] Christophe Reutenauer, Mots circulaires et polinomes irreductibles , Ann. Ciencia. matemáticas Quebec, vol 12, no 2, págs. 275-285

[3] Flajolet, Philippe; Steayaert, Jean-Marc (1982), Autómatas, lenguajes y programación , Lecture Notes in Comput. Sci., vol. 140, Aarhus: Springer, pp. 239–251 , doi : 10.1007/BFb0012773 , ISBN 978-3-540-11576-2

[4] Victor Shoup, Sobre la complejidad determinista de la factorización de polinomios sobre cuerpos finitos , Information Processing Letters 33:261-267, 1990

[5] Rabin, Michael (1980). "Algoritmos probabilísticos en campos finitos". Revista SIAM de Computación . 9 (2): 273– 280. CiteSeerX 10.1.1.17.5653 . doi : 10.1137/0209024 .

[

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]