Polinomi primitiu

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

• Un polinomi sobre un domini de factorizació única (com el dels enters) tal que el màxim comú divisor dels seus coeficients és u.
• El polinomi mínim d'un element primitiu d'una extensió de cossos GF(p^m).

Propietats

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 xⁿ − 1 és n = p^m − 1.

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

Totes les arrels d'un polinomi primitiu tenen ordre p^m − 1.

Usos

Representació dels elements d'un cos

Els polinomis primitius es fan servir en la representació dels elements d'un cos finit. Si α ∈ GF(p^m) és una arrel d'un polinomi primitiu F(x) aleshores l'ordre d'α és p^m − 1 el que significa que tots els elements de GF(p^m) 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 seqüències pseudoaleatòries

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 x¹⁰ + x³ + 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 2¹⁰-1 = 1023 bits pseudoaleatoris.

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

Veure

• LFSR

Enllaços externs

• MathWorld
• PlanetMath Arxivat 2007-01-17 a Wayback Machine.