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 es única para polinomios con coeficientes en cualquier cuerpo , pero se necesitan más bien fuertes restricciones en el cuerpo de los coeficientes para permitir el cálculo de la factorización por medio de un algoritmo . En la práctica, se han diseñado algoritmos solo para polinomios con coeficientes en un cuerpo finito , en el cuerpo de los racionales o en una extensión de cuerpo finitamente generada de uno 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 polinómica . También se utiliza para diversas aplicaciones de cuerpos finitos, como la teoría de 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 de números computacionales .

Como la reducción de la factorización de polinomios multivariados a la de polinomios univariados 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 en varias ramas de las matemáticas. Debido a la aplicabilidad del concepto en otros temas de las matemáticas y las ciencias, como la informática, ha habido un resurgimiento del interés en los campos finitos y esto se debe en parte a importantes aplicaciones en la teoría de la codificación y la criptografía . Las aplicaciones de los campos finitos introducen algunos de estos desarrollos en la criptografía , el álgebra computacional y la 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 primo o una potencia de primo. Para cada potencia de 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. 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 prima q , sea F _q el cuerpo finito con q elementos, único salvo isomorfismo. Un polinomio f de grado n mayor que uno, irreducible sobre F _q , define una extensión de cuerpo de grado n que es isomorfo al cuerpo con q ⁿ elementos: los elementos de esta extensión son los polinomios de grado menor que n ; la adición, 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; la inversa 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. En aras de la eficiencia de la multiplicación en el cuerpo, es habitual buscar polinomios de la forma x ⁿ + ax + b . ^{[ cita requerida ] [1]}

Los polinomios irreducibles sobre campos finitos también son útiles para generadores de números pseudoaleatorios que utilizan registros de desplazamiento de 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 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. ^[2]

Ejemplo

El polinomio P = x ⁴ + 1 es irreducible sobre Q pero no sobre cualquier 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 no cuadrados es un cuadrado y por lo tanto tenemos

1. Si entonces ${\displaystyle -1=a^{2},}$ ${\displaystyle P=(x^{2}+a)(x^{2}-a).}$
2. Si entonces ${\displaystyle 2=b^{2},}$ ${\displaystyle P=(x^{2}+bx+1)(x^{2}-bx+1).}$
3. Si entonces ${\displaystyle -2=c^{2},}$ ${\displaystyle P=(x^{2}+cx-1)(x^{2}-cx-1).}$

Complejidad

Los algoritmos de factorización de polinomios utilizan operaciones polinómicas básicas como productos, divisiones, mcd, potencias de un polinomio módulo otro, etc. Una multiplicación de dos polinomios de grado n como máximo se puede hacer 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 polinómico entre dos polinomios de grado n como máximo 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 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 cuadrado , es decir O ( n ² log( q )) operaciones en F _q utilizando métodos clásicos, u 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 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 campos finitos incluyen las siguientes tres etapas:

1. Factorización libre de cuadrados
2. Factorización de grados distintos
3. 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 campo de base, lo que implica que solo es practicable en campos finitos pequeños. Para un campo de base fijo, su complejidad temporal es polinómica, pero, para campos de base generales, la complejidad es exponencial en el tamaño del campo de base.

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, entonces el mcd se divide nuevamente entre 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 se trata de un polinomio en x ^p , que es, si los coeficientes pertenecen a F _p , la p ésima potencia del polinomio obtenida 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 por la misma sustitución en x , completada aplicando la inversa 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 raíces p . 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 números enteros, no se utiliza el algoritmo que sigue: primero se calcula la factorización libre de cuadrados sobre los números enteros y, para factorizar los polinomios resultantes, se elige un p tal que permanezca libre de cuadrados módulo p .

Algoritmo : SFF (Factorización libre de cuadrados) Entrada : Un polinomio mónico  f en F q [ x ] donde q = p m  Salida : Factorización libre de cuadrados de f  R ← 1  # Haga que w sea 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 while  w ≠ 1 do  y ← gcd ( w , c ) fac ← w / y  R ← R · fac i  w ← y ; c ← c / y ; i ← i + 1 end while # 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 si   Salida ( R )

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 utiliza 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 , uno puede simplemente tomar la raíz cuadrada p y aplicar la recursión.

Ejemplo de factorización libre de cuadrados

Dejar

