- Professor: Hugo Nobrega
- Monitores: Lucas Dias e João Pedro Seda (contato via Telegram). Plantão de monitoria às terças (15:00), quando o monitor for o Lucas, ou às sextas (13:00), quando for o João Pedro, no Lab. 1 (dentro do DCC). Os monitores se alternam a cada semana.
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 20% da média final. Teremos uma lista de exercícios para cada capítulo do livro que cobrirmos.
| Lista | Capítulo do livro-texto | Exercícios | Data limite para entrega |
|---|---|---|---|
| Lista 1 | Cap. 1, pág. 32 | 1 (apenas itens (2) e (3)), 3, 4, 7 | 4 de abril às 8:00. |
| Lista 2 | Cap. 2, pág. 48 | 2, 3, 7, 9, 10 | 15 de abril às 13:00. |
| Lista 3 | Cap. 3, pág. 66 | 3, 4, 5, 6, 7 | 25 de abril às 8:00. |
| Lista 4 | Cap. 4, pág. 85 | 1, 3, 4, 6 | 2 de maio às 8:00. |
| Lista 5 | Cap. 5, pág. 100 | 1 (apenas itens (3) e (4)), 3, 5, 10 | 13 de maio às 13:00. |
| Lista 6 | Cap. 6, pág. 115 | 5, 7 + Enunciar & provar teoremas de terminação e corretude para o Teste de Miller–Rabin | 27 de maio às 13:00. |
| Lista 7 | Cap. 7 | Lista 7 | 3 de junho às 13:00. |
| Lista 8 | Caps. 8–11 | Lista 8 | 27 de junho às 8:00. |
Cronograma e histórico de aulas
| Data | Atividade | Livro-texto |
|---|---|---|
| 11 de março | sem aula | |
| 12 de março | sem aula | |
| 14 de março | sem aula | |
| 18 de março | Lab: Introdução. Código visto em sala. | |
| 19 de março | Revisão ens. médio. Exercícios. | |
| 21 de março | Teoremas e algoritmos; divisão | 0.7 a 1.2 |
| 25 de março | Lab: Breve introdução ao Python_; implementação do algoritmo ingênuo de divisão. Extra:_ Cifra polialfabética (Gabriel) | |
| 26 de março | Divisão (cont.) e mdc; Algoritmo (básico) de Euclides | 1.3 a 1.5 |
| 28 de março | Algoritmo Estendido de Euclides | 1.5 e 1.6 |
| 1 de abril | Lab: Algoritmo Estendido de Euclides | |
| 2 de abril | Algoritmo (ingênuo) para fatoração em números primos | 2.1, 2.2 e 2.6 |
| 4 de abril | Algoritmo de Fermat; unicidade da fatoração em números primos | 2.3 a 2.5, 2.8 |
| 8 de abril | Lab: Fatoração única | |
| 9 de abril | aula cancelada devido às chuvas | |
| 11 de abril | Unicidade da fatoração em números primos (replay); infinidade dos primos; crivo de Eratóstenes | 2.8, 3.5, 3.6 |
| 15 de abril | Lab: Crivo de Eratóstenes. | |
| 16 de abril | Relações de equivalência e de congruência; inteiros módulo \(n\); aritmética modular | 4.1, 4.2, 4.3 |
| 18 de abril | Aritmética modular (cont.); aplicações: restos de divisões de potências de inteiros (enormes) por inteiros (pequenos) e equações lineares em \(\mathbb{Z}\_n\) | 4.3, 4.5, 4.7 |
| 22 de abril | sem aula | |
| 23 de abril | sem aula | |
| 25 de abril | Recursão e Indução | |
| 29 de abril | Lab: recursão e indução; Torre de Hanói | |
| 30 de abril | Indução (cont.) e Pequeno Teorema de Fermat | |
| 2 de maio | Pequeno Teorema de Fermat (cont.), Teste de Fermat e números de Carmichael | |
| 6 de maio | Lab: Teste de Fermat e números de Carmichael; Código visto em sala | |
| 7 de maio | Teste de Miller–Rabin | |
| 9 de maio | Revisão para a P1 | |
| 13 de maio | Prova 1 (primeira parte) NA SALA F3.014 | |
| 14 de maio | Prova 1 (segunda parte) NA SALA F3.014 | |
| 16 de maio | Teste de Miller–Rabin (cont.); sistemas de congruências | |
| 20 de maio | Lab: discussão da P1 | |
| 21 de maio | sem aula | |
| 23 de maio | Teorema chinês dos restos | |
| 27 de maio | Lab: Teste de Miller–Rabin; Teorema chinês dos restos | |
| 28 de maio | Grupos: introdução, o grupo U(n) e a função totiente de Euler | |
| 30 de maio | sem aula (paralisação da educação) | |
| 3 de junho | Lab: Função totiente de Euler | |
| 4 de junho | Grupos cíclicos; Subgrupos; Teorema de Lagrange | |
| 6 de junho | Teorema de Lagrange (cont.); Teorema de Euler; “Lema chave” (Seção 9.1); Teorema da Raiz Primitiva (Seções 10.4 e 10.5) | |
| 10 de junho | Lab: aplicações do Teorema de Euler | |
| 11 de junho | Teorema da Raiz Primitiva (cont.) | |
| 13 de junho | Criptografia RSA (Cap. 11) | |
| 17 de junho | Lab: RSA | |
| 18 de junho | sem aula | |
| 20 de junho | sem aula | |
| 24 de junho | Lab: revisão para P2 | |
| 25 de junho | Prova 2 (1a parte) | |
| 27 de junho | Prova 2 (2a parte) | |
| 1 de julho | Lab: Discussão da P2 | |
| 2 de julho | Prova final (1a parte) | |
| 4 de julho | Prova final (2a parte) | |
| 8 de julho | Lab: a definir | |
| 9 de julho | Prova final (2a ch.) (1a parte) | |
| 11 de julho | Prova final (2a ch.) (2a parte) |
Método de avaliação
Duas provas, \(P1\) e \(P2\), 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 simples das notas das duas provas. 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 \geq 7\), então aprovado. Se \(M < 3\), então reprovado. Se \(3 \leq M < 7\), então o aluno vai para a prova final, \(PF\). Neste caso, se a média aritmética simples entre \(M\) e \(PF\) for \(\geq 5\), aprovado; caso contrário, reprovado.
Segunda chamada
Caso o aluno precise fazer segunda chamada da \(P1\) ou da \(P2\), a \(PF\) servirá como segunda chamada; neste caso, se a média \(M\) obtida satisfizer \(3 \leq M < 7\), o aluno faz a prova \(PF_2\). Caso o aluno faça \(P1\) e \(P2\) mas precise faltar a \(PF\), então a sua prova final será a prova \(PF_2\).
Se a média aritmética simples entre \(M\) e \(PF_2\) for \(\geq 5\), aprovado; caso contrário, reprovado.