Números Inteiros e Criptografia (20-PLE)

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/NCZpYEYL7OLEe9fmMioJCA

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

As listas de exercícios semanais contarão como 70% da média final.

Lista Data limite para entrega
Lista 1 (atualizada em 27/8) 1o de setembro às 8:00
Lista 2 (atualizada em 3/9) 8 de setembro às 8:00
Lista 3 (atualizada em 10/9) 18 de setembro às 18:00
Lista 4 (atualizada em 24/9) 25 de setembro às 18:00
Lista 5 2 de outubro às 18:00
Lista 6 (atualizada em 5/10, 7/10) 9 de outubro às 18:00
Lista 7 (atualizada em 10/10) 16 de outubro às 18:00
Lista 8 (atualizada em 18/10) 26 de outubro às 18:00
Lista 9 (atualizada em 26/10) 3 de novembro às 18:00
Trabalho Final (atualizado em 3/11, 8/11, 10/11) 16 de novembro às 12:30

Cronograma planejado/registro de atividades

Data Horário Aula Conteúdo Links
24 de ago 13-15 Prática 1 Introdução à disciplina; mini-curso de Python 3 (pt. 1) Vídeo 1 Chat 1 Vídeo 2 Chat 2
25 de ago 8-10 Teórica 1 Teoremas, provas, contraexemplos; linguagem matemática, conectivos Quadro (Jamboard) Quadro (PDF) Vídeo 1 (Teoremas, provas, contraexemplos) Chat 1 Vídeo 2 (Linguagem matemática, conectivos) Chat 2
27 de ago 8-10 Teórica 2 Árvore de uma afirmação, tabela verdade compacta, uso de equivalências para estratégias de prova alternativas; Quantificadores para todo e existe, suas estratégias de prova; Conjuntos e suas propriedades, operações e relações básicas (interseção, união, diferença, estar-contido-em) Quadro (Jamboard) Quadro (PDF) Vídeo 1 (Recap aula T 01, árvore de uma afirmação, tabela verdade compacta, uso de equivalências para estratégias de prova alternativas) Chat 1 Vídeo 2 (Quantificadores para todo e existe, suas estratégias de prova) Chat 2 Vídeo 3 (Conjuntos e suas propriedades, operações e relações básicas (interseção, união, diferença, estar-contido-em)) Chat 3
31 de ago 13-15 Prática 2 Dúvidas da Lista 1; Conjuntos (cont.); subconjuntos; conjunto das partes Quadro (Jamboard) Quadro (PDF) Vídeo 1 (Dúvidas da Lista 1) Chat 1 Vídeo 2 (Conjuntos (cont.); subconjuntos; conjunto das partes) Chat 2
1 de set 8-10 Teórica 3 Relações; diagrama (de Hasse) de uma relação; relação “menor ou igual” para números; mínimo e máximo; prova por casos Quadro (PDF) Vídeo 1 (Relações; diagrama (de Hasse) de uma relação) Chat 1 Vídeo 2 (Relação “menor ou igual” para números; mínimo e máximo; prova por casos) Chat 2 Código (Python Jupyter Notebook)
3 de set 8-10 Teórica 4 Relações - conceitos básicos (par ordenado, produto cartesiano, representações por diagrama e tabela, relação oposta); Propriedades de relações entre dois conjuntos (relação determinística, total, injetiva, sobrejetiva, função, bijeção); Propriedades de relações sobre um conjunto (reflexiva, simétrica, transitiva) Quadro (PDF) Vídeo 1 (Relações - conceitos básicos (par ordenado, produto cartesiano, representações por diagrama e tabela, relação oposta)) Chat 1 Vídeo 2 (Propriedades de relações entre dois conjuntos (relação determinística, total, injetiva, sobrejetiva, função, bijeção)) Chat 2 Vídeo 3 (Propriedades de relações sobre um conjunto (reflexiva, simétrica, transitiva)) Chat 3
7 de set FERIADO
8 de set 8-10 Teórica 5 Propriedades de relações; Recap de algumas estratégias de prova; provas existenciais; princípio da casa dos pombos (prova não construtiva); Conceito de algoritmo; algoritmo para divisão euclidiana e seu teorema de terminação Quadro 1 (Propriedades de relações) (PDF) Quadro 2 (Algoritmos, divisão euclidiana) (Jamboard) Quadro 2 (Algoritmos, divisão euclidiana) (PDF) Vídeo 1 (Propriedades de relações) Chat 1 Vídeo 2 (Recap de algumas estratégias de prova; provas existenciais; princípio da casa dos pombos (prova não construtiva)) Chat 2 Vídeo 3 (Conceito de algoritmo; algoritmo para divisão euclidiana e seu teorema de terminação) Chat 3
10 de set 8-10 Teórica 6 Corretude do alg. ingênuo da divisão; unicidade de quociente e resto; divisibilidade de inteiros; mdc; enunciado do algoritmo de Euclides Quadro (Jamboard) Quadro (PDF) Vídeo 1 (Corretude do alg. ingênuo da divisão; unicidade de quociente e resto) Chat 1 Vídeo 2 (Divisibilidade de inteiros; mdc; enunciado do algoritmo de Euclides) Chat 2
14 de set 13-15 Prática 3 Dúvidas sobre provas e contraexemplos; Continuação do minicurso de Python; implementação dos algoritmos ingênuo de divisão e de Euclides para mdc Quadro (Jamboard) Quadro (PDF) Código Python (Google Colaboratory) Vídeo 1 (Dúvidas sobre provas e contraexemplos) Chat 1 Vídeo 2 (Continuação do minicurso de Python; implementação dos algoritmos ingênuo de divisão e de Euclides para mdc) Chat 2
15 de set 8-10 Teórica 7 Terminação e corretude do Alg. de Euclides; Teorema de Bézout (motivação e enunciado); estratégia para a prova (Algoritmo Estendido de Euclides) Quadro (Jamboard) Quadro (PDF) Vídeo 1 (Terminação e corretude do Alg. de Euclides) Chat 1 Vídeo 2 (Teorema de Bézout (motivação e enunciado); estratégia para a prova (Algoritmo Estendido de Euclides)) Chat 2
17 de set 8-10 Teórica 8 Algoritmo Estendido de Euclides (corretude, terminação, implementação e exemplos); Algoritmo ingênuo de fatoração (encontra menor fator [maior que 1] de um número natural) Quadro pt. 1 (Jamboard) Quadro pt. 1 (PDF) Quadro pt. 2 (PDF) Código (Google Colaboratory) Vídeo 1 (Algoritmo Estendido de Euclides (corretude, terminação, implementação e exemplos)) Chat 1 Vídeo 2 (Algoritmo ingênuo de fatoração (encontra menor fator [maior que 1] de um número natural)) Chat 2
21 de set 13-15 Prática 4 Dúvidas da Lista 3 Quadro (Jamboard) Quadro (PDF) Vídeo (Dúvidas da lista 3) Chat
22 de set 8-10 Teórica 9 Algoritmo de fatoração em primos, eficiência da fatoração; Fatoração única e irracionalidade Quadro (PDF) Código (Google Colaboratory) Vídeo 1 (Algoritmo de fatoração em primos, eficiência da fatoração) Chat 1 Vídeo 2 (Fatoração única e irracionalidade) Chat 2
24 de set 8-10 Teórica 10 Propriedade Fundamental dos Primos, Fatoração única, Primordial Quadro (PDF) Vídeo (Propriedade Fundamental dos Primos, Fatoração única, Primordial) Chat
28 de set 13-15 Prática 5 Dúvidas da lista 4; Minicurso de Python (tuplas, listas, for) Quadro (Jamboard) Quadro (PDF) Código (Google Colaboratory) Vídeo 1 (Dúvidas da lista 4) Chat 1 Vídeo 2 (Minicurso de Python (tuplas, listas, for)) Chat 2
29 de set 8-10 Teórica 11 Revisão Quadro (Jamboard) Quadro (PDF) Vídeo (Revisão) Chat
1 de out 8-10 Teórica 12 Recursão (definições recursivas, Torres de Hanói) Quadro (Jamboard) Quadro (PDF) Código (Google Colaboratory) Vídeo (Recursão (definições recursivas, Torres de Hanói)) Chat
5 de out 13-15 Prática 6 Dúvidas da lista 5; Achar os primos até n Quadro (PDF) Código (Google Colaboratory) Vídeo 1 (Dúvidas da lista 5) Chat 1 Vídeo 2 (Achar os primos até n) Chat 2
6 de out 8-10 Teórica 13 Indução Quadro (PDF) Vídeo 1 Chat 2 Vídeo 2 Chat 1
8 de out 8-10 Teórica 14 Crivo de Eratóstenes (cont.); Indução (cont.); Indução Forte Quadro (PDF) Código - Crivo de Eratóstenes (Google Colaboratory) Vídeo 1 (Crivo de Eratóstenes) Chat 1 Vídeo 2 (Indução) Chat 2 Vídeo 3 (Indução Forte) Chat 3
12 de out FERIADO
13 de out 8-10 Teórica 15 Relações de equivalência; Aritmética modular Quadro (PDF) Vídeo 1 (Relações de equivalência) Chat 1 Vídeo 2 (Aritmética modular) Chat 2
15 de out 8-10 Teórica 16 Aritmética Modular - Operações, Teorema da Inversão, Potências Quadro (PDF) Vídeo 1 (Aritmética Modular - Operações e Teorema da Inversão) Chat 1 Vídeo 2 (Aritmética Modular - Potências) Chat 2
19 de out 13-15 Prática 7 Dúvidas; Potências Quadro (PDF) Código (Google Colaboratory) Vídeo 1 Chat 1 Vídeo 2 Chat 2 Vídeo 3 (Potências) Chat 3
20 de out 8-10 Teórica 17 Pequeno Teorema de Fermat Quadro (PDF) Código (Google Colaboratory) Vídeo 1 Chat 1 Vídeo 2 Chat 2 Vídeo 3 Chat 3
22 de out 8-10 Teórica 18 Teste de Fermat; Testemunhas e Pseudoprimos; Números de Carmichael Quadro (Jamboard) Quadro (PDF) Código (Teste de Fermat; Números de Carmichael (ingênuo)) Vídeo (Teste de Fermat; Testemunhas e Pseudoprimos; Números de Carmichael) Chat
26 de out 13-15 Prática 8 Dúvidas; Prova do PTF por contagem de colares; Minicurso de Python (dicionários & comprehension) Quadro (Jamboard) Quadro (PDF) Código Vídeo 1 (Dúvidas; Prova do PTF por contagem de colares) Chat 1 Vídeo 2 (Minicurso de Python (dicionários & comprehension)) Chat 2
27 de out 8-10 Teórica 19 Teorema de Korselt; Teste de Miller-Rabin Quadro (Jamboard) Quadro (PDF) Código Vídeo 1 (Teorema de Korselt) Chat 1 Vídeo 2 (Teste de Miller-Rabin) Chat 2
29 de out 8-10 Teórica 20 Miller-Rabin; RSA Quadro 1 (Jamboard) Quadro 1 (PDF) Quadro 2 (PDF) Vídeo 1 (Miller-Rabin) Chat 1 Vídeo 2 (RSA) Chat 2
2 de nov FERIADO
3 de nov 8-10 Teórica 21 RSA - Trabalhando com texto; segurança Quadro (PDF) Vídeo 1 (RSA - Trabalhando com texto) Chat 1 Vídeo 2 (RSA - Segurança) Chat 2
5 de nov 8-10 Teórica 22 Troca de chaves Diffie–Hellman Quadro (PDF) Vídeo Chat
9 de nov 13-15 SEM AULA
10 de nov 8-10 Teórica 23 Dúvidas RSA e trabalho; Assinaturas digitais Quadro (Jamboard) Quadro (PDF) Vídeo 1 (Dúvidas RSA e trabalho) Chat 1 Vídeo 2 (Assinaturas digitais) Chat 2
12 de nov 8-10 SEM AULA
16 de novembro 13-15 Prática 9 Atividade final RSA: trocas de mensagens secretas em público; encerramento da disciplina

Método de avaliação

Diversas listas de exercícios e (pelo menos) um trabalho de maior porte. Os monitores são responsáveis pela correção das listas