Polinomi primitiu

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

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

Propietats

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

Tots els polinomis primitius tenen un número impar de térmens, entre ells, el terme constant. Si un polinomi primitiu no té el terme constant llavors x (l'indeterminada) pot ser treta com a factor comú en tots els térmens per lo que el polinomi no és irreducible. Si un polinomi primitiu té un número par de térmens, llavors (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 el sancer positiu n més chicotet tal que F(x) dividix xⁿ − 1 és n = p^m − 1.

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

Totes les raïls d'un polinomi primitiu tenen orde p^m − 1.

Usos

Representació dels elements d'un cos

Els polinomis primitius s'usen en la representació dels elements d'un cos finito. Si α ∈ GF(p^m) és una raïl d'un polinomi primitiu F(x) llavors l'orde de α és p^m − 1, lo que significa que tots els elements de GF(p^m) poden ser representats com les successives potències de α:

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

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

Generació de seqüències pseudoaleatorias

Els polinomis primitius definixen una relació de recurrencia que pot ser usada per a generar seqüències pseudoaleatorias.

Per eixemple, donat el polinomi primitiu x¹⁰ + x³ + 1, escomencem en una llavor especificada per l'usuari (pot ser triada a l'encert, pero no és una condició necessària). Llavors prenem el 10.º, 3º, i el 0º bit, escomençant pel menys significatiu, i operem en una porta XOR tot ells, obtenint aixina un nou bit. La llavor es trencada cap a l'esquerra i el nou bit es convertix en el menys significatiu de la llavor. Este procés pot ser repetit fins a generar 2¹⁰-1 = 1023 bits pseudoaleatorios.

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