Números Inteiros e Criptografia (20-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/NCZpYFRTp9ZXtThc8ftKZQ

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

  • 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

ListaData Limite de Entrega
Lista 111 de dezembro às 18:00
Lista 218 de dezembro às 18:00
Lista 3 (parte 1)23 de dezembro às 23:59
Lista 4 (atualizada em 11 de janeiro)15 de janeiro às 18:00
Lista 5 (atualizada em 20 de janeiro)22 de janeiro às 18:00
Lista 629 de janeiro às 18:00
Lista 75 de fevereiro às 18:00
Lista 819 de fevereiro às 18:00
Trabalho Final3/3 às 18:00

Cronograma planejado/registro de atividades

DataHorárioAulaConteúdoLinks
seg 30/1113-15Prát. 1Apresentação da disciplina; Minicurso de Python (início)Quadro (Jamboard) Quadro (PDF) Código Vídeo 1 (Apresentação da disciplina) Chat 1 Vídeo 2 (Minicurso de Python (início)) Chat 2
ter 1/128-10Teór. 1Teoremas, provas, conectivos, tabelas de verdadeQuadro (Jamboard) Quadro (PDF) Vídeo (Teoremas, provas, conectivos, tabelas de verdade) Chat
qui 3/128-10Teór. 2Contraexemplos, algumas estratégias de prova (prova por casos, contrapositiva), tautologia; Quantificadores para todo e existeQuadro (Jamboard) Quadro (PDF) Vídeo (Contraexemplos, algumas estratégias de prova (prova por casos, contrapositiva), tautologia; Quantificadores para todo e existe) Chat
seg 7/1213-15Prát. 2Dúvidas da Lista 1; Minicurso de Python (cont.)Quadro (Jamboard) Quadro (PDF) Código Video 1 (Dúvidas da Lista 1) Chat 1 Vídeo 2 (Minicurso de Python (cont.)) Chat 2
ter 8/128-10Teór. 3Conjuntos, união, interseção, diferença, subconjuntos, conjunto das partesQuadro (Jamboard) Quadro (PDF) Vídeo (Conjuntos, união, interseção, diferença, subconjuntos, conjunto das partes) Chat
qui 10/128-10Teór. 4Quantificadores relativizados, Vacuidade; Relações, representação gráfica ou em tabela, propriedades de relaçõesQuadro (Jamboard), Quadro (PDF), Vídeo 1 (Quantificadores relativizados, Vacuidade), Chat 1, Vídeo 2 (Relações, representação gráfica ou em tabela, propriedades de relações), Chat 2
seg 14/1213-15Prát. 3Dúvidas sobre quantificadores “existem pelo menos n” e “existem no máximo n”Quadro (Jamboard), Quadro (PDF), Código, Vídeo (Dúvidas sobre quantificadores “existem pelo menos n” e “existem no máximo n”), Chat
ter 15/128-10Teór. 5Propriedades de relações; ordens parciais; relações de equivalênciaQuadro (Jamboard), Quadro (PDF), Vídeo (Propriedades de relações; ordens parciais; relações de equivalência), Chat
qui 17/128-10Teór. 6Exemplo de relação e propriedades; Provas existenciais não construtivas; redução ao absurdo; princípio das casas dos pombos; Provas existenciais construtivas; algoritmos; Algoritmo Ingênuo da DivisãoQuadro (Jamboard), Quadro (PDF), Vídeo 1 (Exemplo de relação e propriedades), Chat 1, Vídeo 2 (Provas existenciais não construtivas; redução ao absurdo; princípio das casas dos pombos), Chat 2, Vídeo 3 (Provas existenciais construtivas; algoritmos; Algoritmo Ingênuo da Divisão), Chat 3
seg 21/1213-15Prát. 4Dúvidas das listas 2 e 3; Minicurso de Python: while; implementação do algoritmo ingênuo de divisãoQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Dúvidas das listas 2 e 3), Chat 1, Vídeo 2 (Minicurso de Python: while; implementação do algoritmo ingênuo de divisão), Chat 2
ter 22/128-10Teór. 7Terminação e Corretude do Alg. Ingênuo da Divisão; Relação de divisibilidade; mdc; números primos e coprimosQuadro (Jamboard), Quadro (PDF), Vídeo 1 (Terminação e Corretude do Alg. Ingênuo da Divisão), Chat 1, Vídeo 2 (Relação de divisibilidade; mdc; números primos e coprimos), Chat 2
qui 24/12sem aula
seg 28/12sem aula
ter 29/12sem aula
qui 31/12sem aula
seg 4/113-15Prát. 5Dúvidas sobre relações; Minicurso de Python; calculando mdc de forma ingênua; dicionário; Motivação de mdc; encriptação por multiplicaçãoQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Dúvidas sobre relações), Chat 1, Vídeo 2 (Minicurso de Python; calculando mdc de forma ingênua; dicionário), Chat 2, Vídeo 3 (Motivação de mdc; encriptação por multiplicação), Chat 3
ter 5/18-10Teór. 8Algoritmo de Euclides, terminação e corretude; Motivação para o teorema de Bézout (divisão em mundo cíclico)Quadro (Jamboard), Quadro (PDF), Vídeo 1 (Algoritmo de Euclides, terminação e corretude), Chat 1, Vídeo 2 (Motivação para o teorema de Bézout (divisão em mundo cíclico)), Chat 2
qui 7/18-10Teór. 9Teorema de Bézout; ideia e lemas para a prova; Algoritmo Estendido de Euclides; Terminação, Corretude e Implementação do Algoritmo Estendido de EuclidesQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Teorema de Bézout; ideia e lemas para a prova), Chat 1, Vídeo 2 (Algoritmo Estendido de Euclides), Chat 2, Vídeo 3 (Terminação, Corretude e Implementação do Algoritmo Estendido de Euclides)
seg 11/113-15Prát. 6Recapitulação do Teorema de Bézout e Algoritmo Estendido de Euclides; Aplicação do Teorema de Bézout; (c|a e c|b) sse c|mdc(a,b)); Resolução da Q1 da Prova 1 de 2019.2; Discussão da Lista 4Quadro (Jamboard) Quadro (PDF) Código (algoritmo estendido de euclides) Vídeo 1 (Recapitulação do Teorema de Bézout e Algoritmo Estendido de Euclides) Chat 1 Vídeo 2 (Aplicação do Teorema de Bézout; (c|a e c|b) sse c|mdc(a,b)) Chat 2 Vídeo 3 (Resolução da Q1 da Prova 1 de 2019.2; Discussão da Lista 4) Chat 3
ter 12/18-10Teór. 10Teorema Fundamental da Aritmética; Algoritmo para encontrar o menor fator de um natural; Algoritmo para encontrar todos os fatores primos de um naturalQuadro (Jamboard) Quadro (PDF) Vídeo (Teorema Fundamental da Aritmética; Algoritmo para encontrar o menor fator de um natural; Algoritmo para encontrar todos os fatores primos de um natural) Chat
qui 14/18-10Teór. 11TFA (existência); Propriedade Fundamental dos Primos; Implementação do algoritmo de fatoração em primos; TFA (unicidade)Quadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (TFA (existência); Propriedade Fundamental dos Primos), Chat 1, Vídeo 2 (Implementação do algoritmo de fatoração em primos), Chat 2, Vídeo 3 (TFA (unicidade)), Chat 3
seg 18/113-15Prát. 7Dúvidas das listas 4 e 5; Algoritmo de Fatoração de FermatQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Dúvidas das listas 4 e 5), Chat 1, Vídeo 2 (Algoritmo de Fatoração de Fermat), Chat 2
ter 19/18-10Teór. 12Corretude do Algoritmo de Fatoração de Fermat; Crivo de EratóstenesQuadro (Jamboard), Quadro (PDF), Vídeo 1 (Corretude do Algoritmo de Fatoração de Fermat), Chat 1, Vídeo 2 (Crivo de Eratóstenes), Chat 2
qui 21/18-10Teór. 13Implementação do crivo de Eratóstenes; Infinitude dos primosQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Implementação do crivo de Eratóstenes), Chat 1, Vídeo 2 (Infinitude dos primos), Chat 2
seg 25/113-15Prát. 8Dúvidas da Lista 5; Recursão; Torres de HanóiQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Dúvidas da Lista 5), Chat 1, Vídeo 2 (Recursão; Torres de Hanói), Chat 2
ter 26/18-10Teór. 14Recap de recursão e Hanoi; Princípio da Indução Finita (“Forte” e “Fraca”); Análise do Algoritmo das Torres de Hanói (Terminação e Corretude)Quadro (Jamboard), Quadro (PDF), Vídeo 1 (Recap de recursão e Hanoi; Princípio da Indução Finita (“Forte” e “Fraca”)), Chat 1, Vídeo 2 (Análise do Algoritmo das Torres de Hanói (Terminação e Corretude)), Chat 2
qui 28/18-10Teór. 15Análise de Hanói; Análise de Fibonacci (fórmula de Binet); Cobrindo tabuleiros quadriculados por indução/recursãoQuadro (Jamboard), Quadro (PDF), Vídeo 1 (Análise de Hanói), Chat 1, Vídeo 2 (Análise de Fibonacci (fórmula de Binet)), Chat 2, Vídeo 3 (Cobrindo tabuleiros quadriculados por indução/recursão), Chat 3
seg 1/213-15Prát. 9Dúvida da Lista 6; discussões sobre o calendário; Os inteiros módulo n (Z_n); A aritmética modular (soma, subtração, multiplicação, divisão em Z_n)Quadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Dúvida da Lista 6; discussões sobre o calendário), Chat 1, Vídeo 2 (Os inteiros módulo n (Z_n)), Chat 2, Vídeo 3 (A aritmética modular (soma, subtração, multiplicação, divisão em Z_n)), Chat 3
ter 2/28-10Teór. 16Exponenciação em aritmética modular; Divisão em aritmética modular; Teorema da Inversão; Pequeno Teorema de FermatQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Exponenciação em aritmética modular), Chat 1, Vídeo 2 (Divisão em aritmética modular; Teorema da Inversão), Chat 2, Vídeo 3 (Pequeno Teorema de Fermat), Chat 3
qui 4/28-10Teór. 17Provas do PTF(1) e PTF(2); Teste de primalidade de Fermat; Pseudoprimos de Fermat; Números de CarmichaelQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Provas do PTF(1) e PTF(2)), Chat 1, Vídeo 2 (Teste de primalidade de Fermat), Chat 2, Vídeo 3 (Pseudoprimos de Fermat; Números de Carmichael), Chat 3
seg 8/213-15Prát. 10Dúvidas das Listas 7 e 8; Números de Carmichael; Teorema de Korselt; Teste de Miller–Rabin (intuição)Quadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Dúvidas das Listas 7 e 8), Chat 1, Vídeo 2 (Números de Carmichael; Teorema de Korselt), Chat 2, Vídeo 3 (Teste de Miller–Rabin (intuição)), Chat 3
ter 9/28-10Teór. 18Teste de Miller–Rabin (implementação e exemplos); Teste de Miller–Rabin (análise e comentários)Quadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Teste de Miller–Rabin (implementação e exemplos)), Chat 1, Vídeo 2 (Teste de Miller–Rabin (análise e comentários)), Chat 2
qui 11/28-10Teór. 19Avisos e esclarecimentos sobre o fim do período; Recapitulação de aritmética modular; RSAQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Avisos e esclarecimentos sobre o fim do período), Chat 1, Vídeo 2 (Recapitulação de aritmética modular), Chat 2, Vídeo 3 (RSA), Chat 3
seg 15/2sem aula
ter 16/2sem aula
qui 18/28-10Teór. 20Dúvidas e comentários da Lista 8 e Trabalho Final; RSA (recapitulação e exemplo); Comentários sobre a segurança do RSAQuadro (Jamboard), Quadro (PDF), Código, Vídeo 1 (Dúvidas e comentários da Lista 8 e Trabalho Final), Chat 1, Vídeo 2 (RSA (recapitulação e exemplo)), Chat 2, Vídeo 3 (Comentários sobre a segurança do RSA), Chat 3
seg 22/213-15Dúv. 1Dúvidas (Teste de Miller–Rabin, Trabalho Final)Quadro (Jamboard), Quadro (PDF), Vídeo (Dúvidas (Teste de Miller–Rabin, Trabalho Final)), Chat
ter 23/28-10sem aula
qui 25/29-10Dúv. 2Dúvidas do Trabalho FinalQuadro (Jamboard), Quadro (PDF), Código, Vídeo (Dúvidas do Trabalho Final), Chat
seg 1/314-15Dúv. 3Dúvidas do Trabalho FinalQuadro (Jamboard), Quadro (PDF), Vídeo (Dúvidas do Trabalho Final), Chat
ter 2/38-10sem aula
qui 4/39-10FinalAtividade Final com RSA

Método de avaliação

Diversas listas de exercícios e (pelo menos) um trabalho de maior porte. As listas contarão 70% da nota final. Os monitores farão a correção das listas, sob supervisão e responsabilidade do professor.