Polinomio primitivo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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

Propiedades[editar]

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 xn − 1 es n = pm − 1.

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

Todas las raíces de un polinomio primitivo tienen orden pm − 1.

Usos[editar]

Representación de los elementos de un cuerpo[editar]

Los polinomios primitivos se usan en la representación de los elementos de un cuerpo finito. Si α ∈ GF(pm) es una raíz de un polinomio primitivo F(x) entonces el orden de α es pm − 1, lo que significa que todos los elementos de GF(pm) 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[editar]

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

Por ejemplo, dado el polinomio primitivo x10 + x3 + 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 210-1 = 1023 bits pseudoaleatorios.

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

Encontrar polinomios primitivos[editar]

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 2r−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 x6972593 + x3037958 + 1. Esto se puede utilizar para crear un generador de números al azar de períodos enormes 26972593−1,aproximadamente 102098959.[1]

Ver[editar]

Enlaces externos[editar]