GF(2)
GF(2), em álgebra abstrata, é o corpo finito com dois elementos, 0 e 1.[1] A notação GF(pn) para o corpo finito com pn elementos foi introduzida por E. H. Moore em 1893.[2]
GF(2) também é representado como F2, {0, 1} ou . A notação não é recomendada, pois pode causar ambiguidade com o anel dos inteiros p-ádicos para p = 2.[1]
As operações de soma a produto neste corpo são definidas como:[1]
- 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:[Nota 1]
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
As operações de soma e produto correspondem às operações disjunção exclusiva (xor) e conjunção lógica (and).[3]
Note-se que, neste corpo, -1 = 1 e 2 = 1 + 1 = 0.[1]
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 . x4 + 0 . x3 + 0 . x2 + 0 . x + 1 . x0 = x4 + 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.[1]
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) = x2 + x + 1 e Q(x) = 1.[1]
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 x9 + x8 + x4 + x2, e determinar o resíduo deste polinômio quando dividido por um polinômio gerador, como por exemplo x3 + x + 1. Neste caso, o resíduo da divisão de x9 + x8 + x4 + x2 por x3 + x + 1 é o polinômio x2, que é representado em binário como 100.[1]
O único polinômio irreducível de grau 2 em GF(2) é x2 + x + 1. Se β e δ forem as duas raízes deste polinômio,[Nota 2] então é possível construir um corpo com quatro elementos, 0, 1, β e δ (chamado de GF(4)) no qual temos as operações β + β = 0, β + 1 = δ, β x β = δ, β x δ = 1, etc.[Nota 3][4]
Notas e referências
Notas
- ↑ Nenhuma fonte consultada continha esta tabela.
- ↑ 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)(y2). O polinômio x^2 + y^2 é irreducível em GF(2)(y2), porém ele tem duas raízes iguais a y na extensão algébrica GF(2)(y) de GF(2)(y2).
- ↑ Foram aqui omitidas as operações óbvias decorrentes dos axiomas de corpo.
Referências
- ↑ a b c d e f g Garrett, The finite field with 2 elements [em linha]
- ↑ David A. Fox, Galois Theory (2004), Errata [https://web.archive.org/web/20140108152835/http://www.cs.amherst.edu/~dac/galois/typos.pdf Arquivado em 8 de janeiro de 2014, no Wayback Machine. [em linha]]
- ↑ Xinmiao Zhang, Finite Field Arithmetic and Implementations [em linha]
- ↑ John Gill Stanford University, Notes #4 October 22, Handout #11 [em linha]