Números Inteiros e Criptografia (19-2)

Bibliografia

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

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.

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