Mostrar código-fonte de GF(2)

'''GF(2)''', em [[álgebra abstrata]], é o [[corpo finito]] com [[dois]] elementos, ''[[zero|0]]'' e ''[[um|1]]''.<ref name="garrett.gf2">Garrett, ''The finite field with 2 elements'' [http://www.math.umn.edu/~garrett/coding/Overheads/08_crcs.pdf <nowiki>[em linha]</nowiki>]</ref> A notação [[GF(p^n)|GF(p<sup>n</sup>)]] para o corpo finito com ''p<sup>n</sup>'' elementos foi introduzida por [[E. H. Moore]] em [[1893]].<ref>[[David A. Fox]], ''Galois Theory'' (2004), ''Errata'' [http://www.cs.amherst.edu/~dac/galois/typos.pdf {{Wayback|url=http://www.cs.amherst.edu/~dac/galois/typos.pdf |date=20140108152835 }} <nowiki>[em linha]</nowiki>]</ref>

''GF(2)'' também é representado como '''F<sub>2</sub>''', '''{0, 1}''' ou <math>\mathbb{Z}/2 \mathbb{Z}</math>. A notação <math>\mathbb{Z}_2\,</math> não é recomendada, pois pode causar ambiguidade com o anel dos [[inteiros p-ádicos]] para ''p = 2''.<ref name="garrett.gf2" />

As operações de soma a produto neste corpo são definidas como:<ref name="garrett.gf2" />
: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0
: 0 x 0 = 0, 0 x 1 = 0, 1 x 0 = 0, 1 x 1 = 1

Ou, como tabela:<ref group="Nota">Nenhuma fonte consultada continha esta tabela.</ref>

{| class="wikitable" style="text-align:center"
|-
! + !! 0 !! 1
|-
! 0
| 0 || 1
|-
! 1
| 1 || 0
|}

{| class="wikitable" style="text-align:center"
|-
! × !! 0 !! 1
|-
! 0
| 0 || 0
|-
! 1
| 0 || 1
|}

As operações de soma e produto correspondem às operações [[disjunção exclusiva]] (''[[Ou exclusivo|xor]])'' e [[conjunção lógica]] (''[[and]])''.<ref name="xinmiao.zhang">Xinmiao Zhang, ''Finite Field Arithmetic and Implementations'' [http://faculty.washington.edu/manisoma/ee540/EE540finite.pdf <nowiki>[em linha]</nowiki>]</ref>

Note-se que, neste corpo, ''[[menos um|-1]] = 1'' e ''2 = 1 + 1 = 0''.<ref name="garrett.gf2" />

Um [[polinômio]] sobre GF(2) na variável ''x'' é uma expressão análoga a um polinômio usual (com coeficientes reais), só que seus coeficientes são os elementos ''0'' e ''1'', de GF(2), por exemplo, ''P(x) = 1 . x<sup>4</sup> + 0 . x<sup>3</sup> + 0 . x<sup>2</sup> + 0 . x + 1 . x<sup>0</sup> = x<sup>4</sup> + 1''. Assim como no caso dos polinômios reais, quando o coeficiente de um termo é 0, este termo não é representado, quando o coefieciente é 1, representa-se apenas a parte em ''x''.<ref name="garrett.gf2" />

Para cada polinômio temos uma [[função polinomial]], que consiste em substituir ''x'' por ''0'' e por ''1'' e efetuar as contas. Diferente do caso real, é possível que dois polinômios diferentes gerem duas funções polinomiais iguais, por exemplo, ''P(x) = x<sup>2</sup> + x + 1'' e ''Q(x) = 1''.<ref name="garrett.gf2" />

O método conhecido como [[CRC]], para identificação de erros, se baseia em tratar sequências de bits, como ''1100010100'', como polinômios em GF(2), no caso ''x<sup>9</sup> + x<sup>8</sup> + x<sup>4</sup> + x<sup>2</sup>'', e determinar o [[resíduo (álgebra)|resíduo]] deste polinômio quando dividido por um polinômio gerador, como por exemplo ''x<sup>3</sup> + x + 1''. Neste caso, o resíduo da divisão de ''x<sup>9</sup> + x<sup>8</sup> + x<sup>4</sup> + x<sup>2</sup>'' por ''x<sup>3</sup> + x + 1'' é o polinômio ''x<sup>2</sup>'', que é representado em binário como ''100''.<ref name="garrett.gf2" />

O único [[polinômio irreducível]] de grau 2 em GF(2) é ''x<sup>2</sup> + x + 1''. Se ''&beta;'' e ''&delta;'' forem as duas raízes deste polinômio,<ref group="Nota">Para corpos de característica diferente de 0, é possível haver casos em que um polinômio irreducível tem raízes iguais. Como exemplo, considere ''y'' um elemento transcendente sobre GF(2), e o corpo ''GF(2)(y<sup>2</sup>)''. O polinômio ''x^2 + y^2'' é irreducível em ''GF(2)(y<sup>2</sup>)'', porém ele tem duas raízes iguais a ''y'' na [[extensão algébrica]] ''GF(2)(y)'' de ''GF(2)(y<sup>2</sup>)''.</ref> então é possível construir um corpo com quatro elementos, ''0'', ''1'', ''&beta;'' e ''&delta;'' (chamado de [[GF(4)]]) no qual temos as operações ''&beta; + &beta; = 0'', ''&beta; + 1 = &delta;'', ''&beta; x &beta; = &delta;'', ''&beta; x &delta; = 1'', etc.<ref group="Nota">Foram aqui omitidas as operações óbvias decorrentes dos axiomas de corpo.</ref><ref>''John Gill Stanford University'', ''Notes #4 October 22, Handout #11'' [http://www.stanford.edu/class/ee387/handouts/notes4.pdf <nowiki>[em linha]</nowiki>]</ref>

{{notas e referências}}

[[Categoria:Álgebra]]