Corpo finito

thumb|right|Defeitos de gravação, desgaste e poeira observados na superfície de um CD requerem uma codificação redundante das informações, permitindo corrigir os erros de leitura. Essa detecção e correção de erros utiliza o código Reed–Solomon em um corpo finito de elementos. Em matemática, especificamente na álgebra abstrata, um corpo finito é um corpo que também é finito. Em termos de isomorfismo, um corpo finito é completamente determinado por sua cardinalidade, que é sempre uma potência de um número primo, sendo esse número primo sua característica. Para todo número primo e todo inteiro não nulo , existe um corpo de cardinalidade , que se apresenta como a única extensão de grau do corpo primo .

Os corpos finitos são utilizados na teoria algébrica dos números, onde surgem como uma estrutura essencial na geometria aritmética. Essa área possibilitou, entre outras coisas, a demonstração do último teorema de Fermat.

Os corpos finitos encontraram novas aplicações com o desenvolvimento da ciência da computação. Na teoria de códigos, por exemplo, eles permitem determinar códigos corretivos eficazes. Também têm um papel na criptografia, tanto no desenvolvimento de criptografias de chave simétrica, como no padrão AES, quanto na concepção de criptografias de chave pública, como no problema de logaritmo discreto, entre outros.

Os corpos finitos também foram (ou são) chamados de corpos de Galois. Eles foram de fato estudados por Évariste Galois em um artigo publicado em 1830, sendo o ponto de partida da teoria. Na realidade, Carl Friedrich Gauss já havia descoberto os resultados de Galois no final do século XVIII, mas não os divulgou; seus trabalhos só foram conhecidos após sua morte e não tiveram a mesma influência que os de Galois.

O corpo finito de ordem (sempre uma potência de um número primo) é denotado como (do inglês field, que significa corpo) ou (Galois field).

Construção de corpos finitos A ferramenta que permite a construção de corpos finitos é a relação de congruência: congruência sobre os inteiros para os corpos finitos primos, congruência sobre os polinômios com coeficientes num corpo finito primo para o caso geral. O menor corpo O menor corpo finito é denotado por F2. É composto por dois elementos distintos, 0, que é o elemento neutro para a adição, e 1, que é o elemento neutro para a multiplicação. Isto determina as tabelas destas duas operações, exceto para 1+1, que só pode ser 0, pois 1 deve ter um oposto. Verifica-se então que elas definem de fato um corpo comutativo. + 0 1 0 0 1 1 1 0 . 0 1 0 0 0 1 0 1 O corpo F2 pode ser interpretado de diversas formas. É o anel Z/2Z, os inteiros tomados módulo 2, ou seja, 0 representa os inteiros pares, 1 os inteiros ímpares (é o resto da sua divisão por 2), e as operações deduzem-se das operações sobre Z.

É também o conjunto dos valores lógicos clássicos, 0 para falso e 1 para verdadeiro. A adição é o "ou exclusivo" (xor), a multiplicação o "e".Para o conjunto da seção, ver Demazure 2008, § 6.1, p. 147.

As funções de (F2)n em F2 são chamadas funções booleanas.Por exemplo, Demazure 2008, p. 173. A disjunção (inclusiva) e a negação definem-se assim: x ou y = x + y + xy ; não x = 1 + x. Mais geralmente, deduz-se do teorema de interpolação de Lagrange que todas as funções booleanas são polinomiais (esta é uma propriedade que se estende a qualquer corpo finito).

Corpos primos finitos Uma generalização natural de F2 = Z/2Z é, para p primo, o corpo Z/pZ com p elementos, denotado também por Fp:

Proposição. — O anel Z/nZ é um corpo se e somente se n é um número primo.

Com efeito, p ser primo equivale a que 0 não seja produto de dois inteiros não nulos módulo p, pelo lema de Euclides. É, portanto, necessário que p seja primo para que Z/pZ seja um corpo. Além disso, isto garante que, se p é primo, Z/pZ é um domínio de integridade e, por conseguinte, como é finito, um corpo. O teorema de Bachet-Bézout garante diretamente a existência de um inverso e um cálculo eficiente do mesmo através do algoritmo de Euclides estendido.

