- Professor: Hugo Nobrega
- Monitores: Gustavo Aquino, Luan Martins e Thierry Dutoit
- Grupo de discussões no Telegram: https://t.me/joinchat/NCZpYBW_5ZIBooftRw0eMg
- Plantão de monitoria: Quartas-feiras de 15:00 a 17:00 no LAB3 (DCC)
Bibliografia
- Livro-texto: S. C. Coutinho, Números Inteiros e Criptografia RSA, Segunda Edição, Coleção Matemática e Aplicações, IMPA, 2014.
- Leitura complementar: L. M. Schechter, Uma Introdução à Criptografia de Chave Pública Através do Método El Gamal, Notas em Matemática Aplicada, Volume 77, SBMAC, 2014. Disponível gratuitamente na internet
Listas de exercícios
As listas de exercícios e (algumas) atividades de laboratório contarão como ??% da média final. Teremos (em média) uma lista de exercícios para cada capítulo do livro que cobrirmos.
| Lista | Capítulo do livro | Exercícios | Data limite para entrega |
|---|---|---|---|
| Lista 1 | Cap. 1, p. 32 | 1(1), 1(3), 3, 4, 7 | 5 de setembro às 8:00 |
| Lista 2 | Cap. 2, p. 48 | 2, 3, 7, 9, 10 | 19 de setembro às 8:00 |
| Lista 3 | Cap. 3, p. 66 | 3, 4, 5, 6, 7 | 26 de setembro às 8:00 |
| Lista 4 | Caps. 4 & 5 | Cap 4: 1, 6, 10; Cap 5: 9, 12, 15 | 10 de outubro às 8:00 |
| Lista 5 | Cap. 6 | 3, 5, 7 + Enunciar e provar os teoremas de corretude e terminação para o Teste de Miller-Rabin | 29 de outubro às 8:00 |
| Lista 6 | Cap. 7 | Lista 6 | 12 de novembro às 8:00 |
| Lista 7 | Caps. 8 & 9 | Lista 7 | 28 de novembro às 8:00 |
Para resolver a questão 12 do capítulo 5, você pode (e deve) usar o seguinte Teorema da §5.4 que nós não vimos em sala.
Teorema (p. 97): Se \(p\) é um número primo, então para um polinômio da forma
\(f(x) = x\)\(k\) ${} + \bar{a}$\(\scriptstyle k-1\)$ \,⋅\, x$\(\scriptstyle k-1\) ${} + \bar{a}$\(\scriptstyle k-2\)$ \,⋅\, x$\(\scriptstyle k-2\) ${} + ⋯ $ ${} + \bar{a}$\(\scriptstyle 2\)$ \,⋅\, x$\(\scriptstyle 2\) ${} + \bar{a}$\(\scriptstyle 1\)$ \,⋅\, x$ ${} + \bar{a}$\(\scriptstyle 0\)
a equação \(f(x) = \bar{0}\) possui no máximo \(k\) soluções distintas em \(\mathbb{Z}_p\).
Provas de 19-1
Correções de erros do livro-texto
Capítulo 1
- Na questão 7 da §1.7 (p. 33), onde se lê
α·a + β·b = 1, o correto éα·a' + β·b' = 1
Cronograma planejado e histórico de aulas
| Data | Local | Atividade | Livro |
|---|---|---|---|
| 5 de ago | – | sem aula (semana de recepção) | – |
| 6 de ago | – | sem aula (semana de recepção) | – |
| 8 de ago | – | sem aula (semana de recepção) | – |
| 12 de ago | LEP1 | Aula 1: Introdução. Cifra aditiva, cifra multiplicativa, análise das chaves que funcionam para cifra multiplicativa. | – |
| 13 de ago | F3-014 | Aula 2: Revisão de assuntos do Ensino Médio. Exponenciação de inteiros, produtos notáveis, binômio de Newton, PA, PG. Lista de exercícios para praticar. | – |
| 15 de ago | F3-014 | Aula 3: Teoremas e Demonstrações; Algoritmos | §0.7, §1.1 |
| 19 de ago | LEP1 | Lab 1: Introdução a Python 3; Código visto em sala | – |
| 20 de ago | F3-014 | Aula 4: Algoritmo (ingênuo) de divisão, teoremas de terminação e corretude; MDC, algoritmo de Euclides (apenas enunciado) | §§1.1 – 1.4 |
| 22 de ago | F3-014 | Aula 5: Algoritmo euclideano e algoritmo euclideano estendido); Identidade de Bézout | Cap. 1 |
| 26 de ago | – | sem aula (Semana da Computação) | – |
| 27 de ago | – | sem aula (Semana da Computação) | – |
| 29 de ago | – | sem aula (Semana da Computação) | – |
| 2 de set | LEP1 | Lab 2: Euclides; Código visto em sala | Cap. 1 |
| 3 de set | F3-014 | Aula 6: Teorema da Fatoração Única (enunciado); prova da “existência” via algoritmo; propriedade fundamental dos primos | §§2.1–2.3, 2.6 |
| 5 de set | F3-014 | Aula 7: Fatoração por Fermat; Teorema da Fatoração Única (início da prova da unicidade) | §§2.4, 2.8 |
| 9 de set | LEP1 | Lab 3: Fatoração; Código visto em sala | Cap. 2 |
| 10 de set | F3-014 | Aula 8: Teorema da Fatoração Única: prova da unicidade; Infinidade dos Primos; Crivo de Eratóstenes | §§2.8, 3.5, 3.6 |
| 12 de set | F3-014 | Aula 9: Crivo de Eratóstenes (recap.); Relações e algumas de suas possíveis propriedades (reflexividade, simetria, transitividade) | §§3.6, 4.1 |
| 16 de set | LEP1 | Lab 4: Crivo de Eratóstenes; Código visto em sala | Cap. 3 |
| 17 de set | F3-014 | Aula 10: Relações de equivalência, classes de equivalência, quociente de um conjunto por uma relação de equivalência; Inteiros módulo n; Congruências; Aritmética modular (introd.) | §§4.1–4.3 |
| 19 de set | F3-014 | Aula 11: Revisão para P1 | Caps. 1–3 |
| 23 de set | LEP1 | Lab 5: Revisão para P1 | – |
| 24 de set | F3-014 | PROVA 1 | Caps. 1–3 |
| 26 de set | F3-014 | Aula 12: Aritmética modular | Cap. 4 |
| 30 de set | LEP1 | Lab 6: Discussão da P1 | – |
| 1 de out | F3-014 | Aula 13: Aritmética modular (recap.); o conjunto U(n) dos elementos inversíveis módulo n; Pequeno Teorema de Fermat | Caps. 4 e 5 |
| 3 de out | F3-014 | sem aula | – |
| 7 de out | LEP1 | sem aula | Caps. 4 e 5 |
| 8 de out | F3-014 | Aula 14: PTF (recap.); teste de Fermat; números de Carmichael | Cap. 6 |
| 10 de out | F3-014 | Aula 15: Números de Carmichael - Teorema de Korselt | Cap. 6 |
| 14 de out | LEP1 | Lab 7: Teste de Fermat, Números de Carmichael | Cap. 6 |
| 15 de out | F3-014 | Aula 16: Teste de Miller-Rabin | Cap. 6 |
| 17 de out | F3-014 | Aula 17: Teste de Miller-Rabin (recap.); Teorema Chinês dos Restos (intro) | Cap. 7 |
| 21 de out | – | sem aula (Semana de Integração Acadêmica) | – |
| 22 de out | – | sem aula (Semana de Integração Acadêmica) | – |
| 24 de out | – | sem aula (Semana de Integração Acadêmica) | – |
| 28 de out | – | sem aula (feriado) | – |
| 29 de out | F3-014 | Aula 18: Teorema Chinês dos Restos | Cap. 7 |
| 31 de out | F3-014 | Aula 19: Revisão para P2 | Caps. 4–7 |
| 4 de nov | LEP1 | Lab 9: Teste de Miller-Rabin + Teorema Chinês dos Restos | Caps. 6 & 7 |
| 5 de nov | F3-014 | PROVA 2 | Caps. 4–7 |
| 7 de nov | F3-014 | Aula 20: Grupos (introdução e exemplos) | Cap. 8 |
| 11 de nov | LEP1 | Lab 10: Discussão da P2 | – |
| 12 de nov | F3-014 | Aula 21: Exemplo de grupo: grupo livre gerado por n elementos; função de Euler | Cap. 8 |
| 14 de nov | F3-014 | Aula 22: Subgrupo das potências de um elemento qualquer em um grupo finito | Cap. 8 |
| 18 de nov | LEP1 | Lab 11: Função de Euler | Cap. 8 |
| 19 de nov | F3-014 | Aula 23: Subgrupo das potências (recap); Teorema de Lagrange | ? |
| 21 de nov | F3-014 | Aula 24: Aplicações do Teorema de Lagrange: Teorema de Euler, Lema Chave, Lemas para o Teorema da Raiz Primitiva | §§ 8.7, 9.1, 10.4 |
| 25 de nov | LEP1 | Aula 25: Teorema da Raiz Primitiva | §§ 10.5 e 10.6 |
| 26 de nov | F3-014 | Aula 26: RSA | §§ 11.1–11.6 |
| 28 de nov | F3-014 | Aula 27: Aceleração de descriptação no RSA com o Teo Chinês dos Restos | ? |
| 2 de dez | LEP1 | Lab 13: RSA | ? |
| 3 de dez | F3-014 | Aula 27: Revisão para P3 | ? |
| 5 de dez | F3-014 | PROVA 3 | ? |
| 9 de dez | LEP1 | Lab 14: Discussão da P3 | ? |
| 10 de dez | F3-014 | PROVA 4 | ? |
| 12 de dez | F3-014 | SEGUNDA CHAMADA? | ? |
Método de avaliação
4 provas e diversas listas de exercícios. Os monitores são responsáveis pela correção das listas.
A média teórica \(M_T\) é a média aritmética entre a nota da \(P_4\) e as duas melhores notas das provas \(P_1\), \(P_2\) e \(P_3\). A média prática \(M_P\) é a média aritmética simples das \(n\) melhores listas de exercícios (a definir). A média parcial \(M\) é a média ponderada entre \(M_T\) (peso 4) e \(M_P\) (peso 1). Se \(M \ge 5\), então aprovado. Se \(M < 5\), então reprovado.
Caso o aluno precise fazer segunda chamada, essa prova substitui a nota da prova perdida.