Polinômio primitivo (teoria de corpos)

Na teoria de corpos finitos, um ramo da matemática, um polinômio primitivo é o polinômio mínimo de um elemento primitivo do corpo finito GF(p^m). Isto que dizer que um polinômio F(X) de grau m com coeficientes em GF(p) = Z/pZ é um polinômio primitivo se for mônico e possuir uma raiz α em GF(p^m) tal que ${\displaystyle \{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-2}\}}$ é todo o corpo GF(p^m). De onde decorre que α é uma raiz primitiva (p^m − 1) da unidade em GF(p^m).

• Como todos os polinômios mínimos são irredutíveis, todos os polinômios primitivos também são irredutíveis.
• Um polinômio primitivo deve ter um termo constante diferente de zero, caso contrário será divisível por x . Sobre GF(2), x + 1 é um polinômio primitivo e todos os outros polinômios primitivos têm um número ímpar de termos, já que qualquer polinômio mod 2 com um número par de termos é divisível por x + 1 (tem 1 como raiz).
• Um polinômio irredutível F( x ) de grau m sobre GF( p ), onde p é primo, é um polinômio primitivo se o menor inteiro positivo n tal que F ( x ) divide xⁿ − 1 for n = p^m − 1 .
• Um polinômio primitivo de grau m tem m raízes diferentes em GF(p^m), todas com ordem p^m − 1, o que significa que qualquer uma delas gera o grupo multiplicativo do corpo.
• Sobre GF( p ) existem exatamente φ(p^m − 1) elementos primitivos e φ(p^m − 1) / m polinômios primitivos, cada um de grau m, onde φ é a função totiente de Euler.
• Os conjugados algébricos de um elemento primitivo α em GF(p^m) são α, α^p, α^p2, …, α^pm−1 e assim o polinômio primitivo F(x) tem forma explícita F(x) = (x − α) (x − α^p) (x − α^p2) … (x − α^pm−1) . Que os coeficientes de um polinômio desta forma, para qualquer α em GF(pⁿ), não necessariamente primitivo, estejam em GF(p) decorre da propriedade de que o polinômio é invariante sob a aplicação do automorfismo de Frobenius aos seus coeficientes (usando α^pn = α ) e do fato de que o campo fixo do automorfismo de Frobenius é GF(p) .

Sobre GF(3) o polinômio x² + 1 é irredutível, mas não primitivo porque divide x⁴ − 1: suas raízes geram um grupo cíclico de ordem 4, enquanto o grupo multiplicativo de GF(3²) é um grupo cíclico de ordem 8. O polinômio x² + 2x + 2, por outro lado, é primitivo. Denote uma de suas raízes por α . Então, como os números naturais menores e primos relativos a 3² − 1 = 8 são 1, 3, 5 e 7, as quatro raízes primitivas em GF(3²) são α, α³ = 2α + 1, α⁵ = 2α e α⁷ = α + 2 . As raízes primitivas α e α³ são algebricamente conjugadas. De fato x² + 2x + 2 = (x − α) (x − (2α + 1)) . As restantes raízes primitivas α⁵ e α⁷ = (α⁵)³ também são algebricamente conjugadas e produzem outro polinômio primitivo: x² + x + 2 = (x − 2α) (x − (α + 2)) .

Para o grau 3, GF(3³) tem φ(3³ − 1) = φ(26) = 12 elementos primitivos. Como cada polinômio primitivo de grau 3 tem três raízes, todas necessariamente primitivas, temos 12 / 3 = 4 polinômios primitivos de grau 3. Um polinômio primitivo é x³ + 2x + 1 . Denotando uma de suas raízes por γ, os elementos algebricamente conjugados são γ³ e γ⁹ . Os demais polinômios primitivos estão associados a conjuntos algebricamente conjugados montados sobre outros elementos primitivos γ^r com r primo relativo a 26:

${\displaystyle {\begin{aligned}x^{3}+2x+1&=(x-\gamma )(x-\gamma ^{3})(x-\gamma ^{9})\\x^{3}+2x^{2}+x+1&=(x-\gamma ^{5})(x-\gamma ^{5\cdot 3})(x-\gamma ^{5\cdot 9})=(x-\gamma ^{5})(x-\gamma ^{15})(x-\gamma ^{19})\\x^{3}+x^{2}+2x+1&=(x-\gamma ^{7})(x-\gamma ^{7\cdot 3})(x-\gamma ^{7\cdot 9})=(x-\gamma ^{7})(x-\gamma ^{21})(x-\gamma ^{11})\\x^{3}+2x^{2}+1&=(x-\gamma ^{17})(x-\gamma ^{17\cdot 3})(x-\gamma ^{17\cdot 9})=(x-\gamma ^{17})(x-\gamma ^{25})(x-\gamma ^{23}).\end{aligned}}}$

Polinômios primitivos podem ser usados para representar os elementos de um corpo finito. Se α em GF(p^m) é uma raiz de um polinômio primitivo F(x), então os elementos diferentes de zero de GF(p^m) são representados como potências sucessivas de α:

${\displaystyle \mathrm {GF} (p^{m})=\{0,1=\alpha ^{0},\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.}$

Isso diminui a quantidade de armazenamento em um computador dos elementos diferentes de zero do corpo finito, com cada elemento representado pelo expoente correspondente de ${\displaystyle \alpha .}$ Esta representação facilita ainda a multiplicação, pois equivale à adição de expoentes módulo ${\displaystyle p^{m}-1.}$

Polinômios primitivos sobre GF(2), o corpo com dois elementos, podem ser usados para geração de bits pseudoaleatórios. Na verdade, cada registrador de deslocamento de feedback linear com comprimento de ciclo máximo (que é 2ⁿ − 1, onde n é o comprimento do registrador de deslocamento de feedback linear) pode ser construído a partir de um polinômio primitivo.^[1]

Em geral, para um polinômio primitivo de grau m sobre GF(2), esse processo gerará 2^m − 1 bits pseudoaleatórios antes de repetir a mesma sequência.

A verificação de redundância cíclica (CRC) é um código de detecção de erros que opera interpretando a sequência de bits da mensagem como os coeficientes de um polinômio sobre GF(2) e dividindo-a por um polinômio gerador fixo também sobre GF(2); veja Matemática do CRC. Polinômios primitivos, ou múltiplos deles, às vezes são uma boa escolha para polinômios geradores porque podem detectar de forma confiável erros de dois bits que ocorrem muito distantes na sequência de bits da mensagem, até uma distância de 2ⁿ − 1 para um polinômio primitivo de grau n .

Uma classe útil de polinômios primitivos são os trinômios primitivos, aqueles que têm apenas três termos diferentes de zero: x^r + x^k + 1. Sua simplicidade permite que os registradores de deslocamento de feedback linear sejam particularmente pequenos e rápidos.^[2] Vários resultados fornecem técnicas para localizar e testar a primitividade de trinômios.^[3]

Para polinômios sobre GF(2), onde 2^r − 1 é um primo de Mersenne, um polinômio de grau r é primitivo se e somente se for irredutível. (Dado um polinômio irredutível, ele não é primitivo somente se o período de x for um fator não trivial de 2^r − 1 . Os primos não têm fatores não triviais.) Embora o gerador de números pseudoaleatórios Mersenne Twister não use um trinômio, ele se vale dessa propriedade.

Richard Brent tem tabulado trinômios primitivos desta forma, como x^74207281 + x^30684570 + 1.^[4] Isso pode ser usado para criar um gerador de números pseudoaleatórios do período enorme 2^74207281 − 1 ≈ 7000300000000000000♠3.

• Weisstein, Eric W. «Primitive Polynomial». MathWorld (em inglês)