${\displaystyle 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

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

Como la derivada no es cero, tenemos w = f / c = x ² + 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 ⁸ + x ⁷ + x ⁶ + x ² + x +1 . La segunda vez que pasamos por el bucle obtenemos y = x + 2 , z = 1 , R = x + 1 , con actualizaciones i = 3 , w = x + 2 y c = x ⁷ + 2 x ⁶ + x + 2 . La tercera vez que pasamos por el bucle tampoco cambia R . Por cuarta vez en el bucle obtenemos y = 1 , z = x + 2 , R = ( x + 1)( x + 2) ⁴ , con actualizaciones i = 5 , w = 1 y c = x ⁶ + 1 . Como w = 1, salimos del bucle while. Como c ≠ 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 al procedimiento de descomposición de cuadrados de forma recursiva se determina que es descompuesta de cuadrados. Por lo tanto, al elevarla al cubo y combinarla con el valor de R hasta ese punto se obtiene la descomposición descompuesta de cuadrados

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

Factorización de grados distintos

Este algoritmo divide un polinomio sin 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.

Algoritmo Factorización de grados distintos (DDF) Entrada : Un polinomio mónico sin cuadrados f ∈ 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 mónicos irreducibles de f de grado d . Begin  while do if g ≠ 1 , then ; end if i  := i + 1; end while ; if , then ; if , then return {( f , 1)} , else return S End ${\displaystyle i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;}$   ${\displaystyle \deg f^{*}\geq 2i}$   ${\displaystyle g=\gcd(f^{*},x^{q^{i}}-x)}$    ${\displaystyle S:=S\cup \{(g,i)\}}$ ${\displaystyle f^{*}:=f^{*}/g}$     ${\displaystyle f^{*}\neq 1}$  ${\displaystyle S:=S\cup \{(f^{*},\deg f^{*})\}}$  ${\displaystyle S=\emptyset }$   

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

Lema. Para i ≥ 1 el polinomio

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

es el producto de todos los polinomios mónicos irreducibles 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,

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

puede ser reemplazado por

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

Por lo tanto, tenemos que calcular:

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

Hay dos métodos:

Método I. Partir del valor de

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

calculado en el paso anterior y calcular su q- ésima potencia módulo la nueva f* , utilizando el método de exponenciación por cuadrado . Esto necesita

${\displaystyle O\left(\log(q)\deg(f)^{2}\right)}$

operaciones aritméticas en F _q en cada paso, y por lo tanto

${\displaystyle O\left(\log(q)\deg(f)^{3}\right)}$

Operaciones aritméticas para todo el algoritmo.

Método II. Utilizando el hecho de que la potencia q es una función lineal sobre F _q podemos calcular su matriz con

${\displaystyle O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)}$

operaciones. Luego, en cada iteración del bucle, calcule 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

${\displaystyle 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 igual grado (véase más adelante); por lo tanto, su uso para la factorización de distinto grado ahorra más 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 ≥ 2 factores irreducibles distintos por pares, cada uno de grado d . ${\displaystyle f_{1},\ldots ,f_{r}}$

Primero describimos 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 ( 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 igual grado, pero es determinista. Todos estos algoritmos requieren un orden impar q para el campo de coeficientes. Para más algoritmos de factorización, consulte, por ejemplo, el libro de Knuth The Art of Computer Programming, volumen 2.

Algoritmo de Cantor-Zassenhaus. Entrada: Un cuerpo finito F q de orden impar q . Un polinomio cuadrado libre mónico 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  do , Elija h en F q [ x ] con deg( h ) < n al azar; para cada u en Factores con deg( u ) > d haga si mcd( g , u ) ≠ 1 y mcd( g , u ) ≠ u , entonces Factores:= Factores ; endif endwhile ${\displaystyle g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}}$      ${\displaystyle \,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}}$  Factores 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 se basa en los factores irreducibles de f . Como todos estos campos tienen q ^d elementos, el componente de g en cualquiera de estos campos es cero con probabilidad

