Números Inteiros e Criptografia (20-2)

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/stgBiwH5X-sxZjYx

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

Lista Fundo claro Fundo escuro Data Limite para Entrega
Lista 1 Claro Escuro 12 de abril às 18:00
Lista 2 Claro Escuro 19 de abril às 18:00
Lista 3 Claro Escuro 30 de abril às 18:00
Lista 4 Claro Escuro 7 de maio às 18:00
Lista 5 Claro Escuro 17 de maio às 18:00
Lista 6 Claro Escuro 27 de maio às 18:00
Trabalho Final Claro Escuro 10 de junho às 9:00

Regras de colaboração

É permitido (e até recomendado) que vocês 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 a sua solução aberta à sua frente.

Cronograma planejado/registro de atividades

Data Horário Aula Conteúdo Links
seg 22 mar sem aula (JICTAC 2020)
ter 23 mar sem aula (JICTAC 2020)
qui 25 mar sem aula (JICTAC 2020)
seg 29 mar 13-15 P 01 Parte 1: Apresentação da disciplina; Parte 2: Teoremas e provas Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
ter 30 mar 8-10 T 01 Parte 1: Tipos de teoremas, conjecturas, provas; Parte 2: A linguagem da matemática, conectivos, tabelas de verdade Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
qui 1 abr 8-10 T 02 Parte 1: Mais tabelas de verdade e estratégias de prova; Parte 2: Quantificadores para todo e existe, estratégias de prova Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
seg 5 abr 13-15 P 02 Parte 1: Quantificador existe no máximo 1, discussão da lista 1; Parte 2: Minicurso de Python (funções, tipos numéricos, tipo booleano, módulos) Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
ter 6 abr 8-10 T 03 Parte 1: Conjuntos (união, interseção, diferença, vazio, subconjunto, conjunto das partes); Parte 2: Estratégia de prova para quantificador existe único, conjuntos (extensão, compreensão) Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
qui 8 abr 8-10 T 04 Parte 1: Anúncios de lista 1 e monitoria, dúvidas lista 1; Parte 2: Quantificadores relativizados, vacuidade; Parte 3: Relações, representação gráfica e por tabela Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
seg 12 abr 13-15 P 03 Parte 1: Propriedades de relações (reflexiva, simétrica, antissimétrica, transitiva, ordem parcial, relação de equivalência); Parte 2: Exemplo de relação de equivalência (congruência módulo n) Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
ter 13 abr 8-10 T 05 Parte 1: Provas não construtivas para existenciais (princípio das casas dos pombos e dígitos de pi); Parte 2: O conceito de algoritmo, algoritmo ingênuo da divisão (AID); Parte 3: Prova de terminação do AID Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
qui 15 abr 8-10 T 06 Parte 1: Terminação e Corretude do AID; Unicidade de quociente e resto; Parte 2: Divisibilidade, primos, mdc Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
seg 19 abr 13-15 P 04 Parte 1: Dúvidas da Lista 2; Minicurso de Python (atribuição, alias, condicional, laço de repetição condicional while); Parte 2: Implementação do AID em Python; Parte 3: Mais detalhes sobre while Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
ter 20 abr 8-10 T 07 Parte 1: Motivação do mdc (cifra multiplicativa); Parte 2: Algoritmo ingênuo do mdc; Algoritmo de Euclides Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
qui 22 abr 8-10 T 08 Parte 1: Implementação do Algoritmo de Euclides; Parte 2: Terminação e Corretude do Algoritmo de Euclides Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
seg 26 abr 13-15 P 05 Parte 1: Anúncios sobre listas, dúvidas da Lista 3; Parte 2: Minicurso de Python; Laços sequenciais (for), range, listas, strings Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
ter 27 abr 8-10 T 09 Parte 1: Teorema de Bézout; Algoritmo Estendido de Euclides; Parte 2: Implementação do AEE Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
qui 29 abr 8-10 T 10 Parte 1: (c | a & c | b) sse c | mdc(a,b); Parte 2: Teorema Fundamental da Aritmética (enunciado); Parte 3: Algoritmo para Menor Fator Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
seg 3 mai 13-15 P 06 Parte 1: Algoritmo de fatoração em primos; Parte 2: Propriedade Fundamental dos Primos Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
ter 4 mai 8-10 T 11 Parte 1: Unicidade no TFA; Parte 2: A dificuldade de fatorar; Parte 3: Crivo de Eratóstenes (ideia) Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
qui 6 mai 8-10 T 12 Parte 1: Análise do Crivo de Eratóstenes; Parte 2: Infinitude dos Primos; Parte 3: Minicurso de Python (dicionários) Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
seg 10 mai 13-15 P 07 Parte 1: Dicionários em Python; Implementação do Crivo de Eratóstenes; Parte 2: Definições por recursão (ideia) Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
ter 11 mai 8-10 T 13 Parte 1: Recursão; Parte 2: Torres de Hanói (algoritmo e implementação) Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
qui 13 mai 8-10 T 14 Parte 1: Execução de algoritmos recursivos; Ideia de terminação e corretude de Hanói; Parte 2: O método de prova por indução; aplicação à corretude e terminação de Hanói Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
seg 17 mai 13-15 P 08 Parte 1: Exemplos de provas por indução; Parte 2: Quantidade de movimentos em Hanói; reanalisando reticências em provas antigas Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
ter 18 mai 8-10 T 15 Parte 1: Z_n (inteiros módulo n); Parte 2: Aritmética modular (aritmética em Z_n) Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
qui 20 mai 8-10 T 16 Parte 1: Exponenciação com expoente natural (multiplicação repetida) em Z_n; Parte 2: Divisão em Z_n; Parte 3: Pequeno Teorema de Fermat Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
seg 24 mai 13-15 P 09 Parte 1: Prova do PTF1 e PTF2; Parte 2: Teste de primalidade de Fermat; Números de Carmichael; Parte 3: Ideia para o Teste de Miller–Rabin Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
ter 25 mai 8-10 T 17 Parte 1: Anúncios sobre calendário e Trabalho Final; Parte 2: Teste de Miller–Rabin; Algoritmo, comentário e implementação Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
qui 27 mai 8-10 T 18 Parte 1: Breve revisão de aritmética modular; Parte 2: RSA Quadro (Jamboard), Quadro (PDF), Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2
seg 31 mai 13-15 P 10 Parte 1: RSA (recap); Parte 2: Comentários sobre segurança e aspectos práticos do RSA; Parte 3: Exemplo prático de troca de mensagens com RSA Quadro (Jamboard), Quadro (PDF), Código, Vídeo parte 1 (com LIBRAS e chat), Vídeo parte 1 (apenas quadro e professor), Chat 1, Vídeo parte 2 (com LIBRAS e chat), Vídeo parte 2 (apenas quadro e professor), Chat 2, Vídeo parte 3 (com LIBRAS e chat), Vídeo parte 3 (apenas quadro e professor), Chat 3
ter 1 jun 8-10 T 19 sem aula
qui 3 jun sem aula
seg 7 jun 13-15 P 11 Dúvidas do Trabalho Final Quadro (Jamboard), Quadro (PDF), Código, Vídeo (com LIBRAS e chat), Vídeo (apenas quadro e professor), Chat
ter 8 jun 8-10 T 20 sem aula
qui 10 jun 8-10 T 21 Atividade final com RSA

Método de avaliação

Teremos listas de exercícios semanais, 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.