Corpo finito
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 p e todo inteiro não nulo n, existe um corpo de cardinalidade pn, que se apresenta como a única extensão de grau n do corpo primo Z/pZ.
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. 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".
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).
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. 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].
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.
Nesta seção, detalham-se as principais propriedades da estrutura dos corpos finitos, a saber:
Característica e cardinalidade
Seja K {\displaystyle K} um corpo finito, com 0 K {\displaystyle 0_{K}} e 1 K {\displaystyle 1_{K}} sendo os elementos neutros aditivo e multiplicativo. Denota-se por n ⋅ 1 K {\displaystyle n\cdot 1_{K}} o resultado da adição de 1 K {\displaystyle 1_{K}} iterada n {\displaystyle n} vezes. A aplicação correspondente é compatível com a adição e a multiplicação (é o único morfismo de anéis unitários de Z {\displaystyle \mathbb {Z} } em K {\displaystyle K} ). A característica do corpo K {\displaystyle K} é o menor inteiro p > 0 {\displaystyle p>0} tal que p ⋅ 1 K = 0 K {\displaystyle p\cdot 1_{K}=0_{K}} (tal número existe pois o grupo aditivo gerado por 1 K {\displaystyle 1_{K}} é finito). Além disso, p {\displaystyle p} é um número primo. De fato, se a {\displaystyle a} e b {\displaystyle b} são inteiros tais que a b = p {\displaystyle ab=p} , então ( a ⋅ 1 K ) ( b ⋅ 1 K ) = ( a b ) ⋅ 1 K = 0 K {\displaystyle (a\cdot 1_{K})(b\cdot 1_{K})=(ab)\cdot 1_{K}=0_{K}} . Como K {\displaystyle K} é um corpo, a ⋅ 1 K {\displaystyle a\cdot 1_{K}} ou b ⋅ 1 K {\displaystyle b\cdot 1_{K}} é nulo, logo, pela definição de p {\displaystyle p} , a {\displaystyle a} ou b {\displaystyle b} vale p {\displaystyle p} . Verifica-se então que o homomorfismo de Z {\displaystyle \mathbb {Z} } em K {\displaystyle K} que associa n {\displaystyle n} a n ⋅ 1 K {\displaystyle n\cdot 1_{K}} induz uma injeção de Z / p Z {\displaystyle \mathbb {Z} /p\mathbb {Z} } em K {\displaystyle K} ; sua imagem é um subcorpo de K {\displaystyle K} isomorfo a Z / p Z {\displaystyle \mathbb {Z} /p\mathbb {Z} } . Este subcorpo está contido em qualquer outro subcorpo de K {\displaystyle K} . É, portanto, o menor subcorpo de K {\displaystyle K} , denominado subcorpo primo de K {\displaystyle K} . Pela mesma razão, é o único subcorpo de K {\displaystyle K} isomorfo a Z / p Z {\displaystyle \mathbb {Z} /p\mathbb {Z} } , podendo ser identificado com F p {\displaystyle \mathbb {F} _{p}} .
Automorfismo de Frobenius
Seja K {\displaystyle K} um corpo finito de característica p {\displaystyle p} , de cardinalidade q = p n {\displaystyle q=p^{n}} . Como p {\displaystyle p} é primo, p {\displaystyle p} divide cada um dos coeficientes binomiais ( p i ) {\displaystyle {\binom {p}{i}}} para 0 < i < p {\displaystyle 0<i<p} . Tem-se, portanto: Deduz-se disso que a aplicação de K {\displaystyle K} em si mesmo que associa x {\displaystyle x} a x p {\displaystyle x^{p}} é 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).
Existência e unicidade de um corpo finito de cardinalidade p n {\displaystyle p^{n}}
Seja K {\displaystyle K} um corpo finito de cardinalidade q = p n {\displaystyle q=p^{n}} . Então, K ∗ {\displaystyle K^{*}} , o grupo multiplicativo deste corpo, tem cardinalidade q − 1 {\displaystyle q-1} . Deduz-se do teorema de Lagrange que todo elemento de K ∗ {\displaystyle K^{*}} é raiz do polinômio X q − 1 − 1 {\displaystyle X^{q-1}-1} , e portanto todo corpo de cardinalidade q {\displaystyle q} é um corpo de decomposição do polinômio X q − X {\displaystyle X^{q}-X} sobre F p {\displaystyle \mathbb {F} _{p}} . Consequentemente, dois corpos de cardinalidade q {\displaystyle q} são isomorfos. Seja agora n {\displaystyle n} um inteiro estritamente positivo, q = p n {\displaystyle q=p^{n}} e K {\displaystyle K} o corpo de decomposição do polinômio P ( X ) = X q − X {\displaystyle P(X)=X^{q}-X} sobre o corpo F p {\displaystyle \mathbb {F} _{p}} . O conjunto das raízes de X q − X {\displaystyle X^{q}-X} em K {\displaystyle K} é o conjunto de pontos fixos do automorfismo de Frobenius iterado n {\displaystyle n} vezes ( q = p n {\displaystyle q=p^{n}} ). Ele forma, portanto, um subcorpo de K {\displaystyle K} , que é o próprio K {\displaystyle K} pela definição de corpo de decomposição. Como o polinômio derivado de P ( X ) = X q − X {\displaystyle P(X)=X^{q}-X} é P ′ ( X ) = q X q − 1 − 1 = − 1 {\displaystyle P'(X)=qX^{q-1}-1=-1} , que é constante e não nulo, X q − X {\displaystyle X^{q}-X} não possui raízes múltiplas, possuindo q {\displaystyle q} raízes distintas. O corpo K {\displaystyle K} tem, assim, cardinalidade q = p n {\displaystyle q=p^{n}} . Em resumo:
Grupo multiplicativo e consequências
O grupo ( F q ∗ , × ) {\displaystyle (\mathbb {F} _{q}^{*},\times )} é um grupo abeliano finito, portanto seu expoente e {\displaystyle e} é a ordem de pelo menos um elemento x {\displaystyle x} do grupo. O polinômio X e − 1 {\displaystyle X^{e}-1} , de grau e {\displaystyle e} , possui q − 1 {\displaystyle q-1} raízes distintas em F q {\displaystyle \mathbb {F} _{q}} , o que implica que e ≥ q − 1 {\displaystyle e\geq q-1} . Conclui-se que o subgrupo gerado por x {\displaystyle x} é igual ao grupo inteiro: Proposição. — O grupo multiplicativo de um corpo finito é cíclico. Um gerador de F q ∗ {\displaystyle \mathbb {F} _{q}^{*}} é chamado de elemento primitivo (é uma raiz primitiva da unidade de ordem q − 1 {\displaystyle q-1} ). Todo corpo finito F q {\displaystyle \mathbb {F} _{q}} é a extensão de seu subcorpo primo definida pela adjunção de um elemento primitivo α {\displaystyle \alpha } .
Teoria de Galois e Clausura Algébrica
Um corpo finito é um corpo perfeito, o que significa que suas extensões algébricas são separáveis. O corpo F p n {\displaystyle \mathbb {F} _{p^{n}}} é uma extensão de Galois de F p {\displaystyle \mathbb {F} _{p}} . O grupo de Galois absoluto Gal ( F p alg / F p ) {\displaystyle {\text{Gal}}(\mathbb {F} _{p}^{\text{alg}}/\mathbb {F} _{p})} é o limite projetivo dos grupos Gal ( F p n / F p ) ≃ Z / n Z {\displaystyle {\text{Gal}}(\mathbb {F} _{p^{n}}/\mathbb {F} _{p})\simeq \mathbb {Z} /n\mathbb {Z} } , resultando no completado profinito Z ^ {\displaystyle {\hat {\mathbb {Z} }}} . Esta descrição completa é fundamental na Teoria dos corpos de classes, onde os corpos residuais de corpos de números ou corpos p-ádicos são corpos finitos.
Um critério de irredutibilidade
Se dois polinômios P e Q de K[X] possuem uma raiz comum numa extensão L de K, e se P for irredutível, então P divide Q. Com efeito, caso contrário, esses polinômios seriam primos entre si, o que se manteria em L pela Identidade de Bézout para polinômios. Este resultado preliminar é útil para estabelecer: Proposição. — Sejam Fq um corpo finito com q elementos e n um inteiro estritamente positivo. Em Fq[X], o polinômio Xqn – X é igual ao produto de todos os polinômios mônicos irredutíveis de grau d, onde d divide n. Demonstração: O polinômio X q n − X {\displaystyle X^{q^{n}}-X} possui derivada –1 e, portanto, não possui fator múltiplo. Para demonstrar a proposição, basta estabelecer que os divisores irredutíveis deste polinômio são exatamente os polinômios irredutíveis de grau que divide n.
Polinômio minimal
Num corpo finito F q {\displaystyle \mathbb {F} _{q}} , todo o elemento α é algébrico sobre o seu subcorpo primo F p {\displaystyle \mathbb {F} _{p}} (na verdade, sobre qualquer subcorpo), o que significa que existe um polinômio com coeficientes em F p {\displaystyle \mathbb {F} _{p}} que anula α (as potências sucessivas de α não podem ser independentes). O polinômio mônico com coeficientes em F p {\displaystyle \mathbb {F} _{p}} de menor grau que anula α é chamado de polinômio minimal de α sobre F p {\displaystyle \mathbb {F} _{p}} . Ele é necessariamente irredutível e gera o ideal dos polinômios que anulam α. Sendo os coeficientes do polinômio invariantes pelo automorfismo de Frobenius e seus iterados, os α p i {\displaystyle \alpha ^{p^{i}}} são igualmente raízes deste polinômio. Demonstra-se que não existem outras.
Polinômios primitivos e polinômios ciclotômicos
Seja p um número primo, n um inteiro estritamente positivo e q = pn. Deduziu-se do teorema de Lagrange que todo o elemento não nulo de F q {\displaystyle \mathbb {F} _{q}} é uma raiz da unidade e, portanto, raiz do polinômio X q − 1 − 1 {\displaystyle X^{q-1}-1} . Esta propriedade é ilustrada na figura à direita: os três elementos não nulos de F 4 {\displaystyle \mathbb {F} _{4}} são as três raízes da unidade. Sendo os polinômios ciclotômicos de coeficientes inteiros, eles interpretam-se também nos corpos finitos, mas embora sejam irredutíveis em Q {\displaystyle \mathbb {Q} } , não o são necessariamente num subcorpo primo F p {\displaystyle \mathbb {F} _{p}} . Em Z [ X ] {\displaystyle \mathbb {Z} [X]} , X q − 1 − 1 {\displaystyle X^{q-1}-1} é o produto dos polinômios ciclotômicos cujo índice divide q – 1, e isto passa para F p {\displaystyle \mathbb {F} _{p}} . Por outro lado, um polinômio irredutível P de grau estritamente superior a 1 é tal que F p [ X ] / ( P ) {\displaystyle \mathbb {F} _{p}[X]/(P)} é um corpo finito, e P, polinômio minimal de um elemento deste corpo, divide X q − 1 − 1 {\displaystyle X^{q-1}-1} , logo:
Exemplos
Existem sobre F 2 {\displaystyle \mathbb {F} _{2}} exatamente dois polinômios de grau 1, um dos quais — o polinômio ciclotômico de índice 1 sobre F 2 {\displaystyle \mathbb {F} _{2}} — é primitivo: As raízes do (ou dos) polinômio(s) de grau 2 irredutíveis sobre F 2 {\displaystyle \mathbb {F} _{2}} são os elementos de F 4 {\displaystyle \mathbb {F} _{4}} que não pertencem a F 2 {\displaystyle \mathbb {F} _{2}} . São, portanto, os 2 geradores do grupo multiplicativo F 4 ∗ {\displaystyle \mathbb {F} _{4}^{*}} com três elementos. Por conseguinte, existe de fato um único polinômio irredutível de grau 2 sobre F 2 {\displaystyle \mathbb {F} _{2}} , ele é primitivo, e é o polinômio ciclotômico de índice três:
Equação diofantina
Uma equação diofantina é uma equação com coeficientes inteiros onde se procuram soluções inteiras. Pierre de Fermat dedicou-se longamente a equações desta natureza. O Pequeno teorema de Fermat estipula que, se p {\displaystyle p} é primo, então todo o número inteiro elevado à potência p {\displaystyle p} é congruente a esse mesmo inteiro módulo p {\displaystyle p} . No contexto dos corpos finitos, isto equivale a indicar que os pontos fixos do automorfismo de Frobenius são os elementos do corpo primo, ou que o grupo multiplicativo deste último é cíclico de ordem p − 1 {\displaystyle p-1} . Fermat notou que os únicos números primos que são soma de dois quadrados são aqueles cuja divisão por quatro tem 1 como resto. Ele observou que:
Código corretor de erros
Os códigos corretores de erros têm a sua origem num problema muito concreto ligado à transmissão de dados: em certos casos, a transmissão é feita através de um canal de comunicação que não é inteiramente fiável; por outras palavras, os dados estão sujeitos a alterações durante o percurso. O objetivo de um código corretor é fornecer uma redundância de informação de tal modo que o erro possa ser detetado e até corrigido. Uma mensagem é uma sucessão finita de "letras", que no caso de um código linear são consideradas elementos de um corpo finito. Uma mensagem m {\displaystyle m} surge como um elemento de um espaço vetorial E {\displaystyle E} sobre um corpo finito de dimensão k {\displaystyle k} . O aporte de redundância é o resultado de uma aplicação linear injetiva ϕ {\displaystyle \phi } de E {\displaystyle E} num espaço F {\displaystyle F} , chamado "código", de dimensão n {\displaystyle n} superior a k {\displaystyle k} . A "palavra de código" transmitida é o elemento ϕ ( m ) {\displaystyle \phi (m)} . O interesse em transmitir ϕ ( m ) {\displaystyle \phi (m)} em vez de m {\displaystyle m} é ilustrado na figura seguinte:
A teoria dos corpos finitos desenvolveu-se, num primeiro momento, como o estudo das congruências, tanto sobre inteiros quanto sobre polinômios, e depois, a partir do final do século XIX, no âmbito de uma teoria geral dos corpos comutativos.
Congruências e imaginários de Galois
O estudo dos corpos finitos primos foi tratado sistematicamente, sob a forma de congruências, por Gauss em suas Disquisitiones arithmeticae, publicadas em 1801, embora muitas dessas propriedades já tivessem sido estabelecidas por, entre outros, Fermat, Euler, Lagrange e Legendre. Em 1830, Évariste Galois publicou o que é considerado o artigo fundador da teoria geral dos corpos finitos. Galois, que declarou inspirar-se nos trabalhos de Gauss sobre as congruências inteiras, tratou de congruências polinomiais para um polinômio irredutível com coeficientes tomados eles próprios módulo um número primo p {\displaystyle p} . Mais precisamente, Galois introduziu uma "raiz imaginária" de uma congruência P ( x ) ≡ 0 ( mod p ) {\displaystyle P(x)\equiv 0{\pmod {p}}} , onde P {\displaystyle P} é um polinômio irredutível módulo p {\displaystyle p} . Ele denotou por i {\displaystyle i} essa raiz e trabalhou sobre as expressões:
Teoria dos corpos
Em 1893, o matemático americano E. H. Moore demonstrou que um corpo (comutativo) finito é caracterizado pelo seu cardinal; um corpo finito é um conjunto de símbolos, de cardinalidade finita s {\displaystyle s} , dotado das quatro operações sujeitas às identidades ordinárias da álgebra abstrata. Moore mostrou que tal corpo é a "forma abstrata" de um "campo de Galois" (em inglês: Galois field) de cardinalidade s = p n {\displaystyle s=p^{n}} , definido à maneira de Galois e Serret. A primeira apresentação moderna da teoria dos corpos finitos deve-se ao seu antigo aluno L. E. Dickson, em 1901. Joseph Wedderburn, que trabalhou em colaboração com Dickson na Universidade de Chicago, demonstrou em 1905 que não existem corpos finitos não comutativos. A estrutura dos corpos finitos estava inteiramente elucidada.
Aplicações teóricas
Os corpos finitos são, em particular, utilizados na aritmética, fundamentando, por exemplo, a aritmética modular, que permitiu a Gauss demonstrar a Lei da reciprocidade quadrática. A estrutura de corpo intervém nomeadamente na resolução de equações diofantinas. O Pequeno teorema de Fermat é um exemplo arquetípico. Emil Artin utilizou o fato de que um contexto natural das leis de reciprocidade é o dos corpos finitos. Esta foi uma das ferramentas que lhe permitiu resolver o Nono problema de Hilbert. Ele iniciou a análise do equivalente da Função zeta de Riemann sobre os corpos finitos. A "geometria aritmética" generaliza-se sobre estruturas finitas. Esta abordagem foi particularmente ativa durante a segunda metade do século XX. André Weil generalizou o procedimento para as curvas algébricas e Pierre Deligne para as variedades algébricas. As Conjecturas de Weil sobre variedades sobre corpos finitos, enunciadas em 1940, foram provadas em 1974, abrindo caminho para o Teorema de Taniyama-Shimura, demonstrado por Andrew Wiles e tendo como consequência o Último Teorema de Fermat.
Aplicações práticas
Após a Segunda Guerra Mundial, Claude Shannon formalizou a Teoria da informação como um ramo da matemática, estabelecendo as problemáticas da segurança e da fiabilidade das transmissões. A criptologia apoia-se na possibilidade de gerar rapidamente grandes números primos. A confidencialidade de uma mensagem é assegurada pela dificuldade técnica de fatorar inteiros em tempo razoável. Michael Rabin publicou um teste de primalidade baseando-se nas propriedades do grupo multiplicativo dos corpos primos. A fiabilidade trata da capacidade de transmitir sem erro uma mensagem apesar das alterações na comunicação; ela é tratada pela teoria dos códigos corretores de erros. Em 1950, Richard Hamming utilizou espaços vetoriais de dimensão finita sobre corpos finitos para formalizar um quadro operacional para a teoria, dando origem à teoria dos códigos lineares.