${\displaystyle {\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 , lo que da un número promedio de operaciones aritméticas en F _q que es . ^[3] ${\displaystyle 2.5\log _{2}r}$ ${\displaystyle O(dn^{2}\log(r)\log(q))}$

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

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

eligiendo h en el núcleo del mapa lineal

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

y reemplazando la instrucción

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

por

${\displaystyle 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 para el algoritmo mismo, para el cálculo de la matriz de la función lineal (que puede estar ya calculada en la factorización libre de cuadrados) y O ( n ³ ) para calcular su núcleo. Se puede notar que este algoritmo funciona también si los factores no tienen el mismo grado (en este caso el número r de factores, necesario para detener el bucle while, se encuentra como la dimensión del núcleo). Sin embargo, la complejidad es ligeramente mejor si la factorización libre de cuadrados se realiza antes de usar este algoritmo (como n puede disminuir con la factorización libre de cuadrados, esto reduce la complejidad de los pasos críticos). ${\displaystyle O(n^{2}\log(r)\log(q))}$ ${\displaystyle O(n^{2}(\log(q)+n))}$

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 igual grado. ^[4] 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 .

La complejidad temporal del peor caso del algoritmo de Shoup tiene un factor Aunque exponencial, esta complejidad es mucho mejor que la de 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 es exponencial, y la complejidad temporal media del algoritmo es polinómica en donde d es el grado del polinomio y p es el número de elementos del campo base. ${\displaystyle {\sqrt {p}}.}$ ${\displaystyle d\log(p),}$

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 cuerpo u → u ^p . De ello se deduce que las raíces de g _i en R _i son

${\displaystyle 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\ :\ 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 que es un conjunto separador si, para cada 1 ≤  i  <  j  ≤  k existe s  ∈  S tal que . 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 ${\displaystyle p_{i}(s)\neq p_{j}(s)}$

${\displaystyle {\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 es un conjunto separador porque 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á ${\displaystyle \{s_{0},\dots ,s_{d-1}\}}$ ${\displaystyle p_{i}(s)=g_{i}}$ ${\displaystyle p_{i}(s_{h})\neq p_{j}(s_{h}).}$

Al tener un conjunto separador, 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 del mapa lineal " por "elegir h + i con h en S e i en {1, ..., k −1}". ${\displaystyle v\to v^{q}-v{\pmod {f}}}$

Complejidad temporal

Como se ha descrito en apartados anteriores, para la factorización sobre cuerpos finitos existen algoritmos aleatorios de complejidad temporal polinómica (por ejemplo el algoritmo de Cantor–Zassenhaus). También existen algoritmos deterministas con complejidad media polinómica (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.

La prueba de irreductibilidad de Rabin

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

Sean p ₁ , ..., p _k , todos los divisores primos de n , y denotemos , para 1 ≤ i ≤ k polinomio f en F _q [ x ] de grado n es irreducible en F _q [ x ] si y solo si , para 1 ≤  i  ≤  k , y f divide a . De hecho, si f tiene un factor de grado que no divide a n , entonces f no divide a ; si f tiene un factor de grado que divide a n , entonces este factor divide al menos a uno de los ${\displaystyle n/p_{i}=n_{i}}$ ${\displaystyle \gcd \left(f,x^{q^{n_{i}}}-x\right)=1}$ ${\displaystyle x^{q^{n}}-x}$ ${\displaystyle x^{q^{n}}-x}$ ${\displaystyle 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 1 , ..., p k todos divisores primos distintos de n . Salida : O bien " f es irreducible" o " f es reducible". para  j = 1 a k  hacer ; para i = 1 a k hacer ; g  := mcd( f , h ); si g ≠ 1, entonces retorna " f es reducible" y PARAR ; fin para ; ; si g = 0, entonces retorna " f es irreducible", de lo contrario retorna " f es reducible" ${\displaystyle n_{j}=n/p_{j}}$    ${\displaystyle h:=x^{q^{n_{i}}}-x{\bmod {f}}}$  ${\displaystyle g:=x^{q^{n}}-x{\bmod {f}}}$ 

La idea básica de este algoritmo es calcular comenzando desde el más pequeño mediante el cuadrado repetido o utilizando el automorfismo de Frobenius y luego tomar el mcd correspondiente. Utilizando la aritmética polinómica elemental, el cálculo de la matriz del automorfismo de Frobenius necesita operaciones en F _q , el cálculo de ${\displaystyle x^{q^{n_{i}}}{\bmod {f}}}$ ${\displaystyle n_{1},\ldots ,n_{k}}$ ${\displaystyle O(n^{2}(n+\log q))}$

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

necesita O ( n ³ ) operaciones adicionales, y el algoritmo en sí necesita O ( kn ² ) operaciones, lo que da un total de operaciones en F _q . Usando aritmética rápida (complejidad para la multiplicación y división, y para el cálculo del MCD), el cálculo de por cuadrado repetido es , y el algoritmo en sí es , lo que da un total de operaciones en F _q . ${\displaystyle O(n^{2}(n+\log q))}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n(\log n)^{2})}$ ${\displaystyle x^{q^{n_{i}}}-x{\bmod {f}}}$ ${\displaystyle O(n^{2}\log n\log q)}$ ${\displaystyle O(kn(\log n)^{2})}$ ${\displaystyle O(n^{2}\log n\log q)}$

Véase también

• Algoritmo de Berlekamp
• Algoritmo de Cantor-Zassenhaus
• Factorización de polinomios

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: un estudio. Journal of Symbolic Computation , volumen 31, números 1 y 2, enero de 2001, 3-17.
• Gao Shuhong, Panario Daniel, Prueba y construcción de polinomios irreducibles sobre campos 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 campos 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

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, págs. 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. 

Enlaces externos

• Algunos polinomios irreducibles http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
• Teoría de campos y de Galois: http://www.jmilne.org/math/CourseNotes/FT.pdf
• Campo de Galois: http://designtheory.org/library/encyc/topics/gf.pdf
• Factorización de polinomios sobre cuerpos finitos: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf