Teoria de Números e Criptografia

Código:

M3032

Sigla:

M3032

Áreas Científicas
Classificação	Área Científica
OFICIAL	Matemática

Ocorrência: 2023/2024 - 2S

Ativa?	Sim
Página Web:	https://moodle2324.up.pt/course/view.php?id=2086
Unidade Responsável:	Departamento de Matemática
Curso/CE Responsável:	Licenciatura em Matemática

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:B	2	Plano de Estudos Oficial	3	-	6	48	162
L:CC	8	Plano estudos a partir do ano letivo 2021/22	2	-	6	48	162
			3
L:F	0	Plano de Estudos Oficial	3	-	6	48	162
L:G	0	Plano estudos a partir do ano letivo 2017/18	2	-	6	48	162
			3
L:M	64	Plano de Estudos Oficial	2	-	6	48	162
			3
L:MA	0	Plano de Estudos Oficial	3	-	6	48	162
L:Q	0	Plano estudos a partir do ano letivo 2016/17	3	-	6	48	162

Língua de trabalho

Português - Suitable for English-speaking students
Obs.: Poderá ser feito em inglês o esclarecimento de dúvidas de estudantes que não dominem o português.

Objetivos

Introduzir conceitos e resultados básicos de Teoria dos Números e alguns dos seus aspetos computacionais. Dar algumas das suas aplicações criptográficas.

Resultados de aprendizagem e competências

Ao completar esta unidade curricular, o estudante deve conhecer os conceitos e resultados básicos de Teoria dos Números, assim como alguns dos seus aspetos computacionais e algumas das suas aplicações criptográficas.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Noções básicas de Álgebra Linear e de Programação

Programa

1 Divisibilidade
  O algoritmo de divisão
  Máximo Divisor Comum
  Algoritmo (estendido) de Euclides
  Números Primos e números compostos
  Teorema Fundamental da Aritmética

2 Aritmética modular
  Congruências
  Aplicações básicas das congruências
    Critérios de divisibilidade
    Cálculo de restos
    Deteção de erros em sistemas de identificação
  Inversos modulares
  Pequeno Teorema de Fermat
  O anel dos inteiros módulo m
  Teorema chinês dos restos
  Teorema de Euler
  Sistema Criptográfico RSA
  Números de Mersenne e números de Fermat

3 Teoria dos Números Computacional
  Exponenciação modular
  Testes de primalidade
    Teste de Fermat
    Pseudo-primos fortes e testemunhas
  Números de Carmichael
  Algoritmos de fatorização
    "Trial division"
    Método de Fatorização de Fermat
    Método p-1 de Pollard
  O Sistema Criptográfico RSA (de novo)
    Criação de uma chave RSA
    Assinaturas digitais usando o RSA

4 Raízes primitivas e aplicações
  Raízes primitivas
    Existência de raízes primitivas
    Critério de Korselt (para números de Carmichael)
    Problema do logaritmo discreto
  Aplicações
    Protocolo de Diffie-Hellmann
    Cifra de ElGamal
    Protocolos de conhecimento nulo

5 Reciprocidade quadrática
  Resíduos quadráticos e reciprocidade
    Símbolo de Legendre
    Lei da reciprocidade quadrática
    Símbolo de Jacobi
Congruências quadráticas
  Aplicações
    Protocolo para “lançar a moeda ao ar”
    Provas de conhecimento nulo
    Um teste de primalidade

Bibliografia Obrigatória

Manuel Delgado e António Machiavelo; Teoria dos números - uma introdução com aplicações (Notas a disponibilizar na página da UC)

Bibliografia Complementar

William Stein; Elementary Number Theory: Primes, Congruences, and Secrets , Springer, 2009
Kenneth Ireland; A classical introduction to modern number theory. ISBN: 0-387-90625-8
Alfred J. Menezes; Handbook of applied cryptography. ISBN: 0-8493-8523-7
Victor Shoup; A computational introduction to number theory and algebra. ISBN: 0-521-85154-8

Métodos de ensino e atividades de aprendizagem

Exposição da matéria e apresentação de exemplos pelo docente; resolução de exercícios pelos estudantes com apoio do docente.

Software

GAP (https://www.gap-system.org/)
Sage (https://www.sagemath.org/)

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	100,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	114,00
Frequência das aulas	48,00
Total:	162,00

Obtenção de frequência

A única condição para obtenção de frequência é a inscrição na unidade curricular.

Fórmula de cálculo da classificação final

Nas aulas teórico-práticas serão realizados quatro conjuntos de exercícios, em datas a anunciar.
Os primeiros três conjuntos de exercícios têm a cotação de 3 valores cada e contribuem para a classificação os dois mais bem classificados.
O quarto conjunto de exercícios tem a cotação de 5 valores.

As classificações obtidas nos exercícios podem ser usadas no exame, nos termos descritos abaixo.

A aprovação à unidade curricular é obtida no exame final.

O exame final terá  partes.
A primeira corresponde aos primeiros conjuntos de exercícios e é cotada para 6 valores.
A segunda corresponde ao quarto conjunto de exercícios e é cotada para 5 valores.
O estudante poderá optar por não resolver uma ou ambas dessas partes do exame, ficando atribuída a cada parte não resolvida a classificação obtida pelo estudante no teste correspondente.
A terceira parte do exame tem a cotação de 9 valores.

Avaliação especial (TE, DA, ...)

Qualquer avaliação especial é feita sob a forma de exame.

Melhoria de classificação

Melhoria de classificação pode ser tentada apenas através de exame.