En la teoría de campos , una rama de las matemáticas , un polinomio primitivo es el polinomio mínimo de un elemento primitivo del campo de extensión finito GF ( p m ). En otras palabras, un polinomio F ( X ) con coeficientes en GF ( p ) = Z / p Z es un polinomio primitivo si su grado es my tiene una raíz α en GF ( p m ) tal que {0, 1, α , α 2 , α 3 , ..., α p m −2 }es el campo completo GF (p m ). Esto también significa queαes unaraízprimitiva ( p m - 1 ) de la unidaden GF (p m ).
Propiedades
Debido a que 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 menor entero positivo n tal que F ( x ) divide x n - 1 es n = p m - 1 .
Sobre GF ( p m ) hay exactamente φ ( p m - 1) / m polinomios primitivos de grado m , donde φ es la función totient de Euler .
Un polinomio primitivo de grado m tiene m raíces diferentes en GF ( p m ), todas las cuales tienen orden p m - 1 . Esto significa que, si α es tal raíz, entonces α p m −1 = 1 y α i ≠ 1 para 0 < i < p m - 1 .
El polinomio primitivo F ( x ) de grado m de un elemento primitivo α en GF ( p m ) tiene forma explícita F ( x ) = ( x - α ) ( x - α p ) ( x - α p 2 ) ⋅⋅⋅ ( x - α p m −1 ) .
Uso
Representación de elementos de campo
Los polinomios primitivos se utilizan en la representación de elementos de un campo finito . Si α en GF ( p m ) es una raíz de un polinomio primitivo F ( x ) entonces, dado que el orden de α es p m - 1, eso significa que todos los elementos distintos de cero de GF ( p m ) pueden representarse como potencias sucesivas de α :
Cuando estos elementos se reducen módulo F ( x ), proporcionan la representación de base polinomial de todos los elementos del campo.
Dado que el grupo multiplicativo de un campo finito es siempre un grupo cíclico , un polinomio primitivo f es un polinomio tal que x es un generador del grupo multiplicativo en GF ( p ) [ x ] / f ( x )
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 n - 1 , donde n es la longitud del registro de desplazamiento de retroalimentación lineal) puede construirse a partir de un polinomio primitivo. [1]
Por ejemplo, dado el polinomio primitivo p (x) = x 10 + x 3 + 1 , comenzamos con una semilla de 10 bits distinta de cero especificada por el usuario que ocupa las posiciones de bit 1 a 10, que representan los coeficientes de un polinomio sobre GF (2 ), comenzando por el bit menos significativo. (No es necesario que la semilla se elija al azar, pero puede serlo). Luego, la semilla se desplaza a la izquierda una posición para que el bit 0 se mueva a la posición 1, lo que logra multiplicar por x, el elemento primitivo de GF (2 ^ 10) [x] / p (x). Luego tomamos los bits 10 y 3, y creamos un nuevo bit 0, de modo que el xor de los tres bits sea 0, lo que realiza la división módulo p (x). Este proceso se puede repetir para generar 2 10 - 1 = 1023 bits pseudoaleatorios.
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, son a veces una buena opción para polinomios generadores porque pueden detectar de manera confiable errores de dos bits que ocurren muy separados en la cadena de bits del mensaje, hasta una distancia de 2 n - 1 para un polinomio primitivo de grado n .
Trinomios primitivos
Una clase útil de polinomios primitivos son los trinomios primitivos, los que tienen solo 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 . Varios resultados proporcionan técnicas para localizar y probar la primitividad de los trinomios.
Para polinomios sobre GF (2), donde 2 r - 1 es un número primo de Mersenne , un polinomio de grado r es primitivo si y solo si es irreducible. (Dado un polinomio irreducible, es no primitivo sólo si el período de x es un factor no trivial de 2 r - 1 . Primes no tienen factores no triviales). Aunque el Mersenne Twister generador de números pseudo-aleatoria no utiliza una trinomio, se aprovecha de esto.
Richard Brent ha estado tabulando trinomios primitivos de esta forma, como x 74207281 + x 30684570 + 1 . [2] [3] 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
- ^ C. Paar, J. Pelzl - Comprensión de la criptografía: un libro de texto para estudiantes y profesionales
- ^ Brent, Richard P. (4 de abril de 2016). "Búsqueda de trinomios primitivos (mod 2)" . Consultado el 4 de junio de 2020 .
- ^ Brent, Richard P .; Zimmermann, Paul (24 de mayo de 2016). "Doce nuevos trinomios binarios primitivos". arXiv : 1605.09213 [ math.NT ]. Parámetro desconocido
|url=
ignorado ( ayuda )