- Professor: Hugo Nobrega
- Monitores: Antônio Faria, Kevin Sena e João Matheus Gonçalves
- Grupo de discussões no Telegram: https://t.me/joinchat/Rn5lLUh9B61lMDcx
- Plantão de monitoria: a decidir
- Pasta do Google Drive com vídeos de aula e demais arquivos: https://drive.google.com/drive/folders/197uHlwDV9FPyjKckKW789VhlQiTytIVK?usp=sharing (para obter acesso, cadastre-se aqui)
Funcionamento da disciplina
O meio primário de comunicação entre os alunos, monitores e professores será pelo Telegram, no grupo https://t.me/joinchat/Rn5lLUh9B61lMDcx
As aulas serão realizadas em modo síncrono, com aulas teóricas às 3as e 5as de 8:00 às 10:00 e com aulas práticas/conversas/dúvidas às 2as de 13:00 às 15:00. Esses encontros serão gravados e disponibilizados para todos os alunos que queiram acompanhar em modo assíncrono. A escolha entre modo síncrono e/ou assíncrono é completamente livre para cada aluno.
Bibliografia
- Notas de Aula
- 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
- Uma boa fonte adicional (porém em inglês) para o material de provas, lógica, conjuntos, etc. (que não está presente nos livros acima) é: R. Hammack, Book of Proof, 3a edição. Disponível gratuitamente na internet
Listas de Exercícios & Trabalho Final
| Lista | Data Limite de Entrega |
|---|---|
| Lista 1 (atualizada em 17 de agosto) | 20 de agosto às 18:00 |
| Lista 2 (atualizada em 1o de setembro) | 10 de setembro às 18:00 |
| Lista 3 | 24 de setembro às 18:00 |
| Lista 4 | 4 de outubro às 18:00 |
| Trabalho Final (atualizado em 14 de outubro) | 21 de outubro às 9:00 |
Regras de colaboração
É permitido (e até recomendado) que os alunos estudem juntos, porém cada aluno(a) deve escrever e entregar suas próprias soluções. Soluções iguais ou muito parecidas serão desconsideradas. Para evitar problemas, recomendo que você nem mesmo olhe soluções prontas de seus colegas, e também recomendo que ao discutir soluções com colegas, você não tenha as sua soluções abertas à sua frente.
Cronograma planejado/registro de atividades
| Data | Horário | Aula | Conteúdo | Links |
|---|---|---|---|---|
| seg 12 jul | 13-15 | Prática 01 | Parte 1: Apresentação da disciplina, assuntos administrativos; Parte 2: Abstração em computação e matemática | Quadro, Código, Vídeo 1, Vídeo 2, Chat 1, Chat 2 |
| ter 13 jul | 8-10 | Teórica 01 | Teoremas e Provas | Quadro, Vídeo, Chat |
| qui 15 jul | 8-10 | Teórica 02 | Parte 1: Implicações; contrapositiva; recíproca; Parte 2: Redução ao Absurdo (prova por contradição); princípio das casas dos pombos; dígitos de pi | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 19 jul | 13-15 | Prática 02 | Parte 1: Revisão da primeira semana; Parte 2: Minicurso de python; definição de função em python; tipos numéricos | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 20 jul | 8-10 | Teórica 03 | Parte 1: Algoritmos; Parte 2: Algoritmo Ingênuo da Divisão (AID); enunciado, teste de mesa, Terminação e Corretude (parcial) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 22 jul | 8-10 | Teórica 04 | Parte 1: Corretude do AID (conclusão); “existe único”; Parte 2: Existência e unicidade de quociente e resto (parcial) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 26 jul | 13-15 | Prática 03 | Parte 1: Comentários sobre a disciplina, método de avaliação; Parte 2: Prova da unicidade do quociente e resto; Parte 3: Minicurso de Python (booleanos, if/elif/else, while); implementação do AID em Python; Python Tutor | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| ter 27 jul | 8-10 | Teórica 05 | Parte 1: Divisão entre números inteiros; Parte 2: Exemplos motivadores: cifras aditiva e multiplicativa; Parte 3: Definição de divisibilidade e mdc | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| qui 29 jul | 8-10 | Teórica 06 | Parte 1: Propriedades de divisibilidade e mdc; Parte 2: Algoritmo ingênuo do mdc (enunciado e implementação); Algoritmo de Euclides (enunciado e terminação) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 2 ago | 13-15 | Prática 04 | Parte 1: Implementação do Algoritmo de Euclides; Parte 2: Minicurso de Python (mutabilidade, for, range, listas, strings) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 3 ago | 8-10 | Teórica 07 | Parte 1: Corretude do Algoritmo de Euclides; Parte 2: Mais discussão sobre cifras aditiva e multiplicativa | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 5 ago | 8-10 | Teórica 08 | Parte 1: Descriptação na cifra multiplicativa; Parte 2: Descriptação na cifra multiplicativa (cont.); Parte 3: Teorema de Bézout; Algoritmo Estendido de Euclides (ideia) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| seg 9 ago | 13-15 | Prática 05 | Parte 1: Dúvidas da Lista 1; Parte 2: Algoritmo Estendido de Euclides (enunciado); Parte 3: Algoritmo Estendido de Euclides (implementação, terminação, corretude) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| ter 10 ago | 8-10 | Teórica 09 | Parte 1: Números primos; Teorema Fundamental da Aritmética (enunciado); Parte 2: Prova parcial da “existência” no TFA; Algoritmo ingênuo de fatoração (AIF); Implementação e prova parcial de corretude do AIF | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 12 ago | 8-10 | Teórica 10 | Parte 1: Terminação do AIF; Parte 2: Corretude do AIF | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 16 ago | 13-15 | Prática 06 | Parte 1: Dúvidas da Lista 1; Parte 2: Minicurso de Python (mutabilidade, tuplas, dicionários, conjuntos); reimplementação do AIF usando dicionários; Parte 3: Propriedade Fundamental dos Primos (PFP, enunciado); Lema da seção 2.6 do livro-texto (prova) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| ter 17 ago | 8-10 | Teórica 11 | Parte 1: Prova da Propriedade Fundamental dos Primos (PFP); Parte 2: Prova da unicidade no TFA; Parte 3: Discussão sobre a dificuldade de fatorar; Teorema de Infinitude dos Primos (enunciado) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| qui 19 ago | 8-10 | Teórica 12 | Parte 1: Infinitude dos Primos; Parte 2: Crivo de Eratóstenes (algoritmo e implementação) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 23 ago | 13-15 | Prática 07 | Parte 1: Comentários sobre a L1Q1; Parte 2: Terminação e Corretude do Crivo de Eratóstenes | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 24 ago | 8-10 | Teórica 13 | Parte 1: Definições recursivas (exemplos Fibonacci, Collatz, etc, e discussão); Parte 2: Torres de Hanói (introdução) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 26 ago | 8-10 | Teórica 14 | Parte 1: Mais discussão sobre funções recursivas; calculando “de cima pra baixo” e “de baixo pra cima”; Parte 2: “Memoização” de função recursiva; Implementação do algoritmo das Torres de Hanói; Análise do número de passos do algoritmo de Hanói; Indução (ideia) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 30 ago | 13-15 | Prática 08 | Parte 1: Dúvida da lista 2; recap de Hanói; implementação de Hanói em Python usando listas e mutabilidade; a definição recursiva de “hasheabilidade” em Python; Parte 2: Indução; a soma dos primeiros n ímpares é n ao quadrado | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 31 ago | 8-10 | Teórica 15 | Parte 1: Provas por indução; soma dos n primeiros ímpares é n ao quadrado; 3 divide a diferença entre n ao cubo e n; Parte 2: Fibonaccis consecutivos são coprimos | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 2 set | 8-10 | Teórica 16 | Parte 1: Dúvidas da Lista 2; Exemplo de indução (Q5 da L6 de 2020.2); Indução vista nos livros (“fraca” e “forte”); Parte 2: Exemplo de indução (fórmula de Binet para Fibonacci) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 6 set | sem aula | Feriado | ||
| ter 7 set | sem aula | Feriado | ||
| qui 9 set | 8-10 | Teórica 17 | Parte 1: Dúvidas da Lista 2; Parte 2: Provas indutivas de terminação e corretude do Fibonacci recursivo; Parte 3: Provas de terminação e corretude de Hanói | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| seg 13 set | 13-15 | Prática 09 | Parte 1: Dúvidas da lista 3; Prova do número de passos de Hanói; Parte 2: Refazendo o AID recursivamente; prova indutiva de terminação do AID recursivo (sem reticências ou afins) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 14 set | 8-10 | Teórica 18 | Parte 1: Relações; Propriedades (reflexividade, simetria, transitividade, rel. de equivalência, antissimetria, ordem parcial); exemplos; Parte 2: A aparência das relações de equivalência; classes de equivalência | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 16 set | 8-10 | Teórica 19 | Parte 1: Dúvidas da Lista 3; Inteiros módulo n; Parte 2: Adição em Z_n | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 20 set | 13-15 | Prática 10 | Parte 1: Dúvidas da Lista 3; Parte 2: Aritmética modular (inverso aditivo, subtração, multiplicação, potenciação com expoente natural) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 21 set | 8-10 | Teórica 20 | Parte 1: Mais exemplos de potências em aritmética modular; potências em aritmética modular em python (pow); Parte 2: Divisão em aritmética modular; Parte 3: Pequeno Teorema de Fermat (investigação e enunciado, PTF1 e PTF2) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| qui 23 set | 8-10 | Teórica 21 | Parte 1: Equivalência entre PTF1 e PTF2; Parte 2: Prova do PTF1 | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 27 set | 13-15 | Prática 11 | Parte 1: Teste de Fermat; Parte 2: Pseudoprimos de Fermat; Números de Carmichael; Teorema de Korselt | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 28 set | 8-10 | Teórica 22 | Parte 1: Dúvidas da Lista 4; Prova da “volta” do Teorema de Korselt usando L4Q2c; Parte 2: Ideias a caminho do Teste de Miller-Rabin | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 30 set | 8-10 | Teórica 23 | Parte 1: Teste de Miller–Rabin (algoritmo); Parte 2: Teste de Miller–Rabin (implementação e discussão) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| seg 4 out | 13-15 | Prática 12 | Parte 1: Recap do Teste de Miller–Rabin; Parte 2: Criptografia (transformação de texto em número; quebra em blocos); Parte 3: A ideia do RSA | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| ter 5 out | 8-10 | Teórica 24 | Parte 1: RSA (como garantir que b^ed = b mod pq); Parte 2: O funcionamento do RSA de fato | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 7 out | 8-10 | Teórica 25 | Parte 1: Discussão das questões do TF; Parte 2: Segurança do RSA (dificuldade de obter d a partir de n&e); Parte 3: Segurança do RSA (escolha dos primos p&q) | Quadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| seg 11 out | sem aula | Feriado | ||
| ter 12 out | sem aula | Feriado | ||
| qui 14 out | 8-10 | ?? | (apenas sob demanda) | |
| seg 18 out | 13-15 | Aula Dúvida | Dúvidas do Trabalho Final | Vídeo, Chat |
| ter 19 out | 8-10 | ?? | (apenas sob demanda) | |
| qui 21 out | 9-10 | Final | Atividade de encerramento (troca de mensagens com RSA) |
Método de avaliação
Teremos listas de exercícios aproximadamente a cada 10 dias, valendo nota, mas descartaremos as duas piores notas ao longo do período. Além disso, teremos um trabalho final.
Se a nota no trabalho final for menor do que 5,0, essa também será a nota final do/a aluno/a. Caso contrário, a nota final será a média aritmética entre a nota do trabalho e a média aritmética das notas das listas (após os descartes).
A nota final mínima para aprovação é 5,0.
Os monitores farão a correção das listas, sob supervisão e responsabilidade do professor. O professor fará a correção do trabalho final.