O grupo multiplicativo de Z/pZ (p primo) é de ordem p – 1, o que conduz ao pequeno teorema de Fermat pelo teorema de Lagrange. Demonstra-se que este grupo é cíclico (a demonstração é a mesma do caso geral, tratado na seção Grupo multiplicativo e consequências).Por exemplo, Demazure 2008, pp. 73-74.

Ver-se-á que para todo o número primo p, Z/pZ é, a menos de isomorfismo, o único corpo de cardinalidade p, e que não contém nenhum outro subcorpo além de si próprio. Um tal corpo é chamado corpo primo, e os Z/pZ, com p primo, são os únicos corpos primos finitos.

Quociente por um polinômio irredutível Para construir novos corpos finitos, utiliza-se a estrutura de anel euclidiano de Fp[X] da mesma forma que se utilizou a de Z para construir os corpos primos. Os polinômios irredutíveis desempenham o papel dos números primos. Dois polinômios são equivalentes módulo o polinômio P se tiverem o mesmo resto na divisão por ele. O quociente pela relação de equivalência obtida é denotado por Fp[X]/(P), onde (P) := P Fp[X], e a estrutura induzida por quociente é ainda a de um anel.Ver Demazure 2008, § 3.2.6, p. 84.

Tem-se, de forma estritamente análoga ao caso dos inteiros:

Proposição. — O anel Fp[X]/(P) é um corpo se e somente se P é um polinômio irredutível.

Seja n o grau de P. A propriedade de unicidade do resto da divisão polinomial traduz-se pelo fato de cada elemento de Fp[X]/(P) ser representado por um único polinômio de grau < n. A cardinalidade de Fp[X]/(P) é, portanto, pn. Para construir um corpo finito de cardinalidade pn, basta assim encontrar um polinômio irredutível de grau n em Fp[X].

Se P é irredutível, o quociente K = Fp[X]/(P) é então um corpo de raízes (corpo de decomposição) do polinômio P, pois a classe de X é uma raiz de P em K.

Para estas construções é indispensável que os polinômios sejam polinômios formais, e não funções polinomiais. Existem, de fato, polinômios não nulos cujas funções polinomiais associadas são identicamente nulas sobre Fp (por exemplo, X + X2 sobre F2). Outra forma de perceber a diferença é que só pode existir um número finito de funções de Fp em Fp e, portanto, de funções polinomiais, enquanto existe um número infinito de polinômios formais.

Exemplo: os corpos com p2 elementos Pode-se assim construir os corpos com p2 elementos, mostrando que existe um polinômio irredutível P de grau 2 em Fp[X]. O corpo Fp[X]/(P) possui p2 elementos, e é uma extensão quadrática de Fp. Ver-se-á mais adiante que o corpo com p2 elementos é único (a menos de isomorfismo) e denotar-se-á por Fp2. Em particular, o corpo que vamos construir é, na verdade, independente da escolha do polinômio irredutível P de grau 2 utilizado para o quociente. Esta extensão quadrática de Fp é o análogo da extensão quadrática (única) do corpo dos números reais, que dá o corpo dos números complexos.

Para p = 2, o polinômio 1 + X + X2 é irredutível em F2[X] (é, aliás, o único polinômio irredutível de grau 2 sobre F2). A extensão correspondente é um corpo denotado por F4. Este corpo tem exatamente 4 elementos, que são 0, 1, e as duas raízes φ e φ² = φ + 1 de 1 + X + X2. As suas operações são então: + 0 1 φ φ² 0 0 1 φ φ² 1 1 0 φ² φ φ φ φ² 0 1 φ² φ² φ 1 0 • 0 1 φ φ² 0   0   0 0 0 1 0 1 φ φ² φ 0 φ φ² 1 φ² 0 φ² 1 φ

Quando p é primo ímpar, um polinômio da forma X2 – a é irredutível se e somente se a não for um quadrado. Ora, para p diferente de 2, existem em Fp elementos não quadrados. De fato, os quadrados dos p – 1 elementos não nulos de Fp são em número de (p – 1)/2 (cada quadrado não nulo é o quadrado de exatamente dois elementos, opostos um do outro), logo restam (p – 1)/2 elementos não quadrados, entre os quais se pode escolher a. Para p congruente a 3 módulo 4, neste caso p é um número primo de Gauss, pode-se mesmo escolher simplesmente a = –1 (ver o artigo Teorema de Fermat sobre a soma de dois quadrados ou o artigo Lei da reciprocidade quadrática), de modo que Fp2 é isomorfo ao corpo Z[i]/pZ[i], pois têm a mesma cardinalidade.

