Polinomio primitivo

Un polinomio primitivo puede referirse a uno de los dos siguientes conceptos:

Un polinomio sobre un dominio de factorización única (como el de los enteros) tal que el máximo común divisor de sus coeficientes es 1.
El polinomio mínimo de un elemento primitivo de una extensión de cuerpos GF(p^m).

YouTube Encyclopedic

1/2
Views:
2 136
2 522

Transcription

Propiedades

Como todos los polinomios mínimos son irreducibles, todos los polinomios primitivos también lo son.

Todos los polinomios primitivos tienen un número impar de términos, entre ellos, el término constante. Si un polinomio primitivo no tiene el término constante entonces x (la indeterminada) puede ser sacada como factor común en todos los términos por lo que el polinomio no es irreducible. Si un polinomio primitivo tiene un número par de términos, entonces (x + a) puede ser sacado como factor común.

Un polinomio irreducible de grado m, F(x) sobre GF(p) para un p primo, es primitivo si el entero positivo n más pequeño tal que F(x) divide xⁿ − 1 es n = p^m − 1.

Sobre GF(p^m) hay exactamente φ(p^m − 1)/m polinomios primitivos de grado m, donde φ es función fi de Euler.

Todas las raíces de un polinomio primitivo tienen orden p^m − 1.

Usos

Representación de los elementos de un cuerpo

Los polinomios primitivos se usan en la representación de los elementos de un cuerpo finito. Si α ∈ GF(p^m) es una raíz de un polinomio primitivo F(x) entonces el orden de α es p^m − 1, lo que significa que todos los elementos de GF(p^m) pueden ser representados como las sucesivas potencias de α:

\{0,1,\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}

Cuando estos elementos son reducidos módulo F(x) producen una representación en forma de base polinómica de todos los elementos del cuerpo.

Generación de secuencias pseudoaleatorias

Los polinomios primitivos definen una relación de recurrencia que puede ser usada para generar secuencias pseudoaleatorias.

Por ejemplo, dado el polinomio primitivo x¹⁰ + x³ + 1, empezamos con una semilla especificada por el usuario (puede ser escogida al azar, pero no es una condición necesaria). Entonces tomamos el 10.º, 3º, y el 0º bit, empezando por el menos significativo, y operamos con una puerta XOR todo ellos, obteniendo así un nuevo bit. La semilla se rota hacia la izquierda y el nuevo bit se convierte en el menos significativo de la semilla. Este proceso puede ser repetido hasta generar 2¹⁰-1 = 1023 bits pseudoaleatorios.

En general, para un polinomio primitivo de grado m, este proceso genera 2^m bits pseudoaleatorios antes de repetir la misma secuencia.

Encontrar polinomios primitivos

La clase más útil de polinomios primitivos es la de trinomios primitivos, esos que tienen solamente tres términos distintos a cero, porque son los más simples y resultan los más eficientes generadores de números al azar. Un número de resultados dan técnicas para localizar y testear la primitividad de trinomios. Una prueba simple es la siguiente: para cada r tal que 2^r−1 es un primo de Mersenne, un trinomio de grado r es primitivo si y solo si es irreducible. Los algoritmos recientemente inventados por Richard Brent han permitido el descubrimiento de trinomios primitivos de grado muy grande, por ejemplo x^6972593 + x^3037958 + 1. Esto se puede utilizar para crear un generador de números al azar de períodos enormes 2^6972593−1,aproximadamente 10^2098959.[1]