En matemáticas y álgebra informática la factorización de un polinomio consiste en descomponerlo en un producto de factores irreductibles . Esta descomposición es teóricamente posible y es única para polinomios con coeficientes en cualquier campo , pero se necesitan restricciones bastante fuertes en el campo de los coeficientes para permitir el cálculo de la factorización por medio de un algoritmo . En la práctica, los algoritmos se han diseñado solo para polinomios con coeficientes en un campo finito , en el campo de los racionales o en unextensión de campo 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; ver factorización de polinomios . También se utiliza para 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 numérica computacional .
Como la reducción de la factorización de polinomios multivariados a polinomios univariados no tiene ninguna especificidad en el caso de coeficientes en un campo 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 matemáticas y ciencias como la informática, ha habido un resurgimiento del interés en 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 campos finitos introducen algunos de estos desarrollos en criptografía , álgebra informática y teoría de la codificación .
Un campo finito o campo de Galois es un campo con un orden finito (número de elementos). El orden de un campo finito es siempre primo o potencia primo. Para cada potencia prima q = p r , existe exactamente un campo finito con q elementos, hasta el isomorfismo. Este campo se denota GF ( q ) o F q . Si p es primo, GF ( p ) es el campo primo de orden p ; es el campo de clases de residuos módulo p , y sus p elementos se denotan 0, 1, ..., p −1. Por tanto, a = b en GF ( p ) significa lo mismo que a ≡ b (mod p ).
Polinomios irreducibles
Sea F un campo finito. En cuanto a los campos generales, se dice que un polinomio no constante f en F [ x ] es irreductible 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 los campos finitos de orden no primo. De hecho, para una potencia prima q , sea F q el campo finito con q elementos, únicos hasta el isomorfismo. Un polinomio f de grado n mayor que uno, que es irreductible sobre F q , define una extensión de campo de grado n que es isomorfa al campo con q n elementos: los elementos de esta extensión son los polinomios de grado menor que n ; la suma, resta y 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 GCD extendido (consulte Aritmética de extensiones algebraicas ).
De ello se deduce que, para calcular en un campo 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 campo, es habitual buscar polinomios de la forma x n + ax + b . [ cita requerida ]
Polinomio irreducible sobre campos finitos son también útiles para pseudoaleatorios generadores de números utilizando registros de desplazamiento de realimentación y del logaritmo discreto sobre F 2 n .
El número de polinomios mónicos irreductibles 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 n. [1]
Ejemplo
El polinomio P = x 4 + 1 es irreducible sobre Q pero no sobre ningún campo finito.
- En cualquier extensión de campo de F 2 , P = ( x +1) 4 .
- En todos los demás campos 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 luego
- Si luego
- Si luego
Complejidad
Los algoritmos de factorización polinomial utilizan operaciones polinomiales básicas 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 hacer en O ( n 2 ) operaciones en F q usando "classic "aritmética, o en O ( n log ( n ) log (log ( n ))) operaciones en F q usando aritmética" rápida " . Se puede realizar una división euclidiana (división con resto) dentro de los mismos límites de tiempo. El costo de un polinomio máximo común divisor 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 ( n log 2 ( n ) log (log ( n )) ) operaciones en F q utilizando 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 exponenciación por el método de cuadratura , es decir, O ( n 2 log ( q )) operaciones en F q usando métodos clásicos, u operaciones O ( n log ( q ) log ( n ) log (log ( n ))) 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 campos finitos incluyen las siguientes tres etapas:
- Factorización libre de cuadrados
- Factorización de grados distintos
- 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 en los elementos del campo de tierra, lo que implica que es practicable solo en pequeños campos finitos. Para un campo terrestre fijo, su complejidad de tiempo es polinomial, pero, para campos terrestres generales, la complejidad es exponencial en el tamaño del campo terrestre.
Factorización libre de cuadrados
El algoritmo determina una factorización libre de cuadrados para polinomios cuyos coeficientes provienen del campo finito F q de orden q = p m con p un primo. Este algoritmo determina primero la 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 campos 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 la inversa del automorfismo de Frobenius a los coeficientes. [ cita requerida ]
Este algoritmo trabaja también sobre un campo de característica cero, con la única diferencia de que nunca entra en los bloques de instrucciones, donde p se calculan º raíces. Sin embargo, en este caso, el algoritmo de Yun es mucho más eficiente porque calcula los mayores 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 de modo que permanezcan cuadrados- módulo gratis p .
Algoritmo : SFF (Factorización libre de cuadrados) Entrada : Un polinomio monico 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 mientras w ≠ 1 do y ← mcd ( w , c ) fac ← w / y R ← R · fac i w ← y ; c ← c / y ; i ← i + 1 final mientras que # 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 end 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 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 p -ésima raíz cuadrada y aplicar la recursividad.
Ejemplo de factorización libre de cuadrados
Dejar
factorizar sobre el campo con tres elementos.
El algoritmo calcula primero
Dado que la derivada no es cero, tenemos w = f / c = x 2 + 2 y entramos en el ciclo while. Después de un ciclo 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 también no cambia R . Por cuarta vez a través del bucle que 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 ciclo while. 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 no tiene cuadrados. Por lo tanto, al elevarlo al cubo y combinarlo con el valor de R hasta ese punto, se obtiene la descomposición sin cuadrados
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 Distinct grados (DDF) de entrada : Un cuadrado-libre mónico polinomio f ∈ F q [ x ] Salida : El conjunto de todos los pares ( g , d ) , de manera que f tiene un factor de irreducible de grado d y g es la producto de todos los factores mónicos irreductibles de f de grado d . Empezar tiempo hacer si g ≠ 1 , entonces ; finaliza si i : = i + 1; terminar mientras ; Si , a continuación, ; Si , luego regresa {( f , 1)} , de lo contrario regresa S End
La corrección del algoritmo se basa en lo siguiente:
Lema. Para i ≥ 1 el polinomio
es el producto de todos los polinomios mónicos irreducibles en F q [ x ] cuyo grado divide 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
puede ser reemplazado por
Por lo tanto, tenemos que calcular:
hay dos métodos:
Método I. Partir del valor de
calculado en el paso anterior y para calcular su q -ésimo módulo de potencia la nueva f * , usando exponenciación por el método de cuadratura . Esto necesita
operaciones aritméticas en F q en cada paso, y así
operaciones aritméticas para todo el algoritmo.
Método II. Usando el hecho de que la q -ésima potencia es un mapa lineal sobre F q podemos calcular su matriz con
operaciones. Luego, en cada iteración del ciclo, calcule el producto de una matriz por un vector (con operaciones O (deg ( f ) 2 )). Esto induce un número total de operaciones en F q que es
Por tanto, este segundo método es más eficaz y normalmente se prefiere. Además, la matriz que se calcula en este método se utiliza, por la mayoría de los algoritmos, para la factorización de igual grado (ver más abajo); por lo tanto, usarlo para la factorización de distintos grados 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 f univariante libre de cuadrados monicos , de grado n , sobre un campo finito F q , que tiene r ≥ 2 factores irreducibles distintos por parescada 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 ( 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 Algoritmo de Cantor-Zassenhaus. Entrada: Un campo finito F q de orden impar q . Un polinomio libre mónico cuadrado 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 monicos irreductibles de f .
Factores: = { f }; mientras que Tamaño (factores) < r , Elija h en F q [ x ] con grados ( h ) < n al azar; para cada u en Factores con deg ( u )> d do si mcd ( g , u ) ≠ 1 y mcd ( g , u ) ≠ u , entonces Factores: = Factores ; terminara si; terminar mientras 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 campos F q [ x ] / f i donde f i corre sobre los factores irreductibles de f . Como todos estos campos tienen q d elementos, el componente de g en cualquiera de estos campos es cero con probabilidad
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 ciclo while del algoritmo es menor que , dando un número promedio de operaciones aritméticas en F q que es. [2]
En el caso típico donde d log ( q )> n , esta complejidad puede reducirse a
eligiendo h en el núcleo del mapa lineal
y reemplazando la instrucción
por
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 para el algoritmo en sí, para el cálculo de la matriz del mapa lineal (que ya se puede calcular en la factorización libre de cuadrados) y O ( n 3 ) para calcular 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 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).
El 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. [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 campos primos F p .
La complejidad temporal del peor caso del algoritmo de Shoup tiene un factorAunque exponencial, esta complejidad es mucho mejor que los algoritmos deterministas anteriores (el 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 de tiempo promedio del algoritmo es polinomial endonde d es el grado del polinomio y p es el número de elementos del campo de tierra.
Sea g = g 1 ... g k la factorización deseada, donde g i son polinomios monic irreducibles distintos de grado d . Sea n = grados ( g ) = kd . Consideramos que el anillo de R = F q [ x ] / g y significan también por x la imagen de x en R . El anillo R es el producto directo de los campos R i = F q [ x ] / g i , y denotamos por p i el homomorfismo natural de R en R i . El grupo de Galois de R i sobre F q es cíclico de orden d , generado por el automorfismo de campo u → u p . De ello se deduce que las raíces de g i en R i son
Como en el algoritmo anterior, este algoritmo usa la misma subálgebra B de R que el algoritmo de Berlekamp , a veces llamado "Berlekamp subagebra" y definido como
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, un conjunto de separación se construye mediante la elección 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
Luego es un conjunto de separación porque 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á
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"por" elija h + i con h en S e i en {1, ..., k −1} ".
Complejidad del tiempo
Como se describió en secciones anteriores, para la factorización sobre campos finitos, existen algoritmos aleatorios de complejidad de tiempo polinómico (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 de Rabin [4] se basa en el Lema mencionado anteriormente. El algoritmo de factorización de grados distintos prueba cada d no más de 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 1 , ..., p k , todos los divisores primos de n , y denoten, 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 , yf divide. De hecho, si f tiene un factor de grado que no divide a n , entonces f no divide; si f tiene un factor de grado que divide n , entonces este factor divide al menos uno de los
Entrada de prueba de irreductibilidad del algoritmo de Rabin : Un polinomio monico f en F q [ x ] de grado n , p 1 , ..., p k todos los divisores primos distintos de n . Resultado : " f es irreducible" o " f es reducible". para j = 1 para k hacer ; para i = 1 para k hacer ; g : = mcd ( f , h ); si g ≠ 1, entonces devuelve " f es reducible" y STOP ; final para ; ; si g = 0, entonces devuelve " f es irreducible", de lo contrario devuelve " f es reducible"
La idea básica de este algoritmo es calcular comenzando desde el más pequeño cuadrando repetidamente o usando el automorfismo de Frobenius , y luego tomar el gcd correspondiente. Usando la aritmética polinomial elemental, el cálculo de la matriz del automorfismo de Frobenius necesitaoperaciones en F q , el cálculo de
necesita O ( n 3 ) operaciones adicionales, y el algoritmo mismo necesita O ( kn 2 ) operaciones, dando un total deoperaciones en F q . Usando aritmética rápida (complejidad para multiplicación y división, y para el cálculo de GCD), el cálculo de la por cuadratura repetida es , y el algoritmo en sí es , dando un total de operaciones en F q .
Ver también
- El 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 campos finitos Departamento de Ciencias de la Computación Universidad de Toronto
- Von Zur Gathen, J .; Panario, D. (2001). Factorización de polinomios sobre campos 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 campos 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) Nuevos algoritmos para encontrar polinomios irreducibles en 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. págs. xxii + 585. ISBN 0-7923-9259-0 .
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 campos finitos: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf
Notas
- ^ Christophe Reutenauer, Mots circulaires et polyinomes irreductibles , Ann. Sci. 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., 140 , Springer, págs. 239-251, doi : 10.1007 / BFb0012773 , ISBN 978-3-540-11576-2 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ Victor Shoup, Sobre la complejidad determinista de factorizar polinomios sobre campos 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 .