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 Predefinição:Math. Isto que dizer que um polinômio Predefinição:Math de grau Predefinição:Mvar com coeficientes em Predefinição:Math é um polinômio primitivo se for mônico e possuir uma raiz Predefinição:Math em Predefinição:Math tal que $\{0,1,\alpha ,{\alpha }^2,{\alpha }^3,\dots {\alpha }^{p^m-2}\}$ é todo o corpo Predefinição:Math. De onde decorre que Predefinição:Math é uma [[Raiz da unidade|raiz primitiva (Predefinição:Math) da unidade]] em Predefinição:Math.

Propriedades

• 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), Predefinição:Nowrap é 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 Predefinição:Nowrap (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 Predefinição:Nowrap for Predefinição:Nowrap .
• Um polinômio primitivo de grau Predefinição:Mvar tem Predefinição:Mvar raízes diferentes em Predefinição:Math, todas com ordem Predefinição:Math, o que significa que qualquer uma delas gera o grupo multiplicativo do corpo.
• Sobre GF( p ) existem exatamente Predefinição:Math elementos primitivos e Predefinição:Math polinômios primitivos, cada um de grau Predefinição:Mvar, onde Predefinição:Mvar é a função totiente de Euler.
• Os conjugados algébricos de um elemento primitivo Predefinição:Mvar em Predefinição:Math são Predefinição:Mvar, Predefinição:Math, Predefinição:Math, …, Predefinição:Math e assim o polinômio primitivo Predefinição:Math tem forma explícita Predefinição:Math . Que os coeficientes de um polinômio desta forma, para qualquer Predefinição:Mvar em Predefinição:Math, não necessariamente primitivo, estejam em Predefinição:Math decorre da propriedade de que o polinômio é invariante sob a aplicação do automorfismo de Frobenius aos seus coeficientes (usando Predefinição:Math ) e do fato de que o campo fixo do automorfismo de Frobenius é Predefinição:Math .

Exemplos

Sobre Predefinição:Math o polinômio Predefinição:Math é irredutível, mas não primitivo porque divide Predefinição:Math: suas raízes geram um grupo cíclico de ordem 4, enquanto o grupo multiplicativo de Predefinição:Math é um grupo cíclico de ordem 8. O polinômio Predefinição:Math, por outro lado, é primitivo. Denote uma de suas raízes por Predefinição:Mvar . Então, como os números naturais menores e primos relativos a Predefinição:Math são 1, 3, 5 e 7, as quatro raízes primitivas em Predefinição:Math são Predefinição:Mvar, Predefinição:Math, Predefinição:Math e Predefinição:Math . As raízes primitivas Predefinição:Mvar e Predefinição:Math são algebricamente conjugadas. De fato Predefinição:Math . As restantes raízes primitivas Predefinição:Math e Predefinição:Math também são algebricamente conjugadas e produzem outro polinômio primitivo: Predefinição:Math .

Para o grau 3, Predefinição:Math tem Predefinição:Math elementos primitivos. Como cada polinômio primitivo de grau 3 tem três raízes, todas necessariamente primitivas, temos Predefinição:Math polinômios primitivos de grau 3. Um polinômio primitivo é Predefinição:Math . Denotando uma de suas raízes por Predefinição:Mvar, os elementos algebricamente conjugados são Predefinição:Math e Predefinição:Math . Os demais polinômios primitivos estão associados a conjuntos algebricamente conjugados montados sobre outros elementos primitivos Predefinição:Math com Predefinição:Mvar primo relativo a 26:

$\begin{array}{cc}{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{array}$

Aplicações

Representação de elementos de corpo

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 α:

$\mathrm{G}\mathrm{F}(p^m)=\{0,1={\alpha }^0,\alpha ,{\alpha }^2,\dots ,{\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 $\alpha .$ Esta representação facilita ainda a multiplicação, pois equivale à adição de expoentes módulo $p^m-1.$

Geração de bits pseudo-aleatórios

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 é Predefinição:Nowrap, onde n é o comprimento do registrador de deslocamento de feedback linear) pode ser construído a partir de um polinômio primitivo.

Em geral, para um polinômio primitivo de grau m sobre GF(2), esse processo gerará Predefinição:Nowrap bits pseudoaleatórios antes de repetir a mesma sequência.

Códigos CRC

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 Predefinição:Nowrap para um polinômio primitivo de grau n .

Trinômios primitivos

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

Para polinômios sobre GF(2), onde Predefinição:Nowrap é 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 Predefinição:Nowrap . 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 Predefinição:Nowrap. Isso pode ser usado para criar um gerador de números pseudoaleatórios do período enorme Predefinição:Nowrap ≈ Predefinição:Val.

Ligações externas

• Predefinição:MathWorld