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 . Isto que dizer que um polinômio de grau com coeficientes em é um polinômio primitivo se for mônico e possuir uma raiz em tal que é todo o corpo . De onde decorre que é uma raiz primitiva () da unidade em .

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

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

Para o grau 3, tem elementos primitivos. Como cada polinômio primitivo de grau 3 tem três raízes, todas necessariamente primitivas, temos polinômios primitivos de grau 3. Um polinômio primitivo é . 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 com primo relativo a 26:

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(pm) é uma raiz de um polinômio primitivo F(x), então os elementos diferentes de zero de GF(pm) são representados como potências sucessivas de α:

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 Esta representação facilita ainda a multiplicação, pois equivale à adição de expoentes módulo

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 é , onde n é o comprimento do registrador de deslocamento de feedback linear) pode ser construído a partir de um polinômio primitivo.C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners

Em geral, para um polinômio primitivo de grau m sobre GF(2), esse processo gerará 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 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: . 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 é 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 . 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 . Isso pode ser usado para criar um gerador de números pseudoaleatórios do período enorme ≈ .

Referências

Ligações externas

Categoria:Polinómios Categoria:Teoria dos corpos