1
MÉTODOS DISCRETOS
EM TELEMÁTICA
MATEMÁTICA DISCRETA
Profa. Marcia Mahon
Grupo de Pesquisas em Comunicações - CODEC
Departamento de Eletrônica e Sistemas - UFPE
Outubro 2003
2
CONTEÚDO
1 - Introdução
2 - Grupos
3 - Anéis
4 - Corpos (Campos de Galois)
BIBLIOGRAFIA
1 - J. R. Durbin, Modern Algebra - An Introduction,
John Wiley, 1992.
2 - R. J. McEliece, Finite Fields for Computers
Scientists and Engineers, Kluwer, 1987.
3 - S. B. Wicker, Error Control Systems for Digital
Communication and Storage, Prentice Hall, 1995.
3
1 - INTRODUÇÃO
Estruturas matemáticas discretas desempenham um papel
importante em muitas aplicações em Engenharia. Dentre elas
destacam-se: Grupos, Anéis e Corpos.
Algumas Definições:
ORDEM - A Ordem de um conjunto S é o número de elementos
de S e é denotada por |S|.
CONJUNTO FINITO - Um conjunto S é dito ser finito se ele
tem um número finito de elementos.
4
FECHAMENTO - Um conjunto S é dito ser fechado em relação
a uma operação •
se e somente se,
∀ a, b ∈ S ,então a • b ∈ S .
ASSOCIATIVIDADE - Uma operação • é dita ser associativa se e
somente se, a•b•c = a•(b•c) = (a•b)•c.
NOTAÇÃO - Para qualquer conjunto S, S* é o conjunto
S* = S – {0}.
O MATERIAL APRESENTADO A SEGUIR TRATA DE
CONJUNTOS FINITOS
QUE SÃO FECHADOS
RELAÇÃO A OPERAÇÕES ASSOCIATIVAS.
EM
5
2 - GRUPOS
Um Grupo é uma estrutura algébrica formada por um
conjunto G e uma operação que tem inversa.
Se a operação é "+" (adição), então a operação inversa é "-"
(subtração) e o grupo é chamado aditivo.
Se a operação é "." (multiplicação), então a operação inversa é
"÷" (divisão) e o grupo é chamado multiplicativo.
Exemplos:
• Grupos Infinitos
i) < Z, + >, onde Z denota o conjunto dos Inteiros.
ii) < R, +>, onde R denota o conjunto dos Reais.
iii) < R*, . >
6
• Grupos Finitos
i) < Zn, +n >
Para n = 4, < Z4, +4 > é um grupo de ordem 4, onde Z4 = {0, 1,
2, 3}. O grupo tem um elemento identidade: e = 0. A tabela de
composição do grupo é:
+4
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
3
3
0
1
2
ii) < Zp*, •p >, p primo.
Para p = 5, < Z5*, •5 > é um grupo de ordem 4, onde Z5*= {1, 2,
3, 4}. O grupo tem um elemento identidade: e = 1. A tabela de
composição do grupo é:
7
•5
1
2
3
4
1
1
2
3
4
2
2
4
1
3
3
3
1
4
2
4
4
3
2
1
2.1. Grupos Abelianos
Um grupo <G, •> é chamado Abeliano ou Comutativo, se a•b =
b•a, para qualquer a, b em G.
Exemplos: < Zn, +n > e < Zp*, •p > são grupos abelianos.
2.2. Grupos Cíclicos
Definição: A Ordem de um elemento g∈<G, •> é o menor inteiro
r, tal que
g • g • g • ..... • g = e
1442443
r vezes
onde e denota o elemento identidade do grupo.
8
Exemplo: Ordens dos elementos do grupo < Z7*, •7 >.
O elemento g = 2 tem ordem r = 3, pois
21 ≡ 2(mod 7); 2 2 ≡ 4 (mod 7); 23 = 8 ≡ 1 (mod 7) .
Elementos de < Z7*, •7 > e suas ordens:
g
Ordem
1
1
2
3
3
6
4
3
5
6
6
2
Definição: Um grupo <G, •> é chamado Cíclico
se todo
elemento a ∈ G pode ser expresso como uma "potência" de um
dado elemento de G, chamado elemento gerador do grupo.
Observe então que, em um grupo com |G| = n, o elemento
gerador tem ordem n.
Exemplos: < Zn, +n > e < Zp*, •p > são grupos cíclicos.
9
2.3. Subgrupos
Um Subgrupo de um grupo <G, •> é um subconjunto dos
elementos do conjunto G, que forma um grupo em relação à
operação de G.
Exemplos:
i) G = < Z6, +6 >; seja um subgrupo H = < {0, 2, 4} , +6 >.
ii) G = < Z7*, •7 >
2.4. Classes Laterais
Se H é um subgrupo de G, então as Classes Laterais à esquerda
de G em relação à H, são os conjuntos da forma g•H = {g•h, |
h∈H}, onde g∈G.
10
Exemplos:
i) G = < Z12, +12 >, H = < {0, 4, 8}, +12 >.
As classes laterais à esquerda de G em relação a H:
0 +12 {0, 4, 8} = {0, 4, 8}
1 +12 {0, 4, 8} = {1, 5, 9}
2 +12 {0, 4, 8} = {2, 6, 10}
3 +12 {0, 4, 8} = {3, 7, 11}
ii) G = < Z7*, •7 >, H = < {1, 2, 4}, •7 >.
As classes laterais à esquerda de G em relação a H:
1 •7 {1, 2, 4} = {1, 2, 4}
3 •7 {1, 2, 4} = {3, 6, 5}
O Teorema de Lagrange:
Se H é um subgrupo de G, então |H| divide |G|.
11
3 - ANÉIS
Um Anel é uma estrutura algébrica formada por um
conjunto R e duas operações, onde apenas uma delas tem
inversa.
Se "+" e "." são as operações, a operação inversa é "-" mas
"÷" não é uma operação válida.
Exemplo:
< Zn, +n , •n >
Para n = 4, < Z4, +4 , •4 > é um anel de ordem 4, onde R = {0, 1,
2, 3}. As tabelas de adição e de multiplicação do anel são:
+4
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
3
3
0
1
2
•4
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
12
4 - CORPOS
Um Corpo é uma estrutura algébrica formada por um
conjunto F e duas operações, ambas possuindo inversa.
Se "+" e "." são as operações do corpo, então "-" e "÷" são
as operações inversas, respectivamente.
Um corpo de ordem q, isto é, um corpo com q elementos, é
denotado por GF(q) ou Fq.
Exemplo:
GF(p) = < { 0, 1, 2,..., p-1}, +p , •p >, onde q = p.
Para p = 3, GF(3) = <F, +3 , •3 > é um corpo de ordem 3, onde F
= {0, 1, 2}.
13
As tabelas de adição e de multiplicação do corpo são:
+3
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
•3
0
1
2
0
0
0
0
1
0
1
2
Algumas questões sobre GF(p) = < F, +p , •p > :
i) O que se pode dizer sobre a estrutura < F, +p> ?
Resposta: < F, +p> é um grupo aditivo.
ii) E sobre a estrutura < F, •p > ?
Resposta: CUIDADO!
2
0
2
1
14
< F*, •p > é um grupo multiplicativo.
Definição: A Característica de um corpo é o menor p, tal que
11
+4
1 +4
14
+2
..........
+
44..4
31 ≡ 0 (mod p )
p vezes
Exemplo:
GF(2) é um corpo de característica p = 2. Os elementos do corpo
são 0, 1, 1 + 1 = 2 ≡ 0 (mod 2), e assim p = 2.
4. 1. Construção de um Corpo Finito
Só existem corpos finitos GF(q) de ordem
igual a uma
potência de um primo, isto é, q = pm, onde m ≥ 1 é um inteiro e p
é um primo. Para uma dada ordem existe apenas um corpo finito.
15
4. 1. 1. Construção de GF(p)
Para construir o corpo GF(p) considere o conjunto
{0,1,2,...,p-1}, e as operações de adição e multiplicação módulo p.
Assim,
GF(p) = < {0,1,2,...,p-1}, +p , •p >.
Exemplo:
GF(p) = < { 0,1,2,...,p-1}, +p , •p >
Para p = 5, GF(5) = < {0, 1, 2, 3, 4}, +5 , •5 > é um corpo de
ordem 5.
Observe o grupo multiplicativo de GF(5), que é
< {1, 2, 3, 4}, •5 >
16
Considere as potências do elemento 2:
21 ≡ 2 (mod 5); 2 2 ≡ 4 (mod 5); 23 = 8 ≡ 3 (mod 5); 2 4 = 16 ≡ 1 (mod 5).
Note que as potências de 2 geram todos os elementos do grupo
(que são os elementos não nulos de GF(5)).
Assim, esse grupo é cíclico pois todo elemento do grupo é uma
potência de um único elemento. Esse elemento é um gerador do
grupo. No nosso exemplo, 2 é um gerador do grupo
multiplicativo de GF(5).
Considere agora as potências do elemento 3:
31 ≡ 3 (mod 5); 32 = 9 ≡ 4 (mod 5); 33 = 27 ≡ 2 (mod 5); 34 = 81 ≡ 1 (mod 5),
e 3 é outro gerador do mesmo grupo.
17
Elementos de < F5*, •5 >, grupo multiplicativo de GF(5), e suas
ordens:
g
Ordem
1
1
2
4
3
4
4
2
Definição: Se α é um gerador do grupo multiplicativo de GF(p),
então α é um Elemento Primitivo do Corpo GF(p).
Portanto, a ordem de um elemento primitivo em um corpo de
ordem p é ..............
Resposta: p-1.
No exemplo anterior, 2 e 3 são elementos primitivos de GF(5) e
ambos tem ordem 4 (que é a ordem do grupo multiplicativo de
GF(5)).
18
4. 1. 2. Construção de GF(pm), m > 1
Na construção de GF(pm) os elementos são polinômios e as
operações são adição e multiplicação módulo um certo polinômio.
É, portanto, necessário definir este polinômio.
Definição: Considere um polinômio, denotado por p(x), de grau m
com coeficientes em GF(p), isto é, um polinômio sobre GF(p), que
é irredutível em GF(p).
Assim, na construção de GF(pm), os elementos são todos os
polinômios sobre GF(p) que tem grau menor que m e as operações
do corpo são adição e multiplicação módulo p(x).
19
Exemplo: Construção de GF(22) (p = 2, m = 2), dado p(x) =
x2+x+1 (um polinômio de grau m = 2, irredutível sobre GF(2)).
Os elementos do corpo são todos os polinômios sobre GF(2) de
grau menor que 2, isto é,
0, 1, x, x + 1.
As tabelas de adição e multiplicação para GF(4) são:
+p(x) 0
1
X X+1
0
0
1
X X+1
1
1
0 X+1 X
X
X X+1 0 X+1
X+1 X+1 X
1
0
•p(x)
0
1
X
X+1
0
0
0
0
0
1
X X+1
0
0
0
1
X X+1
X X+1 1
X+1 1
X
20
Os mesmos resultados obtidos sobre o grupo multiplicativo de
GF(p) podem ser estendidos para o grupo multiplicativo de
GF(pm), isto é,
< GF* (pm), •p(x) >
é um GRUPO CÍCLICO.
A ordem do grupo acima é .................
.................pm – 1.
Que outras representações podem ser usadas para os elementos do
corpo?
Pense nas potências de um elemento gerador do grupo
multiplicativo (ou elemento primitivo do corpo).
21
Exemplo: Encontrar um elemento primitivo de GF(4):
Ou .... encontrar um gerador do grupo multiplicativo de GF(4)
Ou .... encontrar um elemento de ordem 3 de GF(4)
O elemento (x + 1) é um elemento primitivo de GF(4) pois,
(x + 1)1 ≡ x + 1 (mod x2 + x + 1);
(x + 1)2 = x2 + 1 ≡ x (mod x2 + x + 1);
(x + 1)3 = x3+ x2 + x + 1 ≡ 1 (mod x2 + x + 1),
que são os elementos não nulos de GF(4).
Exemplo: Construir GF(8) (ou GF(23)), p = 2 e m = 3, dado p(x) =
x3 + x + 1.
22
Possíveis representações dos elementos de GF(8): polinomial,
triplas binárias e potências de um elemento primitivo de GF(8).
Como encontrar um elemento primitivo de GF(8) (a partir de
agora, denotado α)?
A idéia é usar a propriedade de que um elemento primitivo do
corpo também é raiz de um polinômio primitivo.
Assim, se p(x) é um polinômio primitivo de grau m sobre GF(p),
os elementos de GF(pm) podem ser representados como potências
de uma raiz α de p(x).
Então, como encontrar um polinômio primitivo de grau 3, sobre
GF(2) (para representar os elementos de GF(23)?
23
Definição: Um polinômio p(x), de grau m e irredutível sobre
GF(p), tem ordem e (ou pertence ao expoente e) se p(x)(xe – 1)
mas p(x) não divide (xn – 1) para n < e. O polinômio p(x) é
primitivo se e = pm –1.
Exemplo: Determinar a ordem de p(x) = x3 + x + 1.
.........................................................................................................
Assim, e = 23 – 1 = 7 (p = 2, m = 3) e p(x) é um polinômio
primitivo de grau 3 sobre GF(2).
Se α é uma raiz de p(x) = x3 + x + 1, isto é:
p(α) = α3 + α + 1 = 0,
então α é um elemento primitivo de GF(23), cujos elementos
podem ser representados por potências de α (mostrado abaixo):
24
α1 ≡ α (mod α3 + α + 1)
α5 ≡ α2 + α + 1 (mod α3 + α + 1)
α2 ≡ α2 (mod α3 + α + 1)
α6 ≡ α2 + 1 (mod α3 + α + 1),
α3 ≡ α + 1 (mod α3 + α + 1),
α7 ≡ 1 (mod α3 + α + 1).
α4 ≡ α2 + α (mod α3 + α + 1),
Assim, existem três maneiras de representar os elementos de
GF(8):
POLINOMIAL
0
1
X
X2
X +1
X2 + X
X2 + X +1
X2 + 1
TRIPLA BINÁRIA
000
100
010
001
110
011
111
101
POTÊNCIA DE α
α-∞
α0
α
α2
α3
α4
α5
α6
Exemplo: Construir GF(16) (ou GF(24)), dado p(x) = x4 + x + 1.
25
ALGUMAS DEFINIÇÕES
1) Um Grupo <G, •> é uma estrutura algébrica, onde G é um conjunto e • é uma operação
definida sobre os elementos de G, que satisfaz os seguintes axiomas:
i - Fechamento: g•h ∈ G, ∀g, h ∈ G.
ii - Associatividade: g•(h•k) = (g•h)•k = g•h•k, ∀g, h, k ∈ G.
iii - Identidade: Existe um elemento e ∈ G tal que e•g = g•e = g, ∀g ∈ G.
iv - Inversos: Para todo g ∈ G existe o elemento g-1 ∈ G, chamado o inverso de g, tal que
g•g-1 = g-1•g = e.
2) Um Semigrupo <S, •> é uma estrutura algébrica onde S é um conjunto e • é uma
operação definida sobre os elementos de S, que satisfaz os axiomas de fechamento e
associatividade definidos acima.
3) Um Anel <R, +, •> é uma estrutura algébrica onde R é um conjunto, • e + são operações
definidas sobre os elementos de R, satisfazendo:
i - <R, +> é um grupo abeliano.
ii - <R, •> é um semigrupo.
iii - A operação • é distributiva em relação a +, isto é: a•(b+c) = (a•b)+(a•c) e (b+c)•a =
(b•a)+(c•a), ∀ a, b, c ∈ R.
26
4) Um Corpo <F, +, •> é uma estrutura algébrica, onde F é um conjunto, • e + são
operações definidas sobre os elementos de F, satisfazendo os seguintes axiomas.
i - <F, +, •> é um anel comutativo com identidade.
ii - <F*, •> é um grupo abeliano.
5) Se a ordem de F é finita (|F| = q, digamos), então a estrutura <F, +, •> é dita ser um
Corpo Finito ou Campo de Galois, sendo denotada por GF(q). A ordem de um Campo de
Galois é sempre uma potência de um primo, isto é, q = pm, onde p é primo e m é um inteiro
≥ 1.