Teoria dos Números para Computação

Prévia do material em texto

1
Prof. Luis Gonzaga de Paulo
Matemática Computacional
Aula 6
Conversa Inicial
A solução de problemas computacionais 
requer o conhecimento de diversos tipos de 
operações, fórmulas, teoremas e métodos de 
cálculos desenvolvidos ao longo da história
Temas da teoria dos números são cruciais 
para o desenvolvimento de soluções 
computacionais
Criptografia, criptologia, robótica, 
automação, inteligência artificial
Aritmética modular
Algoritmo de Euclides
Logaritmos discretos
Teoremas de Euler e de Fermat
Testes de Fermat e de Miller-Rabin
Aritmética modular
Dois inteiros do conjunto �n (x e y) são iguais 
se x e y diferem por um múltiplo de n
x = y (mod n)
Exemplos:
38 = 3 (mod 5), pois 38 = 7 x 5 + 3
-3 = 11 (mod 14), pois -3 = (-1) x 14 + 11
2
x e y são congruentes módulo n
Inteiros regulares são vistos como se 
estivessem em uma linha numérica
Inteiros módulo n são vistos como se 
estivessem em um círculo
Algoritmo de Euclides
Forma mais simples e eficiente de encontrar 
o MDC (máximo divisor comum) entre dois 
inteiros diferentes de zero
É um dos algoritmos mais antigos: surgiu por 
volta de 300 a.C. (Euclides – Elementos, 
Livros VII e X)
Elemento-chave do método de criptografia de 
chave pública usado no comércio eletrônico, 
o algoritmo RSA
O 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 (x, y) = mdc (y, r)
Em que r é o resto da divisão de x por y
x = r (mod y) 
Se mdc (x, y) = 1, x e y são coprimos ou 
relativamente primos
Se d divide x e d divide y, então d divide 
também a soma de x e y
De modo semelhante, divide também a 
diferença entre eles: (x – y)
Calcular mdc (x, x – y) e repetir até zerar o 
resto para o resultado
Calcular o mdc (27, 33)
Primeiro dividimos o maior número pelo 
menor: 33 = 1 x 27 + 6
Então, temos que mdc (27, 33) = 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, 6) = 3, mdc (27, 33) = 3
3
Logaritmos discretos
Calcular 35 módulo 7
35 = 243 ���� 243 mod 7 = 5
34 = (32)2 ���� 32 = 9, e 9 mod 7 = 2
���� 34 mod 7 = 4 = 22
Finalmente
35 mod 7 = (34 x 3) mod 7 = (4 x 3) mod 
7 = 5
O problema do logaritmo discreto
Seja p um número primo, e g, h dois 
elementos de ��∗
Se gx = h (mod p), qual é o valor de x?
Não conhecemos nenhum algoritmo rápido 
para encontrar os logaritmos discretos
Teoremas de Fermat e de Euler
Pequeno teorema de Fermat
Dado um número primo p, então ap = a
(mod p) para qualquer a ∈∈∈∈ ��	
(x + y)p = xp + yp (mod p)
ap ≡≡≡≡ a (mod p)
ap-1 ≡≡≡≡ 1 (mod p)
Modo genérico do pequeno teorema de 
Fermat
Se a ∈∈∈∈ ��∗ , então aϕ(n) = 1 (mod n)
Para todo a ∈∈∈∈ ��∗ , o valor de a-1 pode ser 
calculado como aϕ(n)-1
4
Testes de Fermat e Miller-Rabin
O uso de grandes números primos é 
essencial para algoritmos de criptografia
O problema: identificar um grande número 
primo
Teste de teorema de Fermat
Se o número n é primo, então para 
qualquer a temos que an-1 = 1 (mod n)
E os números Carmichael ou pseudoprimos?
Podemos obter um fator de n calculando 
o mdc (a, n)
Teste de Miller-Rabin
n é primo se e somente se as soluções 
de x2 = 1 (mod n) são somente x = ± 1
Se an-1 = 1, então a(n - 1)/2 = ± 1, pois 
a(n - 1)/2���� raiz quadrada de 1
(...)
(...)
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
Para toda iteração i = 0, ..., s - 1 verificamos se 
�	
� = 1. Caso seja, n passa no teste, e 
finalizamos o teste
Caso contrário, n é um número composto, 
portanto não é primo
Referências
5
BONAFINI, F. C. Matemática e estatística. São 
Paulo: Pearson Education do Brasil, 2014. 
GERSTING, J. L. Fundamentos matemáticos 
para a ciência da computação: um tratamento 
moderno de matemática discreta. Rio de 
Janeiro: LTC, 2015.
HUNTER, D. J. Fundamentos da matemática 
discreta. Rio de Janeiro: LTC, 2011.
LEITE, A. E.; CASTANHEIRA, N. P. Teoria dos 
números e teoria dos conjuntos. Curitiba: 
InterSaberes, 2014.
LYNN, B. Number theory. Disponível em: 
<https://crypto.stanford.edu/pbc/notes/numbe
rtheory/>. Acesso em: 22 jun. 2019.
MACEDO, L. R. D.; CASTANHEIRA, N. P.; ROCHA, 
A. Tópicos de matemática aplicada. Curitiba: 
InterSaberes, 2013.
SHOUP, V. A primer on algebra and number 
theory for computer scientists. Disponível em: 
<https://cs.nyu.edu/courses/fall02/G22.3033-
010/notes.pdf>. Acesso em: 22 jun. 2019.
STEIN, C.; DRYSDALE, R. L.; BOGART, K. 
Matemática discreta para ciência da 
computação. São Paulo: Pearson Education 
do Brasil, 2013.
VIEIRA, N. J. Introdução aos fundamentos da 
computação: linguagens e máquinas. São 
Paulo: Pioneira Thomson Learning, 2005.
WALPOLE, R. E.; MYERS, R. H.; MYERS, S. L.; 
YE, K. Probabilidade e estatística para 
engenharia e ciências. 8. ed. São Paulo: 
Pearson Prentice Hall, 2009.