Algebra Modular

Prévia do material em texto

Aritmética Modular
Renato Ramos da Silva
Universidade Federal de Lavras
renato.ramos@dcc.ufla.br
7 de outubro de 2015
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 1 / 31
Overview
1 Aritmética Modular
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 2 / 31
Aritmética Modular
Introdução
Aritmética com foco nos fenômenos cíclicos.
Quando é que 13+18 é igual a 7?
Quando estamos falando de horas
Que horas serão daqui 50 horas?
Nesse caso, nosso interesse reside no resto da divisão entre 50 e 24
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 3 / 31
Algoritmo de divisão
Como podemos escrever um algoritmo para dividir dois números?
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 4 / 31
Algoritmo de divisão
Como podemos escrever um algoritmo para dividir dois números?
Quando temos interesse no q (quociente) e r (resto).
a = bq + r e a 0 ≤ r < b
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 5 / 31
Algoritmo de divisão
Algorithm 1: Divisão
Entrada: inteiros positivos a e b
Saída: inteiros positivos q e r
início
Comece fazendo Q=0 e R=a;
repita
R=R-b;
Q=Q+1;
até R ≥ b ;
Escreva Q e R;
fim
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 6 / 31
Algoritmo de divisão
Algorithm 2: Divisão 2
Entrada: inteiros positivos a e b
Saída: inteiros positivos q e r
início
Q = (inteiro)a/b;
R = a-bQ;
Escreva Q e R;
fim
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 7 / 31
Teorema de divisão
Seja a e b inteiros positivos. Existem números inteiros q e r tais que
a = bq + r e 0 ≤ r < b.
Além disso, os valores de q e r satisfazendo as relações acima são únicos.
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 8 / 31
Aritmética Modular
Definição
Para um número inteiro m e um inteiro positivo n, m mod n é o menor
número número não negativo r tal que
m=nq+r
para um q inteiro.
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 9 / 31
Aritmética Modular
Exemplo
10 mod 7 e -10 mod 7
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 10 / 31
Aritmética Modular
Exemplo
10 mod 7 e -10 mod 7
Resposta
10 mod 7 q=1 e r=3
e -10 mod 7 q=-2 e r=4
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 11 / 31
Aritmética Modular
Caso especial - Indicar quando dois números inteiros possuem o
mesmo resto
Se a e b forem números inteiros e m for um número inteiro positivo, então
a é congruente a b módulo m se m divide a-b. Usaremos a notação
a ≡ b(mod m) para indicar que a é congruente a b módulo m.
Assim,
a ≡ b(mod m), se e somente se a mod m = b mod m.
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 12 / 31
Aritmética Modular
Exemplo
Determine se 17 é congruente a 5 módulo 6 e se 24 e 14 são congruentes
ao módulo 6.
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 13 / 31
Aritmética Modular
Exemplo
Determine se 17 é congruente a 5 módulo 6 e se 24 e 14 são congruentes
ao módulo 6.
Solução
6 divide 17-5 = 12 (17 ≡ 5(mod 6)) 6 não divide 24-14 = 10 (17 6≡5(mod
6))
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 14 / 31
Aritmética Modular
Relação de equivalência
Reflexiva
Simétrica
Transitiva
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 15 / 31
Aritmética Modular
Teorema do conjunto dos inteiros modulo n (Zn)
Considere m como um número inteiro positivo. Os números a e b são
congruentes ao módulo m se e somente se houver um inteiro k, tal que
a = b + km
Classe de congruência de a módulo m
É definida como o conjunto de todos os inteiros congruentes com a módulo
m.
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 16 / 31
Exemplo
m=3
0 = {. . . ,−9,−6,−3, 0, 3, 6, 9 . . .} 1 = {. . . ,−8,−5,−2, 1, 4, 7, 10 . . .}
2 = {. . . ,−7,−4,−1, 2, 5, 8, 11 . . .}
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 17 / 31
Exercício
Quantas classes de congruência é possível construir quando m for
igual a:
a) 12?
b) 35?
c) n?
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 18 / 31
Exercício
Calcule
a) 21 mod 9
b) 38 mod 9
c) (21+38) mod 9
d) (21× 38) mod 9
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 19 / 31
Notação
i +n j = (i + j)modn
i ×n j = (i × j)modn
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 20 / 31
Aritmética Modular
Teorema
Considere m como um número inteiro positivo. Se a ≡ b(mod m) e
c ≡ d(mod m) então:
a + c ≡ b +m d e a × c ≡ b ×m d
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 21 / 31
Exemplo
7 ≡ 2(mod 5) e 11 ≡ 1(mod 5)
?
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 22 / 31
Exemplo
7 ≡ 2(mod 5) e 11 ≡ 1(mod 5)
18 = 7+ 11 ≡ 2+ 1 = 3(mod5) 77 = 7× 11 ≡ 2× 1 = 2(mod5)
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 23 / 31
Exemplo - Endereçamento de memória
O computador da faculdade mantém registros de todos os alunos
Como endereçar os registros a fim de recuperar as informações dos
estudantes?
Para acessar os registros uma chave é necessaria.
Uma função h(k) mapeia uma posição de memória para um registro
que possui chave k
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 24 / 31
Exemplo - Endereçamento de memória
Uma função comum para realizar essa tarefa pode ser - h(k)=k mod
m
Sabendo que m é o número de posições de memória disponíveis
Supondo que m =111
h(064212848) = 064212848 mod 111 = 14
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 25 / 31
Exemplo - Geração de número aleatório
É possível gerar uma sequência de números pseudos-aleatórios {xn} com
0 ≤ xn < m para todo n com
xn+1 = (axn + c)modn
2 ≤ a < m, 0 ≤ c < m e 0 ≤ x0 < m
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 26 / 31
Exercício
m=9, a=7, c=4 e x0=3
a) x1
b) x2
c) x3
d) x4
e) x5
f) x6
g) x7
h) x8
i) x9
j) x10
k) x11
l) x12
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 27 / 31
Exemplo - Criptografia
Expressar a encriptação de Julio Cesar como processo matemático
Cada letra será representada por um número (A=0 ... Z = 25)
f(p) = p +26 3
p ≤ 25
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 28 / 31
Exemplo - Criptografia
Passos
Qual é a mensagem secreta produzida pela mensagem: MEET YOU
IN THE PARK
Primeiro passo (trocar as letras por números):
12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10
Segundo passo (trocar cada número p por f(p)):
15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13
Terceiro passo (trocar número por letra): PHHW BRX LQ WKH
SDUN
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 29 / 31
Exemplo - Criptografia
Para recuperar f −1(p) = (p − 3)mod 26
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 30 / 31
The End
Renato Ramos da Silva (UFLA) Short title 7 de outubro de 2015 31 / 31
	Aritmética Modular