Polinomio primitivo (teoría de campos)

Polinomio mínimo de un elemento primitivo en un cuerpo finito

En la teoría de cuerpos finitos , una rama de las matemáticas , un polinomio primitivo es el polinomio mínimo de un elemento primitivo del cuerpo finito GF( p ^m ) . Esto significa que un polinomio F ( X ) de grado m con coeficientes en GF( p ) = Z / p Z es un polinomio primitivo si es mónico y tiene una raíz α en GF( p ^m ) tal que es el cuerpo entero GF( p ^m ) . Esto implica que α es una raíz primitiva ( p m − 1 ) de la unidad en GF( p ^m ) . ${\displaystyle \{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-2}\}}$

Propiedades

• Como todos los polinomios mínimos son irreducibles , todos los polinomios primitivos también son irreducibles.
• Un polinomio primitivo debe tener un término constante distinto de cero, ya que de lo contrario será divisible por  x . Sobre GF(2) , x + 1 es un polinomio primitivo y todos los demás polinomios primitivos tienen un número impar de términos, ya que cualquier polinomio módulo 2 con un número par de términos es divisible por x + 1 (tiene 1 como raíz).
• Un polinomio irreducible F ( x ) de grado m sobre GF( p ), donde p es primo, es un polinomio primitivo si el entero positivo más pequeño n tal que F ( x ) divide a x ⁿ − 1 es n = p ^m − 1 .
• Un polinomio primitivo de grado m tiene m raíces diferentes en GF( p ^m ) , las cuales tienen todas orden p ^m − 1 , lo que significa que cualquiera de ellas genera el grupo multiplicativo del campo.
• Sobre GF( p ) hay exactamente φ ( p ^m − 1) elementos primitivos y φ ( p ^m − 1) / m polinomios primitivos, cada uno de grado m , donde φ es la función totiente de Euler . ^[1]
• Los conjugados algebraicos de un elemento primitivo α en GF( p ^m ) son α , α ^p , α ^{p 2} , …, α ^{p m −1} y por lo tanto el polinomio primitivo F ( x ) tiene forma explícita F ( x ) = ( x − α ) ( x − α ^p ) ( x − α ^{p 2} ) … ( x − α ^{p m −1} ) . Que los coeficientes de un polinomio de esta forma, para cualquier α en GF( p ⁿ ) , no necesariamente primitivo, se encuentren en GF( p ) se deduce de la propiedad de que el polinomio es invariante bajo la aplicación del automorfismo de Frobenius a sus coeficientes (usando α ^{p n} = α ) y del hecho de que el campo fijo del automorfismo de Frobenius es GF( p ) .

Ejemplos

Sobre GF(3) el polinomio x ² + 1 es irreducible pero no primitivo porque divide a x ⁴ − 1 : sus raíces generan un grupo cíclico de orden 4, mientras que el grupo multiplicativo de GF(3 ² ) es un grupo cíclico de orden 8. El polinomio x ² + 2 x + 2 , por otra parte, es primitivo. Denotemos una de sus raíces por α . Entonces, como los números naturales menores que y primos entre sí con 3 ² − 1 = 8 son 1, 3, 5 y 7, las cuatro raíces primitivas en GF(3 ² ) son α , α ³ = 2 α + 1 , α ⁵ = 2 α y α ⁷ = α + 2 . Las raíces primitivas α y α ³ son algebraicamente conjugadas. De hecho, x ² + 2 x + 2 = ( x − α ) ( x − (2 α + 1)) . Las raíces primitivas restantes α ⁵ y α ⁷ = ( α ⁵ ) ³ también son algebraicamente conjugadas y producen el segundo polinomio primitivo: x ² + x + 2 = ( x − 2 α ) ( x − ( α + 2)) .

Para el grado 3, GF(3 ³ ) tiene φ (3 ³ − 1) = φ (26) = 12 elementos primitivos. Como cada polinomio primitivo de grado 3 tiene tres raíces, todas necesariamente primitivas, hay 12 / 3 = 4 polinomios primitivos de grado 3. Un polinomio primitivo es x ³ + 2 x + 1 . Denotando una de sus raíces por γ , los elementos algebraicamente conjugados son γ ³ y γ ⁹ . Los otros polinomios primitivos están asociados a conjuntos algebraicamente conjugados construidos sobre otros elementos primitivos γ ^r con r relativamente primo a 26:

${\displaystyle {\begin{aligned}x^{3}+2x+1&=(x-\gamma )(x-\gamma ^{3})(x-\gamma ^{9})\\x^{3}+2x^{2}+x+1&=(x-\gamma ^{5})(x-\gamma ^{5\cdot 3})(x-\gamma ^{5\cdot 9})=(x-\gamma ^{5})(x-\gamma ^{15})(x-\gamma ^{19})\\x^{3}+x^{2}+2x+1&=(x-\gamma ^{7})(x-\gamma ^{7\cdot 3})(x-\gamma ^{7\cdot 9})=(x-\gamma ^{7})(x-\gamma ^{21})(x-\gamma ^{11})\\x^{3}+2x^{2}+1&=(x-\gamma ^{17})(x-\gamma ^{17\cdot 3})(x-\gamma ^{17\cdot 9})=(x-\gamma ^{17})(x-\gamma ^{25})(x-\gamma ^{23}).\end{aligned}}}$

