Números Inteiros e Criptografia (21-2)

Funcionamento da disciplina

O meio primário de comunicação entre os alunos, monitores e professores será pelo Discord, no grupo listado acima.

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 120 de dezembro às 18:00
Lista 221 de janeiro às 18:00
Lista 331 de janeiro às 18:00
Lista 414 de fevereiro às 18:00
Trabalho Final10 de março à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
ter 16 nov8-10sem aulaSemana de recepção
qui 18 nov8-10sem aulaSemana de recepção
seg 22 nov13-15Aula 0Parte 1: Introdução à disciplina e questões administrativas; Parte 2: Exemplos motivadores (cifra de César e cifra multiplicativa)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
ter 23 nov8-10Aula 01Parte 1: Inversos multiplicativos no mundo circular; Parte 2: Abstração em computação e matemática; expressões e variáveis em pythonQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
qui 25 nov8-10Aula 02Parte 1: Definindo funções em Python; Parte 2: Erros; tipos numéricosQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
seg 29 nov13-15Aula 03Parte 1: Definição de variáveis, atribuições simultâneas, escopo, alias; Parte 2: Tipos numéricos, booleanosQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
ter 30 nov8-10Aula 04Parte 1: Dados Booleanos (True/False); comandos condicionais (if/elif/else); Parte 2: condicional (while) e sequencial (for)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
qui 2 dez8-10Aula 05Parte 1: Recap de while/for; strings; indexação, fatiamento; Parte 2: Mais sobre strings; métodos de strings; cifra de César (início)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
seg 6 dez13-15Aula 06Parte 1: Cifra de César (implementação); Parte 2: Tuplas e listas; mutabilidadeQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
ter 7 dez8-10Aula 07Parte 1: Mais sobre mutabilidade; hasheabilidade; Parte 2: DicionáriosQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
qui 9 dez8-10Aula 08Parte 1: Algoritmos, teoremas e definições em matemática; Parte 2: Provas em matemática; exemplo de uma provaQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
sex 10 dez15-17Monitoria 01Monitoria 01Vídeo, Chat
seg 13 dez13-15Aula 09Parte 1: Dúvidas; Parte 2: Recíproca de um teorema; contrapositiva; Parte 3: Divisibilidade (definição e algumas propriedades)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
ter 14 dez8-10Aula 10Parte 1: Mais sobre divisibilidade; mdc (definição); Parte 2: Algumas propriedades do mdc; algoritmo ingênuo do mdc; algoritmo de Euclides (introdução)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
qui 16 dez8-10Aula 11Parte 1: Algoritmo de Euclides (enunciado completo e implementação); Parte 2: Terminação do algoritmo de Euclides; corretude (ideia)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
sex 17 dez13-15Monitoria 02Monitoria 02Vídeo, Chat
seg 20 dez13-15Aula 12Parte 1: Dúvidas da lista 1; Parte 2: Corretude do Algoritmo de Euclides (ideia novamente)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código
ter 21 dez8-10Aula 13Parte 1: Corretude do Algoritmo de Euclides; Parte 2: Lema para a prova da corretudeQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 23 dez8-10sem aulaRecesso de fim de ano
seg 27 dez13-15sem aulaRecesso de fim de ano
ter 28 dez8-10sem aulaRecesso de fim de ano
qui 30 dez8-10sem aulaRecesso de fim de ano
seg 3 jan13-15Aula 14Parte 1: Recap do conteúdo; Parte 2: Prova do Teorema de Bézout; algoritmo de Euclides estendido (início)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
ter 4 jan8-10Aula 15Parte 1: Enunciado do Algoritmo de Euclides Estendido (AEE); Parte 2: Implementação do AEE; Parte 3: Terminação e Corretude do AEEQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
qui 6 jan8-10Aula 16Parte 1: Estendendo o AEE para números negativos; Parte 2: Números primos e o Teorema Fundamental da Aritmética (TFA, enunciado); Parte 3: Prova de existência no TFA; algoritmo de fatoração em primos (enunciado e implementação)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
seg 10 jan13-15Aula 17Parte 1: Comentários sobre a Lista 2 e sobre as regras de colaboração entre alunos; Parte 2: terminação do algoritmo de fatoração em primos; Parte 3: corretude do algoritmo de fatoração em primosQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
ter 11 jan8-10Aula 18Parte 1: Resolução do exercício L2Q1c; Parte 2: Otimizando a fatoração: o menor fator de um composto é menor ou igual à sua raiz; Parte 3: Comentários sobre a dificuldade do problema da fatoração; Parte 4: Unicidade no TFA (ideia); a Propriedade Fundamental dos Primos (enunciado)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Vídeo 4, Chat 4, Código
qui 13 jan8-10Aula 19Parte 1: Propriedade Fundamental dos Primos (prova); Parte 2: Unicidade no TFA (prova)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
sex 14 jan15-17Monitoria 03Monitoria 03Quadro, Vídeo, Chat
seg 17 jan13-15Aula 20Parte 1: Comentários sobre a Lista 02; Parte 2: Infinitude dos Primos (enunciado); Parte 3: Infinitude dos Primos (prova); Parte 4: Definições recursivas (motivação)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Vídeo 4, Chat 4
ter 18 jan8-10Aula 21Parte 1: Dúvidas da Aula 20, definições recursivas (exemplos e discussão); Parte 2: Definições recursivas (definição oficial); Parte 3: Implementando definições recursivas em programaçãoQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
qui 20 jan8-10sem aulaFeriado
sex 21 jan10-12Monitoria 04Monitoria 04Quadro, Vídeo, Chat
seg 24 jan13-15Aula 22Parte 1: Comentários sobre a Lista 2; Parte 2: Torres de Hanói (definição); Parte 3: Torres de Hanói (algoritmo recursivo); Parte 4: Torres de Hanói (implementação em Python)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Vídeo 4, Chat 4, Código
ter 25 jan8-10Aula 23Parte 1: Dúvidas da Lista 3; Parte 2: O método de prova por indução; exemplo (soma dos naturais até n); Parte 3: Outro exemplo de prova por indução (fórmula de Binet para Fibonacci)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
qui 27 jan8-10Aula 24Parte 1: Recapitulação de indução; Parte 2: Prova de terminação do algoritmo de Hanói; Parte 3: Prova de corretude do algoritmo de Hanói; quantidade de movimentos feitos pelo algoritmoQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
sex 28 jan15-17Monitoria 05Monitoria 05
seg 31 jan13-15Aula 25Parte 1: Dúvidas da Lista 3; Parte 2: Número de passos do algoritmo de Hanói; Parte 3: Relações; reflexividade, simetria, transitividade, relações de equivalênciaQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
ter 1 fev8-10Aula 26Parte 1: Recapitulação de relações; a ‘cara’ das relações de equivalência; Parte 2: Quociente por relação de equivalência; inteiros módulo n; aritmética modular (introdução)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2
qui 3 fev8-10Aula 27Parte 1: Aritmética Modular (adição, subtração, multiplicação); Parte 2: Aritmética Modular (divisão); Parte 3: Aritmética Modular (não há potenciação)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
sex 4 fev15-17Monitoria 06Monitoria 06
seg 7 fev13-15Aula 28Parte 1: Revisão de recursão e indução; Aritmética Modular (elevando uma classe de equivalência a um número natural); exemplos; Parte 2: Mais exemplos de exponenciação modular; Parte 3: Pequeno Teorema de Fermat (motivação e enunciado)Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
ter 8 fev8-10sem aulaAula cancelada
qui 10 fev8-10Aula 29Parte 1: Dúvidas da Lista 4; Parte 2: Equivalência entre PTF1 e PTF2; Parte 3: Prova do PTF1Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
sex 11 fev15-17Monitoria 07Monitoria 07Quadro 1, Quadro 2, Vídeo, Chat
seg 14 fev13-15sem aulaSIAc
ter 15 fev8-10sem aulaSIAc
qui 17 fev8-10Aula 30Parte 1: Aplicação do PTF: cálculo de potências em aritmética modular; Parte 2: Aplicação do PTF: teste de primalidade; Parte 3: Pseudoprimos de Fermat, números de CarmichaelQuadro, Vídeo 1, Vídeo 2, Vídeo 3, Código
sex 18 fev15-17Monitoria 08Monitoria 08
seg 21 fev13-15Aula 31Parte 1: Organização do final da disciplina; Parte 2: Recapitulação de resultados antigos usando a linguagem da aritmética modular; Parte 3: O teste de primalidade de Miller–RabinQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3
ter 22 fev8-10Aula 32Parte 1: Anúncios sobre o trabalho final e monitoria; Parte 2: Implementação e discussão do Teste de Miller–Rabin; Parte 3: A ideia do RSAQuadro, Vídeo 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
qui 24 fev8-10Aula 33Parte 1: Como garantir b**(ed) = b mod pq; Parte 2: RSA; Parte 3: A conversão de textos para números; a escolha dos primos p, qQuadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código
sex 25 fev15-17Monitoria 09Monitoria 09Quadro, Vídeo, Chat
seg 28 fev13-15sem aulaCarnaval
ter 1 mar8-10sem aulaCarnaval
qui 3 mar8-10sem aulaCarnaval
seg 7 mar13-15Aula 34Dúvidas do trabalho finalVídeo, Chat
ter 8 mar8-10Sem aula (a princípio)
qui 10 mar9-10FinalAtividade especial de encerramento

Método de avaliação

Teremos listas de exercícios aproximadamente a cada 10 dias, valendo nota, mas descartaremos as N (a definir) 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).

Não há provas, nem prova final.

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.