Números Inteiros e Criptografia (2020.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

ListaFundo claroFundo escuroData Limite para Entrega
Lista 1ClaroEscuro12 de abril às 18:00
Lista 2ClaroEscuro19 de abril às 18:00
Lista 3ClaroEscuro30 de abril às 18:00
Lista 4ClaroEscuro7 de maio às 18:00
Lista 5ClaroEscuro17 de maio às 18:00
Lista 6ClaroEscuro27 de maio às 18:00
Trabalho FinalClaroEscuro10 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

DataHorárioAulaConteúdoLinks
seg 22 marsem aula (JICTAC 2020)
ter 23 marsem aula (JICTAC 2020)
qui 25 marsem aula (JICTAC 2020)
seg 29 mar13-15P 01Parte 1: Apresentação da disciplina; Parte 2: Teoremas e provasQuadro (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 mar8-10T 01Parte 1: Tipos de teoremas, conjecturas, provas; Parte 2: A linguagem da matemática, conectivos, tabelas de verdadeQuadro (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 abr8-10T 02Parte 1: Mais tabelas de verdade e estratégias de prova; Parte 2: Quantificadores para todo e existe, estratégias de provaQuadro (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 abr13-15P 02Parte 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 abr8-10T 03Parte 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 abr8-10T 04Parte 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 tabelaQuadro (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 abr13-15P 03Parte 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 abr8-10T 05Parte 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 AIDQuadro (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 abr8-10T 06Parte 1: Terminação e Corretude do AID; Unicidade de quociente e resto; Parte 2: Divisibilidade, primos, mdcQuadro (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 abr13-15P 04Parte 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 whileQuadro (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 abr8-10T 07Parte 1: Motivação do mdc (cifra multiplicativa); Parte 2: Algoritmo ingênuo do mdc; Algoritmo de EuclidesQuadro (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 abr8-10T 08Parte 1: Implementação do Algoritmo de Euclides; Parte 2: Terminação e Corretude do Algoritmo de EuclidesQuadro (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 abr13-15P 05Parte 1: Anúncios sobre listas, dúvidas da Lista 3; Parte 2: Minicurso de Python; Laços sequenciais (for), range, listas, stringsQuadro (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 abr8-10T 09Parte 1: Teorema de Bézout; Algoritmo Estendido de Euclides; Parte 2: Implementação do AEEQuadro (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 abr8-10T 10Parte 1: (c | a & c | b) sse c | mdc(a,b); Parte 2: Teorema Fundamental da Aritmética (enunciado); Parte 3: Algoritmo para Menor FatorQuadro (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 mai13-15P 06Parte 1: Algoritmo de fatoração em primos; Parte 2: Propriedade Fundamental dos PrimosQuadro (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 mai8-10T 11Parte 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 mai8-10T 12Parte 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 mai13-15P 07Parte 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 mai8-10T 13Parte 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 mai8-10T 14Parte 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óiQuadro (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 mai13-15P 08Parte 1: Exemplos de provas por indução; Parte 2: Quantidade de movimentos em Hanói; reanalisando reticências em provas antigasQuadro (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 mai8-10T 15Parte 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 mai8-10T 16Parte 1: Exponenciação com expoente natural (multiplicação repetida) em Z_n; Parte 2: Divisão em Z_n; Parte 3: Pequeno Teorema de FermatQuadro (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 mai13-15P 09Parte 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–RabinQuadro (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 mai8-10T 17Parte 1: Anúncios sobre calendário e Trabalho Final; Parte 2: Teste de Miller–Rabin; Algoritmo, comentário e implementaçãoQuadro (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 mai8-10T 18Parte 1: Breve revisão de aritmética modular; Parte 2: RSAQuadro (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 mai13-15P 10Parte 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 RSAQuadro (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 jun8-10T 19sem aula
qui 3 junsem aula
seg 7 jun13-15P 11Dúvidas do Trabalho FinalQuadro (Jamboard), Quadro (PDF), Código, Vídeo (com LIBRAS e chat), Vídeo (apenas quadro e professor), Chat
ter 8 jun8-10T 20sem aula
qui 10 jun8-10T 21Atividade 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.