Polinomi primitiu

De Viquipèdia
Dreceres ràpides: navegació, cerca

Un polinomi primitiu pot referir-se a un dels dos següents conceptes:

Propietats[modifica | modifica el codi]

Com que tots els polinomis mínims són irreductibles, tots els polinomis primitius també ho són.

Tots els polinomis primitius tenen un nombre senar de termes, entre ells, el terme constant. Si un polinomi primitiu no té el terme constant aleshores x (la indeterminada) pot ser treta com a factor comú en tots els termes pel que el polinomi no és irreductible. Si un polinomi primitiu té un nombre parell de termes, aleshores (x + a) pot ser tret com a factor comú.

Un polinomi irreducible de grau m, F(x) sobre GF(p) per a un p primer, és primitiu si l'enter positiu n més petit tal que F(x) divideix xn − 1 és n = pm − 1.

Sobre GF(pm) hi ha exactament φ(pm − 1)/m polinomis primitius de grau m, on φ és funció fi d'Euler.

Totes les arrels d'un polinomi primitiu tenen ordre pm − 1.

Usos[modifica | modifica el codi]

Representació dels elements d'un cos[modifica | modifica el codi]

Els polinomis primitius es fan servir en la representació dels elements d'un cos finit. Si α ∈ GF(pm) és una arrel d'un polinomi primitiu F(x) aleshores l'ordre d'α és pm − 1 el que significa que tots els elements de GF(pm) poden ser representats com a les successives potències d'α:


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

Quan aquests elements són reduïts mòdul F(x) produeixen una representació en forma de base polinòmica de tots els elements del cos.

Generació de sequències pseudoaleatòries[modifica | modifica el codi]

Els polinomis primitius defineixen una relació de recurrència que pot ser utilitzada per a generar seqüències pseudoaleatòries.

Per exemple, donat el polinomi primitiu x10 + x3 + 1, comencem amb una llavor especificada per l'usuari (pot ser escollida a l'atzar, però no és una condició necessària). Aleshores prenen el 10º, 3º, i el 0º bit, començant pel menys significatiu, i operem amb una porta XOR, obtenim així un nou bit. La llavor es rota cap a l'esquerra i el nou bit es converteix en el menys significatiu de la llavor. Aquest procés pot ser repetit fins a generar 210-1 = 1023 bits pseudoaleatoris.

En general, per a un polinomi primitiu de grau m, aquest procés genera 2m bits pseudoaleatoris abans de repetir la mateixa sequència.

Veure[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]