Números Inteiros e Criptografia (2019.2)

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

    ListaCapítulo do livroExercíciosData limite para entrega
    Lista 1Cap. 1, p. 321(1), 1(3), 3, 4, 75 de setembro às 8:00
    Lista 2Cap. 2, p. 482, 3, 7, 9, 1019 de setembro às 8:00
    Lista 3Cap. 3, p. 663, 4, 5, 6, 726 de setembro às 8:00
    Lista 4Caps. 4 & 5Cap 4: 1, 6, 10; Cap 5: 9, 12, 1510 de outubro às 8:00
    Lista 5Cap. 63, 5, 7 + Enunciar e provar os teoremas de corretude e terminação para o Teste de Miller-Rabin29 de outubro às 8:00
    Lista 6Cap. 7Lista 612 de novembro às 8:00
    Lista 7Caps. 8 & 9Lista 728 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 2019.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

DataLocalAtividadeLivro
5 de agosem aula (semana de recepção)
6 de agosem aula (semana de recepção)
8 de agosem aula (semana de recepção)
12 de agoLEP1Aula 1: Introdução. Cifra aditiva, cifra multiplicativa, análise das chaves que funcionam para cifra multiplicativa.
13 de agoF3-014Aula 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 agoF3-014Aula 3: Teoremas e Demonstrações; Algoritmos§0.7, §1.1
19 de agoLEP1Lab 1: Introdução a Python 3; Código visto em sala
20 de agoF3-014Aula 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 agoF3-014Aula 5: Algoritmo euclideano e algoritmo euclideano estendido); Identidade de BézoutCap. 1
26 de agosem aula (Semana da Computação)
27 de agosem aula (Semana da Computação)
29 de agosem aula (Semana da Computação)
2 de setLEP1Lab 2: Euclides; Código visto em salaCap. 1
3 de setF3-014Aula 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 setF3-014Aula 7: Fatoração por Fermat; Teorema da Fatoração Única (início da prova da unicidade)§§2.4, 2.8
9 de setLEP1Lab 3: Fatoração; Código visto em salaCap. 2
10 de setF3-014Aula 8: Teorema da Fatoração Única: prova da unicidade; Infinidade dos Primos; Crivo de Eratóstenes§§2.8, 3.5, 3.6
12 de setF3-014Aula 9: Crivo de Eratóstenes (recap.); Relações e algumas de suas possíveis propriedades (reflexividade, simetria, transitividade)§§3.6, 4.1
16 de setLEP1Lab 4: Crivo de Eratóstenes; Código visto em salaCap. 3
17 de setF3-014Aula 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 setF3-014Aula 11: Revisão para P1Caps. 1–3
23 de setLEP1Lab 5: Revisão para P1
24 de setF3-014PROVA 1Caps. 1–3
26 de setF3-014Aula 12: Aritmética modularCap. 4
30 de setLEP1Lab 6: Discussão da P1
1 de outF3-014Aula 13: Aritmética modular (recap.); o conjunto U(n) dos elementos inversíveis módulo n; Pequeno Teorema de FermatCaps. 4 e 5
3 de outF3-014sem aula
7 de outLEP1sem aulaCaps. 4 e 5
8 de outF3-014Aula 14: PTF (recap.); teste de Fermat; números de CarmichaelCap. 6
10 de outF3-014Aula 15: Números de Carmichael - Teorema de KorseltCap. 6
14 de outLEP1Lab 7: Teste de Fermat, Números de CarmichaelCap. 6
15 de outF3-014Aula 16: Teste de Miller-RabinCap. 6
17 de outF3-014Aula 17: Teste de Miller-Rabin (recap.); Teorema Chinês dos Restos (intro)Cap. 7
21 de outsem aula (Semana de Integração Acadêmica)
22 de outsem aula (Semana de Integração Acadêmica)
24 de outsem aula (Semana de Integração Acadêmica)
28 de outsem aula (feriado)
29 de outF3-014Aula 18: Teorema Chinês dos RestosCap. 7
31 de outF3-014Aula 19: Revisão para P2Caps. 4–7
4 de novLEP1Lab 9: Teste de Miller-Rabin + Teorema Chinês dos RestosCaps. 6 & 7
5 de novF3-014PROVA 2Caps. 4–7
7 de novF3-014Aula 20: Grupos (introdução e exemplos)Cap. 8
11 de novLEP1Lab 10: Discussão da P2
12 de novF3-014Aula 21: Exemplo de grupo: grupo livre gerado por n elementos; função de EulerCap. 8
14 de novF3-014Aula 22: Subgrupo das potências de um elemento qualquer em um grupo finitoCap. 8
18 de novLEP1Lab 11: Função de EulerCap. 8
19 de novF3-014Aula 23: Subgrupo das potências (recap); Teorema de Lagrange?
21 de novF3-014Aula 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 novLEP1Aula 25: Teorema da Raiz Primitiva§§ 10.5 e 10.6
26 de novF3-014Aula 26: RSA§§ 11.1–11.6
28 de novF3-014Aula 27: Aceleração de descriptação no RSA com o Teo Chinês dos Restos?
2 de dezLEP1Lab 13: RSA?
3 de dezF3-014Aula 27: Revisão para P3?
5 de dezF3-014PROVA 3?
9 de dezLEP1Lab 14: Discussão da P3?
10 de dezF3-014PROVA 4?
12 de dezF3-014SEGUNDA 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 ≥ 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.

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