Polinomio primitivo (teoría de campos)

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

En la teoría ^de campos finitos , una rama de las matemáticas , un polinomio primitivo es el polinomio mínimo de un elemento primitivo del campo finito GF( pm ) . 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 sea el cuerpo completo GF ( pm ) .^​ 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, 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 mod 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 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 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 la 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 encuentran en GF( p ) se desprende 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 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 otro lado, es primitivo. Denota una de sus raíces por α . Entonces, debido a que los números naturales menores y primos relativos de 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 se conjugan algebraicamente 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 con 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, representando 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 longitud de ciclo máxima (que es 2 ⁿ − 1 , donde n es la longitud del registro de desplazamiento de retroalimentación lineal) puede construirse 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 verificación de redundancia cíclica (CRC) es un código de detección de errores que opera 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); ver Matemáticas de CRC . Los polinomios primitivos, o múltiplos de ellos, a veces son una buena opción para los polinomios generadores porque pueden detectar de manera confiable dos errores de bits 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 hace que los registros de desplazamiento de retroalimentación lineal sean particularmente pequeños y rápidos . ^[3] Varios resultados proporcionan técnicas para localizar y probar el carácter primitivo de 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 sólo si es irreducible. (Dado un polinomio irreducible, no es primitivo sólo 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, se aprovecha de 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 período enorme 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) vienen dadas por las secuencias A011260, A027385, A027741, A027743 y A319166 en línea. Enciclopedia de secuencias enteras .
2. C. Paar, J. Pelzl - Comprensión de la criptografía: un libro de texto para estudiantes y profesionales
3. Gentil, James E. (2003). Generación de números aleatorios y métodos de Monte Carlo (2 ed.). Nueva York: Springer. pag. 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 [matemáticas.NT].

enlaces externos

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