Números Inteiros e Criptografia (21-1)

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

Listas de Exercícios & Trabalho Final

ListaData 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 324 de setembro às 18:00
Lista 44 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

DataHorárioAulaConteúdoLinks
seg 12 jul13-15Prática 01Parte 1: Apresentação da disciplina, assuntos administrativos; Parte 2: Abstração em computação e matemáticaQuadro, Código, Vídeo 1, Vídeo 2, Chat 1, Chat 2
ter 13 jul8-10Teórica 01Teoremas e ProvasQuadro, Vídeo, Chat
qui 15 jul8-10Teórica 02Parte 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 piQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
seg 19 jul13-15Prática 02Parte 1: Revisão da primeira semana; Parte 2: Minicurso de python; definição de função em python; tipos numéricosQuadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2
ter 20 jul8-10Teórica 03Parte 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 jul8-10Teórica 04Parte 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 jul13-15Prática 03Parte 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 TutorQuadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
ter 27 jul8-10Teórica 05Parte 1: Divisão entre números inteiros; Parte 2: Exemplos motivadores: cifras aditiva e multiplicativa; Parte 3: Definição de divisibilidade e mdcQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
qui 29 jul8-10Teórica 06Parte 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 ago13-15Prática 04Parte 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 ago8-10Teórica 07Parte 1: Corretude do Algoritmo de Euclides; Parte 2: Mais discussão sobre cifras aditiva e multiplicativaQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 5 ago8-10Teórica 08Parte 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 ago13-15Prática 05Parte 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 ago8-10Teórica 09Parte 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 AIFQuadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 12 ago8-10Teórica 10Parte 1: Terminação do AIF; Parte 2: Corretude do AIFQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
seg 16 ago13-15Prática 06Parte 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 ago8-10Teórica 11Parte 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 ago8-10Teórica 12Parte 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 ago13-15Prática 07Parte 1: Comentários sobre a L1Q1; Parte 2: Terminação e Corretude do Crivo de EratóstenesQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
ter 24 ago8-10Teórica 13Parte 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 ago8-10Teórica 14Parte 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 ago13-15Prática 08Parte 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 quadradoQuadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2
ter 31 ago8-10Teórica 15Parte 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 coprimosQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 2 set8-10Teórica 16Parte 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 setsem aulaFeriado
ter 7 setsem aulaFeriado
qui 9 set8-10Teórica 17Parte 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óiQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
seg 13 set13-15Prática 09Parte 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 set8-10Teórica 18Parte 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ênciaQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 16 set8-10Teórica 19Parte 1: Dúvidas da Lista 3; Inteiros módulo n; Parte 2: Adição em Z_nQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
seg 20 set13-15Prática 10Parte 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 set8-10Teórica 20Parte 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 set8-10Teórica 21Parte 1: Equivalência entre PTF1 e PTF2; Parte 2: Prova do PTF1Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
seg 27 set13-15Prática 11Parte 1: Teste de Fermat; Parte 2: Pseudoprimos de Fermat; Números de Carmichael; Teorema de KorseltQuadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2
ter 28 set8-10Teórica 22Parte 1: Dúvidas da Lista 4; Prova da “volta” do Teorema de Korselt usando L4Q2c; Parte 2: Ideias a caminho do Teste de Miller-RabinQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 30 set8-10Teórica 23Parte 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 out13-15Prática 12Parte 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 RSAQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
ter 5 out8-10Teórica 24Parte 1: RSA (como garantir que b^ed = b mod pq); Parte 2: O funcionamento do RSA de fatoQuadro, Código, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 7 out8-10Teórica 25Parte 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 outsem aulaFeriado
ter 12 outsem aulaFeriado
qui 14 out8-10??(apenas sob demanda)
seg 18 out13-15Aula DúvidaDúvidas do Trabalho FinalVídeo, Chat
ter 19 out8-10??(apenas sob demanda)
qui 21 out9-10FinalAtividade 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.