Estrutura dos corpos finitos Nesta seção, detalham-se as principais propriedades da estrutura dos corpos finitos, a saberLidl & Niederreiter 1997.:

todo corpo finito possui como cardinalidade a potência de um número primo, e existe, a menos de isomorfismo, um único corpo para cada cardinalidade dada; o grupo multiplicativo de um corpo finito é cíclico; um subcorpo de um corpo de cardinalidade ( primo) tem cardinalidade onde divide , e para cada divisor de , o corpo de cardinalidade contém um único subcorpo de cardinalidade .

Característica e cardinalidade Seja um corpo finito, com e sendo os elementos neutros aditivo e multiplicativo. Denota-se por o resultado da adição de iterada vezes. A aplicação correspondente é compatível com a adição e a multiplicação (é o único morfismo de anéis unitários de em ).

A característica do corpo é o menor inteiro tal que (tal número existe pois o grupo aditivo gerado por é finito). Além disso, é um número primo. De fato, se e são inteiros tais que , então . Como é um corpo, ou é nulo, logo, pela definição de , ou vale . Verifica-se então que o homomorfismo de em que associa a induz uma injeção de em ; sua imagem é um subcorpo de isomorfo a . Este subcorpo está contido em qualquer outro subcorpo de . É, portanto, o menor subcorpo de , denominado subcorpo primo de . Pela mesma razão, é o único subcorpo de isomorfo a , podendo ser identificado com .

Se é um subcorpo de , ou seja, se é uma extensão de , possui naturalmente uma estrutura de espaço vetorial sobre . No caso de corpos finitos, sua dimensão é necessariamente finita. A cardinalidade de é então , onde é a dimensão de como espaço vetorial sobre seu subcorpo primo . De forma geral, a cardinalidade de um subcorpo de é da forma , e como também é um espaço vetorial sobre , é um divisor de . Assim:

Proposição. — A cardinalidade de um corpo finito K é uma potência de um número primo p que é sua característica. Além disso, se este corpo tem cardinalidade , todo subcorpo de K tem cardinalidade , onde d divide n.Demazure 2008, pp. 209-210; Perrin 1981, cap. III.8.

Automorfismo de Frobenius Seja um corpo finito de característica , de cardinalidade . Como é primo, divide cada um dos coeficientes binomiais para . Tem-se, portanto:Deduz-se disso que a aplicação de em si mesmo que associa a é um endomorfismo de corpo, logo injetivo, que deixa o subcorpo primo estável (pelo Pequeno teorema de Fermat). Este é chamado de Endomorfismo de Frobenius. Sendo o corpo finito, o endomorfismo é uma bijeção (automorfismo).

É simples verificar que o conjunto dos pontos fixos de um automorfismo em um corpo é um subcorpo. No caso do automorfismo de Frobenius, este subcorpo é, por definição, o conjunto das raízes do polinômio , de cardinalidade no máximo ; logo, é o subcorpo primo de .Perrin 1981, cap. III.9.

Existência e unicidade de um corpo finito de cardinalidade Seja um corpo finito de cardinalidade . Então, , o grupo multiplicativo deste corpo, tem cardinalidade . Deduz-se do teorema de Lagrange que todo elemento de é raiz do polinômio , e portanto todo corpo de cardinalidade é um corpo de decomposição do polinômio sobre . Consequentemente, dois corpos de cardinalidade são isomorfos.

Seja agora um inteiro estritamente positivo, e o corpo de decomposição do polinômio sobre o corpo . O conjunto das raízes de em é o conjunto de pontos fixos do automorfismo de Frobenius iterado vezes (). Ele forma, portanto, um subcorpo de , que é o próprio pela definição de corpo de decomposição. Como o polinômio derivado de é , que é constante e não nulo, não possui raízes múltiplas, possuindo raízes distintas. O corpo tem, assim, cardinalidade . Em resumo:

Proposição. — Existe um corpo de cardinalidade , único a menos de isomorfismo, denotado por Fq. Uma clausura algébrica de Fp contém um único corpo de cardinalidade q, que é o corpo de decomposição de .