Números Inteiros e Criptografia (26-1)

Funcionamento da disciplina

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

As aulas serão realizadas em modalidade presencial, com aulas às quartas e sextas de 8:00 às 10:00 na sala F3-08 do CCMN.

Bibliografia

Listas de Exercícios

Lista Data Limite de Entrega
Lista 1 23 de setembro às 18:00
Lista 2 5 9 de outubro às 18:00 (nova data)
Lista 3 14 de outubro às 7:59
Lista 4 1º de dezembro às 18:00

Provas de Períodos Anteriores

Regras de colaboração

Cronograma planejado/registro de atividades

Data Aula Conteúdo Material
qua 12 ago 0 Apresentação da Disciplina; atividade de descriptação de mensagem secreta Vídeo (sem imagem); Sem quadro (projetor com defeito)
sex 14 ago 01 Discussão sobre a atividade de encriptação e descriptação; O propósito da disciplina (formalização, abstração) Vídeo; Quadro
qua 19 ago 02 Discussão sobre os conceitos de Teorema, Conjectura, Prova, Definição (sem vídeo nem quadros)
sex 21 ago 03 Continuação da discussão: Contraexemplo, Algoritmo; O Algoritmo Ingênuo da Divisão (AID); Prova da terminação e corretude (ideia) do AID Vídeo; Quadro; Código (AID)
qua 26 ago 04 Prova da corretude do AID; prova da Unicidade no Teorema da Divisão; recap. da motivação para mdc: criptografia por “cifra multiplicativa”; mdc - definição e primeiras propriedades Vídeo; Quadro; Código (encriptação)
sex 28 ago 05 Mais propriedades de divisibilidade e mdc; algoritmo ingênuo de mdc; ideia do Algoritmo de Euclides Vídeo; Quadro; Código (mdc ingênuo)
qua 2 set 06 Algoritmo de Euclides (enunciado, terminação, corretude); Teorema de Bézout (enunciado e ideia da prova – Algoritmo Estendido de Euclides) Vídeo; Quadro; Código (Euclides)
sex 4 set 07 Algoritmo Estendido de Euclides (enunciado, terminação, corretude, implementação) Vídeo; Quadro; Código (Euclides Estendido)
qua 9 set 08 Recursão e indução: discussão inicial (“quando funciona??”) Vídeo; Quadro; Código (implementando algumas das funções)
sex 11 set 09 Recursão: discussão mais formal dos critérios de “quando fuciona”; exemplos de “agendamentos” de definições recursivas; exemplo das Torres de Hanói Vídeo; Quadro;
qua 16 set 10 Hanói: implementação. Indução: “provas escritas por recursão”. Primeiros exemplos Vídeo; Quadro; Código (Hanói)
sex 18 set 11 Exemplos de provas por indução Vídeo; Quadro; Código (exemplo)
qua 23 set sem aula Paralisação Estudantil -
sex 25 set 12 Mais exemplos de provas por indução (incluindo terminação + corretude de Hanói); Teorema Fundamental da Aritmética (enunciado e discussão) Vídeo; Quadro
qua 30 set 13 Prova da “Existência” no TFA: o algoritmo ingênuo da fatoração (AIF); terminação e corretude do AIF Vídeo; Quadro; Código (Fatoração Ingênua)
sex 2 out 14 Prova da “Unicidade” no TFA; propriedade fundamental dos primos Vídeo; Quadro
qua 7 out sem aula 15ª SIAc
sex 9 out sem aula 15ª SIAc
qua 14 out 15 Revisão para Prova 1 Vídeo; Quadro
sex 16 out 16 Infinitude dos primos; relações de equivalência; a relação de equivalência módulo n Vídeo; Quadro
qua 21 out 17 Classes de equivalência, quociente de universo por rel. de equivalência; Inteiros módulo n; Aritmética modular: adição e multiplicação Vídeo; Quadro
sex 23 out P1 Prova 1
qua 28 out 18 Mais aritmética modular: subtração, divisão, elevação de classe de equivalência a um inteiro Vídeo; Quadro
sex 30 out sem aula Feriado
qua 4 nov 19 Mais exploração de potências modulares; Pequeno Teorema de Fermat (dois enunciados, ideia da prova) Vídeo; Quadro
sex 6 nov 20 Prova do PTF; teste primalidade de Fermat; números de Carmichael Vídeo; Quadro; Código (Teste de Fermat)
qua 11 nov 21 Mais exemplos de Fermat e contas em aritmética modular; a ideia do Teste de Miller–Rabin Vídeo; Quadro; Código (Teste de Primalidade “Ingênuo”)
sex 13 nov 22 Teste de Miller–Rabin Vídeo; Quadro; Código (Teste de Miller–Rabin)
qua 18 nov 23 “Radiciação” (extração de raízes) em aritmética modular; a base do RSA Vídeo; Quadro
sex 20 nov sem aula Feriado
qua 25 nov
sex 27 nov
qua 2 dez
sex 4 dez
qua 9 dez
sex 11 dez
qua 16 dez
sex 18 dez

Método de avaliação