Teoria dos Números e Criptografia RSA

Prévia do material em texto

1 O Teorema Fundamental da Aritmética (wiki) sustenta que todos os números inteiros positivos maiores que 1 [1] podem ser decompostos num produto de números primos, sendo esta decomposição única a menos de permutações dos fatores. O que você entendeu desse Teorema? dê exemplos de números decompostos em números primos. 
É possível entender a partir deste Teorema que qualquer número inteiro e positivo pode ser decomposto em números primos. O que significa que que pode ser dividido por algum número primo até se chegar ao 1 que não é possível dividir. São exemplos: 15 / 3 = 5 / 5 = 1 ou seja 15 = 3 * 5 e também 10 / 2 = 5 / 5 = 1 ou seja 10 = 2 * 5.
2 O Crivo de Eratóstenes (wiki) é um algoritmo e um método simples e prático para encontrar números primos até um certo valor limite. Segundo a tradição, foi criado pelo matemático grego Eratóstenes (a.c. 285-194 a.C.), o terceiro bibliotecário-chefe da Biblioteca de Alexandria. Utilizando o Crivo de Eratóstenes encontre todos os números primos compreendidos entre 1 e 30. 
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	16
	17
	18
	19
	20
	21
	22
	23
	24
	25
	26
	27
	28
	29
	30
· Inicialmente, deve-se cortar o número 1
· Criei uma lista de todos os números inteiros de 2 até o valor limite: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, e 30.
· Removi da lista todos os múltiplos de 2 até o valor limite. Fica: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27 e 29.
· O próximo número da lista é 3. Removendo seus múltiplos, a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25 e 29. 
· O próximo número, 5, também é primo; a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. 5 é o último número a ser verificado, conforme determinado inicialmente. 
· Assim, a lista encontrada contém somente números primos, fica: 2, 3, 5, 7, 11, 13, 17, 19, 23,39
3 Chamamos números primos entre si (ou coprimos) (wiki) ao conjunto de números onde o único divisor comum a todos eles é o número 1. Liste os números coprimos de 10 e os números coprimos de 11. 
Sobre o número 10: 10 = 1, 2, 5, 10 | 21 = 1, 3, 7, 21 | 31 = 1, 31 (primo) | 37 = 1, 37 (primo) Assim, podemos determinar que são coprimos de 10: 21, 31 e 37. 
Sobre o número 11: 11 = 1, 11 (primo) | 25 = 1, 5, 25 | 34 = 1, 2, 17, 34. Assim, podemos determinar que são coprimos de 11: 25 e 34.
4 A função totiente (wiki), por vezes também chamada de função tociente, ou função phi (fi), – representada por φ(x) – é, na teoria dos números, definida para um número natural x como sendo igual à quantidade de números menores ou igual a x co-primos com respeito a ele. Qual o resultado de fi(10), fi(11), fi(20)? 
10 = 2 * 5
fi(10) = 10(1 – ½)(1 – 1/5) = 10 * 0,5 * 0,8 = 4
11 = 11
fi(11) = 11(1 - 1/11) = 11 * 0,91 = 10,01 = 10
20 = 2 * 2 * 5
fi(20) = 20(1 – ½)(1 – 1/5) = 20 * 0,5 * 0,8 = 8
5 Qual a relação entre números primos e a criptografia RSA?
A reçação diz repeito ao fato de RSA utiliza os números primos em forma do conceito de fatorização em fatores primos para assim gerar a chave pública e privada dessa criptografia. A chave pública é a multiplicação de 2 grandes números primos enquanto a chave privada é formada pelos números primos utilizados na multiplicação da chave pública.