Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

1
Prof. Gian Carlo Brustolin
Matemática Computacional
Aula 5
Conversa Inicial
Aritmética modular
Algoritmo de Euclides
Logaritmos discretos
Teoremas de Euler e Fermat
Testes de Fermat e Miller-Rabin
Aritmética Modular
x ≡ y(mod n)
x, y e n Є ℤ
ℤ = {..., - 3, - 2, - 1, 0, 1, 2, 3,...}
x e y são congruentes módulo n se
x = y + Kn
Exemplo y=-5, n=7
x ≡ -5(mod 7) então
x = 2 pois -5 + (7*1) =2 
e poderemos escrever 2≡-5(mod 7)
x = 9 pois -5 + (7*2) =9 
e poderemos escrever 9≡-5(mod 7)
-3 ≡ 11(mod 14)?
Aguarde a aula prática
Valor de K
pode ser
qualquer ℤ
2
Adições e subtrações são possíveis 
dos dois lados da congruência
2≡-5(mod 7) 
Somando 2
4≡-3(mod 7) 
Subtraindo 1
3≡-4(mod 7)
Multiplicações são possíveis 
dos dois lados da congruência
2≡-5(mod 7) 
Multiplicando por 2
4≡-10(mod 14) 
Mas divisões
Não há nenhuma noção de grandeza 
ou proporção entre as congruências 
Por exemplo, 0 < 4 (mod 8) não faz 
sentido
E para que serve?
Além das aplicações teóricas... Criptografia
Quebra de criptografia
Análise da frequência de caracteres
12 letras mais frequentes:
80% do uso total 
8 letras: 65% do uso total
Quebra de criptografia
Em cifras de substituição ou transposição
Em cifras modernas (XOR, Rotação)
Matemática modular impede
a análise de frequência
Cifra de transposição ou P-Box
BLOCO 1
1
O
2
M
3
N
4
I
5
A
6 7
T
8
M
9
E
A
5
N
3
T
7
I
4
E
8
M
9
N
2
O
1 6
BLOCO 2
1
P
2
U
3
S
4 5
H
6
A
7
B
8
E
9
N
H
5
S
3
B
7 4
E
8
N
9
U
2
P
1
A
6
BLOCO 3
1
T
2
-
3
E
4
C
5 6
3
7
,
8
1
9
5
E
3
,
7
C
4
1
8 9
-
2
T
1
3
6
Se codificarmos a palavra ASA, normalmente 
os símbolos criptográficos para A e A serão 
os mesmos ou correlacionados
Tome o ASCii para A = 65, podemos fazer
x ≡ 65 mod 3 então x pode ser 5 no primeiro 
A e 98 no próximo ou podemos pensar em 
fazer 
x ≡ 5 mod 63…
3
Algoritmo de Euclides Se c = mdc(a,b) então existe solução inteira 
para 
c = ax + by
Teorema de Euclides estendido
Se c = mdc(a,b) então existe solução inteira 
para
c = ax + by para c = mdc(a,b)
c= 21x+35y o MDC(21,35)=7 então 
21x+35y =7 admitirá solução (x,y) inteira, 
por exemplo (2,1) e se quisermos resolver:
c= 241x+395y
Precisamos de uma forma simples de 
calcular MDCs – Máximo Divisor Comum 
- para números grandes
O algoritmo de Euclides é uma forma 
simples para encontrar o MDC para dois 
inteiros diferentes de zero, sem exigir a 
fatoração – Euclides 300 a.C
Teorema: mdc(x,y) = mdc(y, x-y)
Se x > y então x-y = resto de x/y
Mdc(x,y) = mdc (y, resto(x/y))
x y
resto 1 1*y=x-resto
resto=x-y
4
mdc(x,y)= mdc (y, resto)
Um MDC pode ser calculado
de forma recursiva
O resto da divisão na primeira 
entrada é usado no passo 
seguinte, até que o resto seja zero
mdc (27,33)=mdc(33,27)
Dividimos x/y: 33 = 1 x 27 + 6
mdc (33,27) = mdc (27, 6)
Repetimos o processo: 27 = 4 x 6 + 3
Então temos que mdc (27, 6) = mdc (6, 3)
E, finalmente, 6 = 2 x 3 + 0 
Como 6 é um múltiplo de 3, então temos
que mdc (6, 3) = 3, e por conseguinte
mdc (27, 33) = 3
Calcular o mdc (27, 33)
Voltando ao Teorema de Euclides estendido
Se c = mdc(a,b) então existe
solução inteira para c = ax + by
Podemos criptografar 2 caracteres (x,y) 
enviando cifra c e chave (a,b)
A relação entre c e (a,b) não é direta
Usado em criptografia de chave pública 
para comércio eletrônico, RSA
Logaritmos Discretos
Suponha que se deseje calcular todos os n 
que produzem a constante k para aplicação 
criptográfica
an mod b =k
Se conhecemos a, b e K então n
pode ser calculado 
x*b - an=k então an = xb –k e para 
extrairmos n devemos aplicar o log
O problema do logaritmo discreto
Sabemos que se zv =t então v=logz t 
aplicando a nossa equação
an = xb –k n=loga (xb-k) 
matematicamente simples, mas calcular 
o log é um trabalho longo e demorado
5
Observou-se que também as 
potências na matemática 
modular são cíclicas
31 mod 7 = 3
32 mod 7 = 2
33 mod 7 = 6
34 mod 7 = 4
35 mod 7 = 5
36 mod 7 = 1
37 mod 7 = 3
38 mod 7 = 2
39 mod 7 = 6
310 mod 7 = 4
311 mod 7 = 5
312 mod 7 = 1
Este conhecimento permite 
utilizar o expoente como 
forma de codificação, 
tornando a reversão 
computacionalmente 
impossível
Euler e Fermat evoluem um 
pouco mais esta coincidência
matemática
31 mod 7 = 3
32 mod 7 = 2
33 mod 7 = 6
34 mod 7 = 4
35 mod 7 = 5
36 mod 7 = 1
37 mod 7 = 3
38 mod 7 = 2
39 mod 7 = 6
310 mod 7 = 4
311 mod 7 = 5
312 mod 7 = 1
Teoremas de Euler e Fermat
Se “p” é um número primo, então
ap ≡ a mod p e
ap-1 ≡ 1 mod p
Podemos então codificar a se encontrarmos 
o p que satisfaz a congruência e é primo
O que nos levaria ao problema de 
encontrar números primos
Pequeno Teorema de Fermat
Se “p” é um número primo, então
ap = a mod p e
ap-1 = 1 mod p
Euler associou este teorema com o problema 
dos logaritmos discretos e sua conclusão 
sobre a quantidade de números primos entre 
si abaixo de determinado número, dita Ф(n), 
segundo a qual, se n é primo, Ф(n)= n-1
Pequeno Teorema de Fermat
e conclusão de Euler
Desta forma, Euler foi capaz de calcular “t” 
período de repetição do resultado modular 
em função da base e do expoente
Facilitando os cálculos do logaritmo discreto
E facilitando os cálculos de criptografia
Teorema de Euler
6
Testes de Fermat e Miller-Rabin
O uso de números primos grandes 
é essencial para criptografia, mas 
como identificá-los?
O teste de Fermat
O teste de Miller-Rabin
Segundo o pequeno teorema de Fermat, se 
o número n é primo, então para qualquer a 
temos que an-1 = 1(mod n) para a
∈ {1, ..., n − 1}
Na verdade este teste apenas
garante que a e n são coprimos
Os testes de Fermat
Dado n, encontramos s de modo
que n−1 = 2sq para algum q ímpar
Escolhemos um valor aleatório para
a de tal modo que a ∈ {1, ..., n − 1}
Se aq = 1, então n passa no teste,
e finalizamos o teste
O teste de Miller-Rabin
Para toda iteração i = 0, ..., s − 1
verificamos se 
aj = −1, com j=2iq
Caso seja, n passa no teste,
e finalizamos o teste
Caso contrário, n é um número composto, 
e, portanto, não é primo
Finalizando
7
A criptografia é uma ciência matemática 
ligada à teoria dos números
O principal mote na modelagem matemática 
do problema criptografia é a reversibilidade
A operação de fatoração não é facilmente 
reversível do ponto de vista computacional