Corpo finito
En matemáticas, un corpo finito ou corpo de Galois (chamado así en honra a Évariste Galois) é un corpo que contén un número finito de elementos. Como en calquera corpo, un corpo finito é un conxunto sobre o que se definen as operacións de multiplicación, suma, resta e división e cumpren determinadas regras básicas. Os exemplos máis comúns de corpos finitos son os enteiros mod p cando p é un número primo.
A orde dun corpo finito é o seu número de elementos, que é un número primo ou unha potencia prima. Para cada número primo p e cada número enteiro positivo k hai corpos de orde pk, todos eles isomorfos.
Os corpos finitos son fundamentais en varias áreas das matemáticas e da informática, incluíndo a teoría dos números, a xeometría alxébrica, a teoría de Galois, a xeometría finita, a criptografía e a teoría da codificación.
Propiedades
[editar | editar a fonte]Un corpo finito é un conxunto finito que é un corpo; isto significa que a multiplicación, a suma, a resta e a división (excluíndo a división por cero) están definidas e cumpren as regras da aritmética coñecidas como axiomas de corpo.
O número de elementos dun corpo finito chámase a súa orde ou, ás veces, o seu tamaño. Un corpo finito de orde q existe se e só se q é unha potencia de primo pk (onde p é un número primo e k é un enteiro positivo). Nun corpo de orde pk, engadindo p copias de calquera elemento sempre resulta cero; é dicir, a característica do corpo é p.
Para q = pk, todos os corpos de orde q son isomorfos . A maiores, un corpo non pode conter dous subcorpos finitos diferentes coa mesma orde. Pódense, polo tanto, identificar todos os corpos finitos coa mesma orde, e denotalos sen ambigüidades , Fq ou GF(q), onde as letras GF significan "corpo de Galois".
Nun corpo finito de orde q, o polinomio Xq − X ten todos os q elementos do corpo finito como raíces. Os elementos distintos de cero dun corpo finito forman un grupo multiplicativo. Este grupo é cíclico, polo que todos os elementos distintos de cero poden expresarse como potencias dun único elemento chamado elemento primitivo do corpo. (En xeral, haberá varios elementos primitivos para un corpo dado).
Os exemplos máis simples de corpos finitos son os corpo de orde prima: para cada número primo p, o corpo primo de orde p pode construírse como os enteiros módulo p, .
Os elementos do corpo primo de orde p poden ser representados por números enteiros no rango 0, ..., p − 1. A suma, a diferenza e o produto son o resto da división por p do resultado da operación enteira correspondente. A inversa multiplicativa dun elemento pódese calcular usando o algoritmo de Euclides estendido.
é certa nun corpo de característica p. Isto despréndese do teorema binomial, xa que cada coeficiente binomial da expansión de (x + y)p, excepto o primeiro e o último, é un múltiplo de p.
Polo pequeno teorema de Fermat, se p é un número primo e x está no corpo GF(p) entón xp = x. Isto implica a igualdade
para polinomios sobre GF(p). De forma máis xeral, cada elemento en GF(pn) satisfai a ecuación polinómica xpn − x = 0.
Calquera extensión finita de corpo dun corpo finito é separábel e simple. É dicir, se E é un corpo finito e F é un subcorpo de E, entón E obtense a partir de F unindo un único elemento cuxo polinomio mínimo é separábel.
Unha estrutura alxébrica máis xeral que satisfai todos os outros axiomas dun corpo, mais cuxa multiplicación non é conmutativa, chámase anel de división (ou ás veces corpo nesgado). Segundo o teorema de Wedderburn, calquera anel de división finito é conmutativo e, polo tanto, é un corpo finito.
Existencia e unicidade
[editar | editar a fonte]Sexa q = pn unha potencia de primo e F o corpo de descomposición do polinomio
sobre o corpo primo GF(p). Isto significa que F é un corpo finito de orde máis baixa, no que P ten q raíces distintas (a derivada formal de P é P'=-1, o que implica que gcd(P, P ') = 1, o que en xeral implica que o corpo de división é unha extensión separábel da orixinal).
A identidade anterior mostra que a suma e o produto de dúas raíces de P son raíces de P, así como a inversa multiplicativa dunha raíz de P. Noutras palabras, as raíces de P forman un corpo de orde q, que é igual a F pola minimalidade do corpo de división.
A unicidade ata o isomorfismo dos corpos de división implica que todos os corpos de orde q son isomorfos. Alén diso, se un corpo F ten un corpo de orde q = pk como subcorpo, os seus elementos son as raíces q de Xq − X, e F non pode conter outro subcorpo de orde q .
En resumo, temos o seguinte teorema de clasificación probado por primeira vez en 1893 por EH Moore:[1]
A orde dun corpo finito é unha potencia de primo. Por cada potencia de primo q hai corpos de orde q, e todos son isomorfos. Nestes corpos, todo elemento satisfai
- e o polinomio Xq − X factoriza como
Dedúcese que GF(pn) contén un subcorpo isomorfo a GF(pm) se e só se m é un divisor de n; nese caso, este subcorpo é único. De feito, o polinomio Xpm − X divide Xpn − X se e só se m é un divisor de n.
Construción explícita
[editar | editar a fonte]Corpos non primos
[editar | editar a fonte]Dada unha potencia de primo q = pn con p primo e n > 1, o corpo GF(q) pode construírse explicitamente do seguinte xeito.
Elixe primeiro un polinomio irredutíbel P en GF(p)[X] de grao n (tal polinomio irredutíbel sempre existe). Logo o anel cociente
do anel polinómico GF(p)[X] polo ideal xerado por P é un corpo de orde q.
Excepto na construción de , hai varias opcións posíbeis para , que producen resultados isomorfos. Para simplificar a división euclidiana, adóitase escoller para un polinomio da forma
que fai que as divisións euclidianas necesarias sexan moi eficientes. No entanto, para algúns corpos, normalmente na característica , poden non existir polinomios irredutíbeis da forma .[2]
Unha posíbel escolla para tal polinomio vén dada polos polinomios de Conway. Aseguran unha certa compatibilidade entre a representación dun corpo e as representacións dos seus subcorpos.
Corpo con 4 elementos
[editar | editar a fonte]O corpo non primo máis pequeno é o corpo con catro elementos, que se denota comunmente como ou Está formado polos catro elementos tal que , , , e , para todo a outra operación resulta ser facilmente deducida da lei distributiva. Vexa a continuación as táboas de operacións completas.
Isto pódese deducir do seguinte xeito dos resultados do apartado anterior.
Sobre , só hai un polinomio irredutíbel de grao :
Polo tanto, para a construción da sección anterior debe implicar este polinomio, e
Denotamos unha raíz deste polinomio en . Isto implica que
e que e son os elementos de que non están en . As táboas das operacións en resultan disto e son as seguintes:
|
|
|
(Como para todo en todo anel a división por 0 ten que permanecer sen definir).
Nas táboas, pódese ver que a estrutura aditiva de é isomorfa ao Grupo de Klein, mentres que a estrutura multiplicativa distinta de cero é isomorfa ao grupo .
O mapa
é o automorfismo de corpos non trivial, chamado Automorfismo de Frobenius, que envía á segunda raíz do citado polinomio irredutíbel .
GF(p2) para un primo impar p
[editar | editar a fonte]Para aplicar o visto na construción xeral dos corpos finitos no caso de , hai que atopar un polinomio irredutíbel de grao 2. Para , isto fíxose na sección anterior. Se é un primo impar, sempre hai polinomios irredutíbeis da forma , con en .
Máis precisamente, o polinomio é irredutíbel sobre se e só se é un non residuo cadrático módulo (esta é case a definición dun non residuo cadrático).
Hai non residuos cadráticos módulo . Por exemplo, é un non residuo cadrático para , e é un non residuo cadrático para . Se , isto é , pódese escoller como un non residuo cadrático, o que nos permite ter un polinomio irredutíbel moito simple .
Tendo escollido un non residuo cadrático , sexa unha raíz cadrada simbólica de , isto é, un símbolo que ten a propiedade . Daquela, os elementos de son todas as expresións lineares
con e en .
As operacións en defínense do seguinte xeito (as operacións entre elementos de representadas con letras latinas son as operacións en ):
Estrutura multiplicativa
[editar | editar a fonte]O conxunto de elementos distintos de cero en GF(q) é un grupo abeliano baixo a multiplicación, de orde q – 1 . Segundo o teorema de Lagrange, existe un divisor k de q – 1 tal que xk = 1 para todo x distinto de cero en GF(q). Como a ecuación xk = 1 ten como máximo k solucións en calquera caorpo, q – 1 é o valor máis baixo posíbel para k. O teorema de estrutura dos grupos abelianos finitos implica que este grupo multiplicativo é cíclico, é dicir, todos os elementos distintos de cero son potencias dun só elemento. En resumo: Tal elemento a chámase elemento primitivo de GF(q). A menos que q = 2, 3, o elemento primitivo non é único. O número de elementos primitivos é φ(q − 1) onde φ é a función totiente de Euler.
O resultado anterior implica que xq = x para todo x en GF(q). O caso particular onde q é primo é o pequeno teorema de Fermat .
Logaritmo discreto
[editar | editar a fonte]Se é un elemento primitivo en , entón, para calquera elemento distinto de cero en , hai un único enteiro con tal que . Este número enteiro chámase logaritmo discreto de para a base .
Aínda que pódese calcular moi rapidamente, por exemplo usando a exponenciación ao cadrado, non se coñece un algoritmo eficiente para calcular a operación inversa, o logaritmo discreto.
Cando os elementos distintos de cero de están representados polos seus logaritmos discretos, a multiplicación e división son fáciles, xa que se reducen a suma e resta módulo . Porén, a suma equivale a calcular o logaritmo discreto de .
A identidade
permite resolver este problema construíndo a táboa dos logaritmos discretos de , chamada logaritmo de Zech, para (convén definir o logaritmo discreto de cero como .
Os logaritmos de Zech son útiles para grandes cálculos, como a álxebra linear sobre corpos de tamaño medio, é dicir, corpos suficientemente grandes para que os algoritmos naturais sexan ineficientes, mais non demasiado grandes, xa que hai que calcular previamente unha táboa do mesmo tamaño que a orde do corpo.
Raíces da unidade
[editar | editar a fonte]
Todo elemento distinto de cero dun corpo finito é unha raíz da unidade, pois para todo elemento distinto de cero de .
Se é un número enteiro positivo, unha raíz primitiva da unidade -ésima é unha solución da ecuación que non é unha solución da ecuación para calquera número enteiro positivo . Se é unha raíz primitiva da unidade -ésima nun corpo , entón contén todas as raíces da unidade, que son .
O corpo contén unha raíz primitiva da unidade -ésima se e só se é un divisor de ; se é un divisor de , entón o número de raíces primitivas -ésimas da unidade en é (función totiente de Euler). O número de raíces -ésimas da unidade en é .
Nun corpo da característica , cada -ésima raíz da unidade é tamén unha -ésima raíz da unidade. Dedúcese que as raíces primitivas de -ésimas da unidade nunca existen nun corpo de característica .
Por outra banda, se é coprimo con , as raíces do -ésimo polinomio ciclotómico son distintas en todos os corpos da característica , xa que este polinomio é un divisor de cuxo discriminante é distinto de cero módulo .
Dedúcese que o -ésimo polinomio ciclotómico factoriza sobre en distintos polinomios irredutíbeis que teñen todos o mesmo grao, digamos , e que é o corpo máis pequeno de característica que contén -ésimos raíces primitivas da unidade.
Ao calcular os caracteres de Brauer, utilízase o mapa para asignar valores propios dunha matriz de representación aos números complexos. Baixo esta asignación, o subcorpo base consta de puntos espazados uniformemente arredor da circunferencia unitaria (omitindo cero).
Exemplo: GF(64)
[editar | editar a fonte]O corpo ten varias propiedades interesantes que os corpos máis pequenos non comparten: ten dous subcorpos de xeito que ningún está contido no outro; non todos os xeradores (elementos con polinomio mínimo de grao sobre ) son elementos primitivos; e os elementos primitivos non están todos conxugados baixo o grupo de Galois.
A orde deste corpo é 26, e os divisores de 6 son 1, 2, 3, 6, os subcorpos de GF(64) son GF(2), GF(22) = GF(4), GF(23) = GF(8), e o propio GF(64). Como 2 e 3 son coprimos, a intersección de GF(4) e GF(8) en GF(64) é o corpo primo GF(2).
A unión de GF(4) e GF(8) ten así 10 elementos. Os 54 elementos restantes de GF(64) xeran GF(64) no sentido de que ningún outro subcorpo contén ningún deles. Dedúcese que son raíces de polinomios irredutíbeis de grao 6 sobre GF(2). Isto implica que, sobre GF(2), hai exactamente 9 = 54/6 polinomios mónicos irredutíbeis de grao 6. Isto pódese verificar factorizando X64 − X sobre GF(2).
Os elementos de GF(64) son raíces primitivas -ésimas da unidade para algúns que dividen . Como a terceira e a sétima raíces da unidade pertencen a GF(4) e GF(8), respectivamente, os xeradores de 54 son raíces primitivas n-éimas da unidade para algúns n' en in {9, 21, 63} . A función totiente de Euler mostra que hai 6 raíces primitivas 9-ésimas da unidade, raíces primitivas -ésimas da unidade e raíces primitivas 63-ésimas da unidade. Sumando estes números (6+12+36), atópase de novo elementos.
Factorizando os polinomios ciclotómicos sobre , atópase que:
- As seis raíces primitivas da unidade -ésimas son raíces de
- e están todas conxugadas baixo a acción do grupo de Galois.
- As doce raíces primitivas da unidade -ésimas son raíces de
- Forman dúas órbitas baixo a acción do grupo de Galois. Como os dous factores son recíprocos entre si, unha raíz e a súa inversa (multiplicativa) non pertencen á mesma órbita.
- Os elementos primitivos de son as raíces de
Descompóñense en seis órbitas de seis elementos cada unha baixo a acción do rupo de Galois.
Isto mostra que a mellor opción para construír é definilo como GF(2)[X] / (X6 + X + 1). De feito, este xerador é un elemento primitivo, e este polinomio é o polinomio irredutíbel que produce a división euclidiana máis sinxela.
Automorfismo de Frobenius e teoría de Galois
[editar | editar a fonte]Nesta sección, p é un número primo e q = pn é unha potencia de p.
En GF(q), a identidade (x + y)p = xp + yp implica que o mapa
é un endomorfismo linear GF(p) e un automorfismo de corpos de GF(q), que fixa todos os elementos do subcorpo GF(p). Chámase automorfismo de Frobenius, en honor de Ferdinand Georg Frobenius.
Denotando como φk a composición de φ consigo mesmo k veces, temos
Demostrouse na sección anterior que φn é a identidade. Para 0 < k < n, o automorfismo φk non é a identidade, xa que, en caso contrario, o polinomio tería máis de pk raíces.
Non hai outros automorfismos GF(p) de GF(q). Noutras palabras, GF(pn) ten exactamente n GF(p) -automorfismos, que son
En termos da teoría de Galois, isto significa que GF(pn) é unha extensión de Galois de GF(p), que ten un grupo de Galois cíclico.
Factorización de polinomios
[editar | editar a fonte]- Artigo principal: Factorización de polinomios.
En matemáticas e álxebra informática, a factorización de polinomios ou factorización polinómica expresa un polinomio con coeficientes nun corpo determinado ou en números enteiros como o produto de factores irredutíbleis con coeficientes no mesmo dominio. A factorización polinómica é un dos compoñentes fundamentais dos sistemas de álxebra informática.
O primeiro algoritmo de factorización polinómica foi publicado por Theodor von Schubert en 1793. Leopold Kronecker redescubriu o algoritmo de Schubert en 1882 e estendeuno a polinomios e coeficientes multivariados nunha extensión alxébrica.
Mais a maior parte do coñecemento sobre este tema non é máis antigo que arredor de 1965 e os primeiros sistemas de álxebra informática.Notas
[editar | editar a fonte]- ↑ Moore, E. H. (1896). "A doubly-infinite system of simple groups". En E. H. Moore. Mathematical Papers Read at the International Mathematics Congress Held in Connection with the World's Columbian Exposition. Macmillan & Co. pp. 208–242.
- ↑ Recommended Elliptic Curves for Government Use (PDF). National Institute of Standards and Technology. xullo 1999. p. 3. Arquivado dende o orixinal (PDF) o 2008-07-19.
Véxase tamén
[editar | editar a fonte]![]() |
Wikimedia Commons ten máis contidos multimedia na categoría: Corpo finito ![]() |
Bibliografía
[editar | editar a fonte]- W. H. Bussey (1905) "Galois field tables for pn ≤ 169", Bulletin of the American Mathematical Society 12(1): 22–38, doi 10.1090/S0002-9904-1905-01284-2
- W. H. Bussey (1910) "Tables of Galois fields of order < 1000", Bulletin of the American Mathematical Society 16(4): 188–206, doi 10.1090/S0002-9904-1910-01888-7
- Jacobson, Nathan (2009) [1985]. Basic algebra I (Second ed.). Dover Publications. ISBN 978-0-486-47189-1.
- Mullen, Gary L.; Mummert, Carl (2007). Finite Fields and Applications I. Student Mathematical Library (AMS). ISBN 978-0-8218-4418-2.
- Mullen, Gary L.; Panario, Daniel (2013). Handbook of Finite Fields. CRC Press. ISBN 978-1-4398-7378-6.
- Lidl, Rudolf; Niederreiter, Harald (1997). Finite Fields (2nd ed.). Cambridge University Press. ISBN 0-521-39231-4.
- Skopin, A. I. (2001) [1994]. "Galois field". Encyclopedia of Mathematics. EMS Press.