Diferencia entre revisiones de «Factorización de polinomios sobre cuerpos finitos»

Contenido eliminado Contenido añadido

En renglón

Revisión del 09:39 9 may 2021

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 computacionales.

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

Campo finito

Artículos principales: Artículo y 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 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 cuerpos finitos y esto 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 finito o Cuerpo finito es un cuerpo con un orden finite (número de elementos). El orden de un cuerpo finito es siempre un número primo o una potencia de prima. Para cada potencia prima q = p^r , existe exactamente un cuerpo finito con elementos q , isomorfismo salvo (matemáticas). Este cuerpo se indica como GF ( q ) o F _q. Si p es primo, GF ( p ) es el característica (matemática) de orden p ; es el cuerpo de residue classes 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 positivo la licenciatura. Un polinomio de grado positivo que no es irreductible sobre F se llama reducible sobre F .

Los polinomios irreducibles nos permiten construir los cuerpos finitos de orden no primo. De hecho, para una potencia primaria q , sea 'F' _q el cuerpo finito con elementos q , únicos hasta el 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 isomorfo al cuerpo con ' Elementos 'qn: los elementos de esta extensión 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 GCD extendido (ver Arithmetic of algebraic extensions).

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

Los polinomios irreducibles sobre cuerpos finitos también son útiles para los generadores de números Pseudorandom que utilizan registros de desplazamiento de retroalimentación y logaritmo discreto sobre 'F' _2ⁿ.

El número de polinomio mónico irreductibles de grado n sobre 'F' _q es el número de aperiodic necklaces, dado por Moreau's necklace-counting function 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 n.^[1]

Ejemplo

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

En cualquier extensión de cuerpo de 'F' ₂, P = ( x + 1) ⁴.
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 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 polinomial utilizan operaciones polinomiales básicas como productos, divisiones, mcd, potencias de un polinomio módulo otro, etc. Un multiplication de dos polinomios de grado como máximo n se puede realizar en operaciones O(n²) en 'F' _q usando aritmética "clásica", o en O ( nlog ( n ) log (log ( n ))) operaciones en 'F' ' 'q usando "fast" arithmetic. Se puede realizar una División euclídea (división con resto) dentro de los mismos límites de tiempo. El costo de un máximo común divisor polinómico entre dos polinomios de grado como máximo n se puede tomar como operaciones O ( n²) en 'F' q usando metanfetamina clásica

ods, o como O ( nlog² ( 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 hacer con O (log ( q )) productos polinomiales, usando el método exponenciación binaria, es decir O ( n²log ( q )) operaciones en 'F' _q usando métodos clásicos, o ' 'O' '(' 'nlog (' 'q' ') log (' 'n' ') log (log (' 'n' '))) operaciones en' F 'q usando fast métodos.

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:

Square-free factorization
Distinct-degree factorization
Equal-degree factorization

Una excepción importante es Berlekamp's algorithm, que combina las etapas 2 y 3.

Algoritmo de Berlekamp

Artículos principales: Artículo y Berlekamp's algorithm.

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 de tierra, lo que implica que es practicable solo en pequeños cuerpos finitos. Para un cuerpo terrestre fijo, su complejidad temporal es polinomial, pero, para cuerpos terrestres generales, la complejidad es exponencial en el tamaño del cuerpo terrestre.

Factorización libre de cuadrados

El algoritmo determina una factorización square-free para polinomios cuyos coeficientes provienen del cuerpo finito 'F' _q de orden q = p^m con p primo. Este algoritmo determina primero el derivada y luego calcula el mcd del polinomio y su derivada. Si no es uno, el mcd se vuelve a dividir en 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, el p la 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 de el Frobenius automorphism a los coeficientes. ^{[cita requerida]}

Este algoritmo funciona también sobre un cuerpo de characteristic 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, Yun's algorithm 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 una p tal que permanecen libres de cuadrados módulo p .

 'Algoritmo' :  'SFF'  (Factorización sin cuadrados)
     'Entrada' : A polinomio mónico  f  en  'F'  _q [ x ] donde  q = p^m 
     'Salida' : Factorización libre de cuadrados de  f 
     R  ← 1
   
    # Hacer que  w  sea el producto (sin multiplicidad) de todos los factores de  f  que tienen
    # multiplicidad no divisible por  p 
     c  ←  'mcd'  ( f ,  f  & prime;)
     w  ←  f  /  c 
   
    # Paso 1: Identifique 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 
     'terminar mientras' 
    #  c  es ahora el producto (con multiplicidad) de los factores restantes de  f 
   
    # Paso 2: identifica todos los factores restantes mediante la recursividad
    # Tenga en cuenta 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
    terminara si
   
     'Salida'  ( R )

La idea es identificar el producto de todos los factores irreductibles 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 , uno puede simplemente tomar la raíz cuadrada de la p y aplicar la recursividad.

Ejemplo de factorización libre de cuadrados

Dejar

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

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, tenemos $w = f / c = x 2 + 2$ y entramos en el ciclo 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 a través del ciclo da $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 a través del bucle tampoco cambia $R$ . Por cuarta vez a través del bucle obtenemos $y = 1$ , $z = x + 2$ , $R = (x + 1)(x + 2) 4$ , con actualizaciones $i = 5$

XXX, $w = 1$ y $c = x 6 + 1$ . Dado que w = 1, salimos del ciclo while. Dado que c ≠ 1, debe ser un cubo perfecto. La raíz cúbica de c , obtenida al reemplazar x³ por x es x² + 1, y llamar al procedimiento sin cuadrados determina de forma recursiva que es cuadrado libre. 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 irreductibles 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 monic cuadrado libre  $f \in F q [x]$ 
     'Salida' : El conjunto de todos los pares  $(g, d)$ , tal que
              $f$  tiene un factor irreducible de grado  $d$  y
              $g$  es el producto de todos los factores mónicos irreductibles de  $f$  de grado  $d$ .
    Empezar
         $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$ 
            terminara si
             $i := i + 1;$ 
         'end while' ;
         'si'   $f^{*}\neq 1$ ,  'entonces'   $S:=S\cup \{(f^{*},\deg f^{*})\}$ ;
         'si'   $S=\emptyset$ ,  'entonces devuelve'   ${(f, 1)}$ ,
             'si no regresa'   $S$ 
    Final

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

Lemma. For i ≥ 1 the polynomial
$x^{q^{i}}-x\in \mathbf {F} _{q}[x]$
is the product of all monic irreducible polynomials in F_q[x] whose degree divides 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 emabargo

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^{*},

hay dos métodos:

Method I. Start from the value of
$x^{q^{i-1}}\mod f^{*}$

computed at the preceding step and to compute its q-th power modulo the new f*, using exponenciación binaria method. This needs

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

arithmetic operations in F_q at each step, and thus

$O\left(\log(q)\deg(f)^{3}\right)$
arithmetic operations for the whole algorithm.

Method II. Using the fact that the q-th power is a linear map over F_q we may compute its matrix with
$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)$

operations. Then at each iteration of the loop, compute the product of a matrix by a vector (with O(deg(f)²) operations). This induces a total number of operations in F_q which is

$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).$
Thus this second method is more efficient and is usually preferred. Moreover, the matrix that is computed in this method is used, by most algorithms, for equal-degree factorization (see below); thus using it for the distinct-degree factorization saves further computing time.

