Mostrar código-fonte de Polinômio primitivo (teoria de corpos)

Na [[Corpo (matemática)|teoria de corpos finitos]], um ramo da [[matemática]], um '''polinômio primitivo''' é o [[polinômio mínimo]] de um [[Elemento primitivo (campo finito)|elemento primitivo]] do [[corpo finito]] {{Math|GF(''p''<sup>''m''</sup>)}}. Isto que dizer que um polinômio {{Math|''F''(''X'')}} de grau {{Mvar|m}} com coeficientes em {{Math|1=GF(''p'') = '''Z'''/''p'''''Z'''}} é um ''polinômio primitivo'' se for [[Polinômios mônicos|mônico]] e possuir uma raiz {{Math|''α''}} em {{Math|GF(''p''<sup>''m''</sup>)}} tal que <math>\{0,1,\alpha, \alpha^2,\alpha^3, \ldots \alpha^{p^m-2}\}</math> é todo o corpo {{Math|GF(''p''<sup>''m''</sup>)}}. De onde decorre que {{Math|''α''}} é uma [[Raiz da unidade|raiz primitiva ({{Math|''p''<sup>''m''</sup> − 1}}) da unidade]] em {{Math|GF(''p''<sup>''m''</sup>)}}.

== Propriedades ==

* Como todos os polinômios mínimos são [[Polinômio irredutível|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&nbsp;''x'' . Sobre [[GF(2)]], {{Nowrap|''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 {{Nowrap|''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 {{Nowrap|''x''<sup>''n''</sup> − 1}} for {{Nowrap|1=''n'' = ''p''<sup>''m''</sup> − 1}} .
* Um polinômio primitivo de grau {{Mvar|m}} tem {{Mvar|m}} raízes diferentes em {{Math|GF(''p''<sup>''m''</sup>)}}, todas com [[Ordem (teoria dos grupos)|ordem]] {{Math|''p''<sup>''m''</sup> − 1}}, o que significa que qualquer uma delas gera o [[Corpo finito|grupo multiplicativo]] do corpo.
* Sobre GF( ''p'' ) existem exatamente {{Math|''φ''(''p''<sup>''m''</sup> − 1)}} elementos primitivos e {{Math|''φ''(''p''<sup>''m''</sup> − 1) / ''m''}} polinômios primitivos, cada um de grau {{Mvar|m}}, onde {{Mvar|φ}} é [[Função totiente de Euler|a função totiente de Euler]].
* Os conjugados algébricos de um elemento primitivo {{Mvar|α}} em {{Math|GF(''p''<sup>''m''</sup>)}} são {{Mvar|α}}, {{Math|''α''{{i sup|''p''}}}}, {{Math|''α''{{i sup|''p''{{sup|2}}}}}}, …, {{Math|''α''{{i sup|''p''{{sup|''m''−1}}}}}} e assim o polinômio primitivo {{Math|''F''(''x'')}} tem forma explícita {{Math|''F''(''x'') {{=}} (''x'' − ''α'') (''x'' − ''α''{{i sup|''p''}}) (''x'' − ''α''{{i sup|''p''{{sup|2}}}}) … (''x'' − ''α''{{i sup|''p''{{sup|''m''−1}}}})}} . Que os coeficientes de um polinômio desta forma, para qualquer {{Mvar|α}} em {{Math|GF(''p''<sup>''n''</sup>)}}, não necessariamente primitivo, estejam em {{Math|GF(''p'')}} decorre da propriedade de que o polinômio é invariante sob a aplicação do [[Endomorfismo de Frobenius|automorfismo de Frobenius]] aos seus coeficientes (usando {{Math|''α''<sup>''p''<sup>''n''</sup></sup> {{=}} ''α''}} ) e do fato de que o campo fixo do [[automorfismo]] de Frobenius é {{Math|GF(''p'')}} .

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

Para o grau 3, {{Math|GF(3<sup>3</sup>)}} tem {{Math|''φ''(3<sup>3</sup> − 1) {{=}} ''φ''(26) {{=}} 12}} elementos primitivos. Como cada polinômio primitivo de grau 3 tem três raízes, todas necessariamente primitivas, temos {{Math|12 / 3 {{=}} 4}} polinômios primitivos de grau 3. Um polinômio primitivo é {{Math|''x''<sup>3</sup> + 2''x'' + 1}} . Denotando uma de suas raízes por {{Mvar|γ}}, os elementos algebricamente conjugados são {{Math|''γ''<sup>3</sup>}} e {{Math|''γ''<sup>9</sup>}} . Os demais polinômios primitivos estão associados a conjuntos algebricamente conjugados montados sobre outros elementos primitivos {{Math|''γ''<sup>''r''</sup>}} com {{Mvar|r}} [[Números primos entre si|primo relativo]] a 26:

: <math>\begin{align}x^3+2x+1 & = (x-\gamma)(x-\gamma^3)(x-\gamma^9)\\
x^3+2x^2+x+1 &= (x-\gamma^5)(x-\gamma^{5\cdot3})(x-\gamma^{5\cdot9}) = (x-\gamma^5)(x-\gamma^{15})(x-\gamma^{19})\\
x^3+x^2+2x+1 &= (x-\gamma^7)(x-\gamma^{7\cdot3})(x-\gamma^{7\cdot9}) = (x-\gamma^7)(x-\gamma^{21})(x-\gamma^{11})\\
x^3+2x^2+1 &= (x-\gamma^{17})(x-\gamma^{17\cdot3})(x-\gamma^{17\cdot9}) = (x-\gamma^{17})(x-\gamma^{25})(x-\gamma^{23}).
\end{align}</math>

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

: <math>
\mathrm{GF}(p^m) = \{ 0, 1= \alpha^0, \alpha, \alpha^2, \ldots, \alpha^{p^m-2} \} .
</math>

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 <math>\alpha.</math> Esta representação facilita ainda a multiplicação, pois equivale à adição de expoentes [[Aritmética modular|módulo]] <math>p^m-1.</math>

=== Geração de bits pseudo-aleatórios ===
Polinômios primitivos sobre GF(2), o corpo com dois elementos, podem ser usados para [[Gerador de números pseudoaleatórios|geração de bits pseudoaleatórios]]. Na verdade, cada [[registrador de deslocamento de feedback linear]] com comprimento de ciclo máximo (que é {{Nowrap|2<sup>''n''</sup> − 1}}, onde ''n'' é o comprimento do registrador de deslocamento de ''feedback'' linear) pode ser construído a partir de um polinômio primitivo.<ref>C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners</ref>

Em geral, para um polinômio primitivo de grau ''m'' sobre GF(2), esse processo gerará {{Nowrap|2<sup>''m''</sup> − 1}} bits pseudoaleatórios antes de repetir a mesma sequência.

=== Códigos CRC ===
A [[CRC|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 {{Nowrap|2<sup>''n''</sup> − 1}} 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: {{Nowrap|''x<sup>r</sup>'' + ''x<sup>k</sup>'' + 1}}. Sua simplicidade permite que [[Registrador de deslocamento de feedback linear|os registradores de deslocamento de feedback linear]] sejam particularmente pequenos e rápidos.<ref>{{Citar livro|url=https://www.worldcat.org/oclc/51534945|título=Random number generation and Monte Carlo methods|ultimo=Gentle|primeiro=James E.|data=2003|editora=Springer|localização=New York|páginas=39|isbn=0-387-00178-6|oclc=51534945|edição=2}}</ref> Vários resultados fornecem técnicas para localizar e testar a primitividade de trinômios.<ref>{{Citar periódico |título=On primitive trinomials (Mod 2) |data=dezembro 1968 |periódico=Information and Control |número=6 |ultimo=Zierler |primeiro=Neal |ultimo2=Brillhart |primeiro2=John |paginas=541, 548, 553 |lingua=en |doi=10.1016/S0019-9958(68)90973-X |volume=13 |doi-access=}}</ref>

Para polinômios sobre GF(2), onde {{Nowrap|2<sup>''r''</sup> − 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 {{Nowrap|2<sup>''r''</sup> − 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 Peirce Brent|Richard Brent]] tem tabulado trinômios primitivos desta forma, como {{Nowrap|''x''<sup>74207281</sup> + ''x''<sup>30684570</sup> + 1}}.<ref>{{Citar web|ultimo=Brent|primeiro=Richard P.|url=https://maths-people.anu.edu.au/~brent/trinom.html|titulo=Search for Primitive Trinomials (mod&nbsp;2)|data=4 abril 2016|acessodata=25 maio 2024}}</ref> Isso pode ser usado para criar um gerador de números pseudoaleatórios do período enorme {{Nowrap|2<sup>74207281</sup> − 1}} ≈ {{Val|3}}.

== Referências ==
{{Reflist}}

== Ligações externas ==

* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>{{MathWorld|id=PrimitivePolynomial|titulo=Primitive Polynomial}}

[[Categoria:Polinómios]]
[[Categoria:Teoria dos corpos]]