Aplicaciones

Representación de elementos de campo

Los polinomios primitivos se pueden utilizar para representar los elementos de un cuerpo finito . Si α en GF( p ^m ) es una raíz de un polinomio primitivo F ( x ), entonces los elementos distintos de cero de GF( p ^m ) se representan como potencias sucesivas de α :

${\displaystyle \mathrm {GF} (p^{m})=\{0,1=\alpha ^{0},\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.}$

Esto permite una representación económica en una computadora de los elementos distintos de cero del campo finito, al representar un elemento por el exponente correspondiente de Esta representación facilita la multiplicación, ya que corresponde a la suma de exponentes módulo ${\displaystyle \alpha .}$ ${\displaystyle p^{m}-1.}$

Generación de bits pseudoaleatorios

Los polinomios primitivos sobre GF(2), el campo con dos elementos, se pueden utilizar para la generación de bits pseudoaleatorios . De hecho, cada registro de desplazamiento de retroalimentación lineal con una longitud de ciclo máxima (que es 2 ⁿ − 1 , donde n es la longitud del registro de desplazamiento de retroalimentación lineal) se puede construir a partir de un polinomio primitivo. ^[2]

En general, para un polinomio primitivo de grado m sobre GF(2), este proceso generará 2 ^m − 1 bits pseudoaleatorios antes de repetir la misma secuencia.

Códigos CRC

La comprobación de redundancia cíclica (CRC) es un código de detección de errores que funciona interpretando la cadena de bits del mensaje como los coeficientes de un polinomio sobre GF(2) y dividiéndolo por un polinomio generador fijo también sobre GF(2); consulte Matemáticas de CRC . Los polinomios primitivos, o múltiplos de ellos, son a veces una buena opción para los polinomios generadores porque pueden detectar de manera confiable dos errores de bit que ocurren muy separados en la cadena de bits del mensaje, hasta una distancia de 2 ⁿ − 1 para un polinomio primitivo de grado n .

Trinomios primitivos

Una clase útil de polinomios primitivos son los trinomios primitivos, aquellos que tienen sólo tres términos distintos de cero: x ^r + x ^k + 1 . Su simplicidad permite obtener registros de desplazamiento con retroalimentación lineal particularmente pequeños y rápidos . ^[3] Una serie de resultados proporcionan técnicas para localizar y probar la primitividad de los trinomios. ^[4]

Para polinomios sobre GF(2), donde 2 ^r − 1 es un primo de Mersenne , un polinomio de grado r es primitivo si y solo si es irreducible. (Dado un polinomio irreducible, no es primitivo solo si el período de x es un factor no trivial de 2 ^r − 1 . Los primos no tienen factores no triviales). Aunque el generador de números pseudoaleatorios Mersenne Twister no utiliza un trinomio, sí aprovecha esto.

Richard Brent ha estado tabulando trinomios primitivos de esta forma, como x ^74207281 + x ^30684570 + 1. [ ^{5] [6]} Esto se puede utilizar para crear un generador de números pseudoaleatorios del enorme período 2 ^74207281 − 1 ≈3 × 10 ^{22 338 617} .

Referencias

1. Las enumeraciones de polinomios primitivos por grado sobre GF(2) , GF(3) , GF(5) , GF(7) y GF(11) se dan mediante las secuencias A011260, A027385, A027741, A027743 y A319166 en la Enciclopedia en línea de secuencias de enteros .
2. C. Paar, J. Pelzl - Comprensión de la criptografía: un libro de texto para estudiantes y profesionales
3. Gentle, James E. (2003). Generación de números aleatorios y métodos de Monte Carlo (2.ª edición). Nueva York: Springer. pág. 39. ISBN 0-387-00178-6.OCLC 51534945  .
4. Zierler, Neal; Brillhart, John (diciembre de 1968). "Sobre trinomios primitivos (Mod 2)". Información y Control . 13 (6): 541, 548, 553. doi :10.1016/S0019-9958(68)90973-X.
5. Brent, Richard P. (4 de abril de 2016). «Búsqueda de trinomios primitivos (mod 2)» . Consultado el 25 de mayo de 2024 .
6. Brent, Richard P. ; Zimmermann, Paul (24 de mayo de 2016). "Doce nuevos trinomios binarios primitivos". arXiv : 1605.09213 [math.NT].

Enlaces externos

• Weisstein, Eric W. "Polinomio primitivo". MundoMatemático .