Factorización de igual grado

Algoritmo de Cantor-Zassenhaus

Artículos principales: Artículo y Cantor–Zassenhaus algorithm.

En esta sección, consideramos la factorización de un polinomio univariante monic sin cuadrados f , de grado n , sobre un cuerpo finito 'F' _q, que tiene r ≥ 2 factores irreductibles 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 que tiene una complejidad ligeramente mejor. Ambos son algoritmos probabilísticos cuyo tiempo de ejecución depende de elecciones aleatorias (Algoritmo de Las Vegass) y tienen un buen tiempo de ejecución medio. 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 cuerpo de coeficientes. Para obtener más algoritmos de factorización, consulte, p. Ej. Libro de Knuth The Art of Computer Programming volumen 2.

 'Algoritmo'  Algoritmo de Cantor-Zassenhaus.
     'Entrada:'  Un cuerpo finito  'F'  _q de orden impar  q .
           Un polinomio monic cuadrado libre  f  en  'F'  _q [ x ] de grado  n  =  rd ,
                que tiene  r  ≥ 2 factores irreductibles cada uno de grado  d 
     'Salida:'  El conjunto de factores mónicos irreductibles de  f .

    Factores: = { f };
    while Tamaño (factores) < r do,
        Choose h in F_q [ x ] con grados ( h ) < n at random;
         $g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}$ 
        para cada  u  en Factores con deg ( u )>  d  do
            si mcd ( g ,  u ) ≠ 1 y mcd ( g ,  u ) ≠  u , entonces
                Factores: = Factors $\,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}$ ;
            terminara si;
    mientras tanto

    Factores de retorno.

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 elementos q^d , 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 while 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))$ .^[2]

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

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

eligiendo 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 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 del mapa lineal (que puede estar ya calculado en la factorización libre de cuadrados) y O ( n³) para computando su kernel. 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 while, 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).

====V

algoritmo de ictor Shoup==== Como los algoritmos de la sección anterior, el algoritmo de Victor Shoup es un algoritmo de factorización de igual grado.^[3] 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 complejidad temporal 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 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 de tierra.

