Números Inteiros e Criptografia (19-1)

  • Professor: Hugo Nobrega
  • Monitores: Lucas Dias e João Pedro Seda (contato via Telegram). Plantão de monitoria às terças (15:00), quando o monitor for o Lucas, ou às sextas (13:00), quando for o João Pedro, no Lab. 1 (dentro do DCC). Os monitores se alternam a cada semana.

Bibliografia

  • Livro-texto: S. C. Coutinho, Números Inteiros e Criptografia RSA, Segunda Edição, Coleção Matemática e Aplicações, IMPA, 2014.
  • Leitura complementar: L. M. Schechter, Uma Introdução à Criptografia de Chave Pública Através do Método El Gamal, Notas em Matemática Aplicada, Volume 77, SBMAC, 2014. Disponível gratuitamente na internet

Listas de exercícios

As listas de exercícios e (algumas) atividades de laboratório contarão como 20% da média final. Teremos uma lista de exercícios para cada capítulo do livro que cobrirmos.

ListaCapítulo do livro-textoExercíciosData limite para entrega
Lista 1Cap. 1, pág. 321 (apenas itens (2) e (3)), 3, 4, 74 de abril às 8:00.
Lista 2Cap. 2, pág. 482, 3, 7, 9, 1015 de abril às 13:00.
Lista 3Cap. 3, pág. 663, 4, 5, 6, 725 de abril às 8:00.
Lista 4Cap. 4, pág. 851, 3, 4, 62 de maio às 8:00.
Lista 5Cap. 5, pág. 1001 (apenas itens (3) e (4)), 3, 5, 1013 de maio às 13:00.
Lista 6Cap. 6, pág. 1155, 7 + Enunciar & provar teoremas de terminação e corretude para o Teste de Miller–Rabin27 de maio às 13:00.
Lista 7Cap. 7Lista 73 de junho às 13:00.
Lista 8Caps. 8–11Lista 827 de junho às 8:00.

Cronograma e histórico de aulas

DataAtividadeLivro-texto
11 de marçosem aula
12 de marçosem aula
14 de marçosem aula
18 de marçoLab: Introdução. Código visto em sala.
19 de marçoRevisão ens. médio. Exercícios.
21 de marçoTeoremas e algoritmos; divisão0.7 a 1.2
25 de marçoLab: Breve introdução ao Python_; implementação do algoritmo ingênuo de divisão. Extra:_ Cifra polialfabética (Gabriel)
26 de marçoDivisão (cont.) e mdc; Algoritmo (básico) de Euclides1.3 a 1.5
28 de marçoAlgoritmo Estendido de Euclides1.5 e 1.6
1 de abrilLab: Algoritmo Estendido de Euclides
2 de abrilAlgoritmo (ingênuo) para fatoração em números primos2.1, 2.2 e 2.6
4 de abrilAlgoritmo de Fermat; unicidade da fatoração em números primos2.3 a 2.5, 2.8
8 de abrilLab: Fatoração única
9 de abrilaula cancelada devido às chuvas
11 de abrilUnicidade da fatoração em números primos (replay); infinidade dos primos; crivo de Eratóstenes2.8, 3.5, 3.6
15 de abrilLab: Crivo de Eratóstenes.
16 de abrilRelações de equivalência e de congruência; inteiros módulo \(n\); aritmética modular4.1, 4.2, 4.3
18 de abrilAritmética modular (cont.); aplicações: restos de divisões de potências de inteiros (enormes) por inteiros (pequenos) e equações lineares em \(\mathbb{Z}\_n\)4.3, 4.5, 4.7
22 de abrilsem aula
23 de abrilsem aula
25 de abrilRecursão e Indução
29 de abrilLab: recursão e indução; Torre de Hanói
30 de abrilIndução (cont.) e Pequeno Teorema de Fermat
2 de maioPequeno Teorema de Fermat (cont.), Teste de Fermat e números de Carmichael
6 de maioLab: Teste de Fermat e números de Carmichael; Código visto em sala
7 de maioTeste de Miller–Rabin
9 de maioRevisão para a P1
13 de maioProva 1 (primeira parte) NA SALA F3.014
14 de maioProva 1 (segunda parte) NA SALA F3.014
16 de maioTeste de Miller–Rabin (cont.); sistemas de congruências
20 de maioLab: discussão da P1
21 de maiosem aula
23 de maioTeorema chinês dos restos
27 de maioLab: Teste de Miller–Rabin; Teorema chinês dos restos
28 de maioGrupos: introdução, o grupo U(n) e a função totiente de Euler
30 de maiosem aula (paralisação da educação)
3 de junhoLab: Função totiente de Euler
4 de junhoGrupos cíclicos; Subgrupos; Teorema de Lagrange
6 de junhoTeorema de Lagrange (cont.); Teorema de Euler; “Lema chave” (Seção 9.1); Teorema da Raiz Primitiva (Seções 10.4 e 10.5)
10 de junhoLab: aplicações do Teorema de Euler
11 de junhoTeorema da Raiz Primitiva (cont.)
13 de junhoCriptografia RSA (Cap. 11)
17 de junhoLab: RSA
18 de junhosem aula
20 de junhosem aula
24 de junhoLab: revisão para P2
25 de junhoProva 2 (1a parte)
27 de junhoProva 2 (2a parte)
1 de julhoLab: Discussão da P2
2 de julhoProva final (1a parte)
4 de julhoProva final (2a parte)
8 de julhoLab: a definir
9 de julhoProva final (2a ch.) (1a parte)
11 de julhoProva final (2a ch.) (2a parte)

Método de avaliação

Duas provas, \(P1\) e \(P2\), e diversas listas de exercícios. Os monitores são responsáveis pela correção das listas.

A média teórica \(M_T\) é a média aritmética simples das notas das duas provas. A média prática \(M_P\) é a média aritmética simples das \(n\) melhores listas de exercícios (a definir). A média parcial \(M\) é a média ponderada entre \(M_T\) (peso 4) e \(M_P\) (peso 1). Se \(M \geq 7\), então aprovado. Se \(M < 3\), então reprovado. Se \(3 \leq M < 7\), então o aluno vai para a prova final, \(PF\). Neste caso, se a média aritmética simples entre \(M\) e \(PF\) for \(\geq 5\), aprovado; caso contrário, reprovado.

Segunda chamada

A segunda chamada só é direito para casos devidamente justificados dentro do prazo de 48 horas.

Caso o aluno precise fazer segunda chamada da \(P1\) ou da \(P2\), a \(PF\) servirá como segunda chamada; neste caso, se a média \(M\) obtida satisfizer \(3 \leq M < 7\), o aluno faz a prova \(PF_2\). Caso o aluno faça \(P1\) e \(P2\) mas precise faltar a \(PF\), então a sua prova final será a prova \(PF_2\).

Se a média aritmética simples entre \(M\) e \(PF_2\) for \(\geq 5\), aprovado; caso contrário, reprovado.