Números Inteiros e Criptografia (2019.1)

  • 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.

ListaCapítulo do livro-textoExercíciosData limite para entrega
Lista 1Cap. 1, pág. 321 (apenas itens (2) e (3)), 3, 4, 74 de abril às 8:00.
Lista 2Cap. 2, pág. 482, 3, 7, 9, 1015 de abril às 13:00.
Lista 3Cap. 3, pág. 663, 4, 5, 6, 725 de abril às 8:00.
Lista 4Cap. 4, pág. 851, 3, 4, 62 de maio às 8:00.
Lista 5Cap. 5, pág. 1001 (apenas itens (3) e (4)), 3, 5, 1013 de maio às 13:00.
Lista 6Cap. 6, pág. 1155, 7 + Enunciar & provar teoremas de terminação e corretude para o Teste de Miller–Rabin27 de maio às 13:00.
Lista 7Cap. 7Lista 73 de junho às 13:00.
Lista 8Caps. 8–11Lista 827 de junho às 8:00.

Cronograma e histórico de aulas

DataAtividadeLivro-texto
11 de marçosem aula
12 de marçosem aula
14 de marçosem aula
18 de marçoLab: Introdução. Código visto em sala.
19 de marçoRevisão ens. médio. Exercícios.
21 de marçoTeoremas e algoritmos; divisão0.7 a 1.2
25 de marçoLab: Breve introdução ao Python; implementação do algoritmo ingênuo de divisão. Extra: Cifra polialfabética (Gabriel)
26 de marçoDivisão (cont.) e mdc; Algoritmo (básico) de Euclides1.3 a 1.5
28 de marçoAlgoritmo Estendido de Euclides1.5 e 1.6
1 de abrilLab: Algoritmo Estendido de Euclides
2 de abrilAlgoritmo (ingênuo) para fatoração em números primos2.1, 2.2 e 2.6
4 de abrilAlgoritmo de Fermat; unicidade da fatoração em números primos2.3 a 2.5, 2.8
8 de abrilLab: Fatoração única
9 de abrilaula cancelada devido às chuvas
11 de abrilUnicidade da fatoração em números primos (replay); infinidade dos primos; crivo de Eratóstenes2.8, 3.5, 3.6
15 de abrilLab: Crivo de Eratóstenes.
16 de abrilRelações de equivalência e de congruência; inteiros módulo $n$; aritmética modular4.1, 4.2, 4.3
18 de abrilAritmé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 abrilsem aula
23 de abrilsem aula
25 de abrilRecursão e Indução
29 de abrilLab: recursão e indução; Torre de Hanói
30 de abrilIndução (cont.) e Pequeno Teorema de Fermat
2 de maioPequeno Teorema de Fermat (cont.), Teste de Fermat e números de Carmichael
6 de maioLab: Teste de Fermat e números de Carmichael; Código visto em sala
7 de maioTeste de Miller–Rabin
9 de maioRevisão para a P1
13 de maioProva 1 (primeira parte) NA SALA F3.014
14 de maioProva 1 (segunda parte) NA SALA F3.014
16 de maioTeste de Miller–Rabin (cont.); sistemas de congruências
20 de maioLab: discussão da P1
21 de maiosem aula
23 de maioTeorema chinês dos restos
27 de maioLab: Teste de Miller–Rabin; Teorema chinês dos restos
28 de maioGrupos: introdução, o grupo U(n) e a função totiente de Euler
30 de maiosem aula (paralisação da educação)
3 de junhoLab: Função totiente de Euler
4 de junhoGrupos cíclicos; Subgrupos; Teorema de Lagrange
6 de junhoTeorema 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 junhoLab: aplicações do Teorema de Euler
11 de junhoTeorema da Raiz Primitiva (cont.)
13 de junhoCriptografia RSA (Cap. 11)
17 de junhoLab: RSA
18 de junhosem aula
20 de junhosem aula
24 de junhoLab: revisão para P2
25 de junhoProva 2 (1a parte)
27 de junhoProva 2 (2a parte)
1 de julhoLab: Discussão da P2
2 de julhoProva final (1a parte)
4 de julhoProva final (2a parte)
8 de julhoLab: a definir
9 de julhoProva final (2a ch.) (1a parte)
11 de julhoProva 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

A segunda chamada só é direito para casos devidamente justificados dentro do prazo de 48 horas.

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.