Sea g = g₁ ... g_k la factorización deseada, donde g_i son polinomios mónicos irreducibles distintos de grado d . Deje n = deg ( g ) = kd . Consideramos ring 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 lo denotamos por p_i ' 'el homomorfismo natural de la' 'R' 'al' '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 el mismo subálgebra B de R que el Berlekamp's algorithm, a veces llamado "Berlekamp subagebra" y definido 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 separating set si, por cada 1 ≤ i < j ≤ k there exists s ∈ S such that $p_{i}(s)\neq p_{j}(s)$ . En el algoritmo anterior, se construye un conjunto de separación eligiendo al azar los elementos de S . En el algoritmo de Shoup, el conjunto de 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 de separación porque $p_{i}(s)=g_{i}$ para i = 1, ..., k (los dos polinomios monicos 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 de 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 del mapa lineal $v\to v^{q}-v{\pmod {f}}$ " por "elegir h + ' 'i' 'con' 'h' 'en' 'S' 'y' 'i' 'en {1, ...,' 'k' '- 1} ".

Complejidad de tiempo

Como se describió en secciones anteriores, para la factorización sobre cuerpos finitos, existen algoritmo probabilista del polinomio complejidad temporal (por ejemplo, el algoritmo de Cantor-Zassenhaus). 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 irreductibilidad de Rabin

Al igual que el algoritmo de factorización de distintos grados, el algoritmo^[4] 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 menos "d". De lo contrario, es similar al algoritmo de factorización de distintos grados. Se basa en el siguiente hecho.

Sean p₁, ..., p_k , todos los divisores primos de n , y denoten $n/p_{i}=n_{i}$ , para 1 ≤ i ≤ k 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 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.$

 'Algoritmo'  Prueba de irreductibilidad de Rabin
     'Entrada' : Un polinomio monico  f  en  'F'  _q [ x ] de grado  n ,
         p₁, ...,  p_k  todos los divisores primos distintos de  n .
     'Salida' : O " f  es irreducible" o " 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 return'  " f  es reducible"  'y STOP' ;
     'fin de' ;
     $g:=x^{q^{n}}-x{\bmod {f}}$ ;
     'si'   g  = 0,  'entonces return'  " f  es irreducible",
         'else return'  " f  es reducible"

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 Frobenius automorphism, y luego tomar el gcd correspondiente. Usando la aritmética polinomial elemental, el cálculo de la matriz del automorfismo de Frobenius necesita operaciones $O(n^{2}(n+\log q))$ en 'F' _q, el cálculo de

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

necesita O ( n³) operaciones adicionales, y el algoritmo mismo necesita operaciones O ( kn²), dando un total de

Operaciones $O(n^{2}(n+\log q))$ en 'F' _q. Usando aritmética rápida (complejidad $O(n\log n)$ para multiplicación y división, y $O(n(\log n)^{2})$ para cálculo de GCD), el cálculo de $x^{q^{n_{i}}}-x{\bmod {f}}$ por cuadratura repetida es $O(n^{2}\log n\log q)$ , y el algoritmo en sí es $O(kn(\log n)^{2})$ , dando un total de operaciones $O(n^{2}\log n\log q)$ en 'F' _q.

Ver también

Referencias

KEMPFERT, H (1969) '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 de la Universidad de Toronto
Von Zur Gathen, J.; Panario, D. (2001). Factorización de polinomios sobre cuerpos finitos: una encuesta. Journal of Symbolic Computation, Volumen 31, números 1 a 2, enero de 2001, 3 a 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 el Departamento de Ciencias de la Computación de la Universidad de Toronto, Canadá M5S-1A4
Shoup, Victor (1989) Nuevo Algoritmos para encontrar polinomios irreducibles en cuerpos finitos Departamento de Ciencias de la Computación Universidad de Wisconsin & ndash; Madison
Geddes, Keith O.; Czapor, Stephen R .; Labahn, George (1992). Algoritmos para álgebra informática. Boston, MA: Kluwer Academic Publishers. págs. xxii + 585. ISBN 0-7923-9259-0.

Referencias

↑ Christophe Reutenauer, Mots circulaires et polynomes irreductibles, Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285
↑ Flajolet, Philippe; Steayaert, Jean-Marc (1982), Automata, Languages and Programming, Lecture Notes in Comput. Sci. 140, Springer, pp. 239-251, ISBN 978-3-540-11576-2, doi:10.1007/BFb0012773 .
↑ Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990
↑ Rabin, Michael (1980). «Probabilistic algorithms in finite fields». SIAM Journal on Computing 9 (2): 273-280. doi:10.1137/0209024. Parámetro desconocido |citeseerx= ignorado (ayuda)

Enlaces externos

Algunos polinomios irreducibles http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
Campo y teoría de Galois: http: //www.jmilne.org/math/CourseNotes/FT.pdf
Campo 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

Datos: Q5428743

[1] Christophe Reutenauer, Mots circulaires et polynomes irreductibles, Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285

[2] Flajolet, Philippe; Steayaert, Jean-Marc (1982), Automata, Languages and Programming, Lecture Notes in Comput. Sci. 140, Springer, pp. 239-251, ISBN 978-3-540-11576-2, doi:10.1007/BFb0012773 .

[3] Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990

[4] Rabin, Michael (1980). «Probabilistic algorithms in finite fields». SIAM Journal on Computing 9 (2): 273-280. doi:10.1137/0209024. Parámetro desconocido |citeseerx= ignorado (ayuda)

[1]

[2]

[3]

[4]