Números Inteiros e Criptografia (20-1)

Professor: Hugo Nobrega
Monitores: Caio Monteiro, Gabriele Cavalcanti, Leonardo Santiago e Markson Arguello
Grupo de discussões no Telegram: https://t.me/joinchat/NCZpYFRTp9ZXtThc8ftKZQ
Plantão de monitoria: Quartas-feiras, 13:00–15:00 (sala anunciada pelo Telegram)
Pasta do Google Drive com vídeos de aula e demais arquivos: https://drive.google.com/drive/folders/1tQQY57Q9PcZXelJwe20LFegFxzCDpA-Q (solicite permissão para um dos professores por email ou Telegram, indicando seu nome completo e DRE)

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

Lista	Data Limite de Entrega
Lista 1	11 de dezembro às 18:00
Lista 2	18 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 6	29 de janeiro às 18:00
Lista 7	5 de fevereiro às 18:00
Lista 8	19 de fevereiro às 18:00
Trabalho Final	3/3 às 18:00

Cronograma planejado/registro de atividades

Data	Horário	Aula	Conteúdo	Links
seg 30/11	13-15	Prát. 1	Apresentaçã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/12	8-10	Teór. 1	Teoremas, provas, conectivos, tabelas de verdade	Quadro (Jamboard) Quadro (PDF) Vídeo (Teoremas, provas, conectivos, tabelas de verdade) Chat
qui 3/12	8-10	Teór. 2	Contraexemplos, algumas estratégias de prova (prova por casos, contrapositiva), tautologia; Quantificadores para todo e existe	Quadro (Jamboard) Quadro (PDF) Vídeo (Contraexemplos, algumas estratégias de prova (prova por casos, contrapositiva), tautologia; Quantificadores para todo e existe) Chat
seg 7/12	13-15	Prát. 2	Dú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/12	8-10	Teór. 3	Conjuntos, união, interseção, diferença, subconjuntos, conjunto das partes	Quadro (Jamboard) Quadro (PDF) Vídeo (Conjuntos, união, interseção, diferença, subconjuntos, conjunto das partes) Chat
qui 10/12	8-10	Teór. 4	Quantificadores relativizados, Vacuidade; Relações, representação gráfica ou em tabela, propriedades de relações	Quadro (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/12	13-15	Prát. 3	Dú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/12	8-10	Teór. 5	Propriedades de relações; ordens parciais; relações de equivalência	Quadro (Jamboard), Quadro (PDF), Vídeo (Propriedades de relações; ordens parciais; relações de equivalência), Chat
qui 17/12	8-10	Teór. 6	Exemplo 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ão	Quadro (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/12	13-15	Prát. 4	Dúvidas das listas 2 e 3; Minicurso de Python: while; implementação do algoritmo ingênuo de divisão	Quadro (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/12	8-10	Teór. 7	Terminação e Corretude do Alg. Ingênuo da Divisão; Relação de divisibilidade; mdc; números primos e coprimos	Quadro (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/12			sem aula
seg 28/12			sem aula
ter 29/12			sem aula
qui 31/12			sem aula
seg 4/1	13-15	Prát. 5	Dúvidas sobre relações; Minicurso de Python; calculando mdc de forma ingênua; dicionário; Motivação de mdc; encriptação por multiplicação	Quadro (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/1	8-10	Teór. 8	Algoritmo 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/1	8-10	Teór. 9	Teorema de Bézout; ideia e lemas para a prova; Algoritmo Estendido de Euclides; Terminação, Corretude e Implementação do Algoritmo Estendido de Euclides	Quadro (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/1	13-15	Prát. 6	Recapitulaçã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 4	Quadro (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/1	8-10	Teór. 10	Teorema Fundamental da Aritmética; Algoritmo para encontrar o menor fator de um natural; Algoritmo para encontrar todos os fatores primos de um natural	Quadro (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/1	8-10	Teór. 11	TFA (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/1	13-15	Prát. 7	Dúvidas das listas 4 e 5; Algoritmo de Fatoração de Fermat	Quadro (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/1	8-10	Teór. 12	Corretude do Algoritmo de Fatoração de Fermat; Crivo de Eratóstenes	Quadro (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/1	8-10	Teór. 13	Implementação do crivo de Eratóstenes; Infinitude dos primos	Quadro (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/1	13-15	Prát. 8	Dúvidas da Lista 5; Recursão; Torres de Hanói	Quadro (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/1	8-10	Teór. 14	Recap 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/1	8-10	Teór. 15	Análise de Hanói; Análise de Fibonacci (fórmula de Binet); Cobrindo tabuleiros quadriculados por indução/recursão	Quadro (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/2	13-15	Prát. 9	Dú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/2	8-10	Teór. 16	Exponenciação em aritmética modular; Divisão em aritmética modular; Teorema da Inversão; Pequeno Teorema de Fermat	Quadro (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/2	8-10	Teór. 17	Provas do PTF(1) e PTF(2); Teste de primalidade de Fermat; Pseudoprimos de Fermat; Números de Carmichael	Quadro (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/2	13-15	Prát. 10	Dú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/2	8-10	Teór. 18	Teste 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/2	8-10	Teór. 19	Avisos e esclarecimentos sobre o fim do período; Recapitulação de aritmética modular; RSA	Quadro (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/2			sem aula
ter 16/2			sem aula
qui 18/2	8-10	Teór. 20	Dúvidas e comentários da Lista 8 e Trabalho Final; RSA (recapitulação e exemplo); Comentários sobre a segurança do RSA	Quadro (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/2	13-15	Dúv. 1	Dúvidas (Teste de Miller–Rabin, Trabalho Final)	Quadro (Jamboard), Quadro (PDF), Vídeo (Dúvidas (Teste de Miller–Rabin, Trabalho Final)), Chat
ter 23/2	8-10		sem aula
qui 25/2	9-10	Dúv. 2	Dúvidas do Trabalho Final	Quadro (Jamboard), Quadro (PDF), Código, Vídeo (Dúvidas do Trabalho Final), Chat
seg 1/3	14-15	Dúv. 3	Dúvidas do Trabalho Final	Quadro (Jamboard), Quadro (PDF), Vídeo (Dúvidas do Trabalho Final), Chat
ter 2/3	8-10		sem aula
qui 4/3	9-10	Final	Atividade 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.