Teoria dos Números e Criptografia

Código:

M242

Sigla:

M242

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

Ocorrência: 2015/2016 - 2S

Ativa?	Sim
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:AST	0	Plano de Estudos a partir de 2008	3	-	7,5	-
L:B	2	Plano de estudos a partir de 2008	3	-	7,5	-
L:F	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:G	1	P.E - estudantes com 1ª matricula anterior a 09/10	3	-	7,5	-
		P.E - estudantes com 1ª matricula em 09/10	3	-	7,5	-
L:M	37	Plano de estudos a partir de 2009	1	-	7,5	-
			2
			3
L:Q	0	Plano de estudos Oficial	3	-	7,5	-

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

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

Resultados de aprendizagem e competências

Conhecer os conceitos e resultados básicos de Teoria dos Números, assim como alguns dos seus aspectos computacionais e algumas das suas aplicações criptográficas.

Modo de trabalho

Presencial

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

Álgebra Linear

Introdução à Programação

Programa

[0.] Introdução/motivação
Uma breve introdução ao GAP.
A cifra RSA (rudimentos).

[I.] Noções básicas.
Princípio da Boa Ordenação / Indução.
Algoritmo da divisão.
Números primos e números compostos.
Teorema Fundamental da Aritmética.

[II.] Congruências.
Introdução à aritmética modular; aplicações.
Teoremas de Fermat e de Euler.
Números de Fermat e números de Mersenne.
Exponenciação Modular.
Teorema Chinês dos Restos.

[III.] Rudimentos sobre testes de primalidade e algoritmos de factorização.
Considerações sobre a distribuição dos números primos.
Pseudo-primos de Fermat.
Números de Carmichael.
Pseudo-primos fortes e testemunhas.
Método de factorização de Fermat.

[IV.] Algoritmo de Euclides e aplicações.
Algoritmo de Euclides.
Algoritmo estendido de Euclides / Identidade de Bézout.
Inversos modulares.

[V.] Raízes primitivas.
Raízes primitivas módulo um inteiro.
Aplicação: Protocolo de troca de chaves de Diffie-Hellman.

[VI.] Resíduos quadráticos.
Símbolo de Legendre.
O carácter quadrático de 2.
Lei da reciprocidade quadrática.
Aplicações.

[VIII.] Criptografia.
Mais considerações sobre testes de primalidade e algoritmos de factorização.
O sistema criptográfico RSA.
Considerações sobre outros sistemas criptográficos.

Bibliografia Obrigatória

Shoup Victor; A computational introduction to number theory and algebra. ISBN: 0-521-85154-8 (Disponível gratuitamente em http://www.shoup.net/ntb)

Bibliografia Complementar

Vinogradov I. M.; Elements of number theory. ISBN: 0-486-60259-1
Menezes Alfred J.; Handbook of applied cryptography. ISBN: 0-8493-8523-7 (Disponível gratuitamente em http://www.cacr.math.uwaterloo.ca/hac)
Endler O.; Teoria dos Números Algébricos
Ireland Kenneth; A classical introduction to modern number theory. ISBN: 0-387-90625-8

Métodos de ensino e atividades de aprendizagem

1. Aulas (teóricas e teórico-práticas): exposição da matéria e apresentação de exemplos pelo docente; resolução de exercícios pelos estudantes com apoio do docente.
2. Horário regular de atendimento para apoio e esclarecimento de dúvidas.
3. Além da bibliografia indicada, são disponibilizados online slides com notas das aulas.

Software

GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra

Palavras Chave

Ciências Físicas > Matemática > Teoria dos números

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	100,00
Total:	100,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

Ao longo do semestre (nas aulas TP, em datas a anunciar) serão realizados N conjuntos de exercícios. Aquele em que o estudante obtiver a classificação mais baixa não conta para efeito da sua classificação final: a classificação correspondente aos exercícios é a soma das classificações obtidas nos N-1 conjuntos de exercícios mais bem classificados. A classificação correspondente aos exercícios pode ser usada no exame, nos termos descritos a seguir.

O exame final consiste de duas partes, correspondendo a primeira aos conjuntos de exercícios e podendo, por solicitação do estudante, ser classificada com a classificação correspondente aos exercícios. Tem a cotação de 15 valores. A segunda parte tem a cotação de 5 valores.

Em épocas subsequentes (época de recurso, incluindo melhoria de nota, ou época especial) não é dada a possibilidade de usar a classificação correspondente aos exercícios.

 

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

Qualquer tipo de avaliação especial poderá revestir uma das seguintes formas: exclusivamente uma prova oral; uma prova oral e uma prova escrita, ambas com caráter eliminatório; somente uma prova escrita. A opção por uma das alternativas compete exclusivamente aos docentes responsáveis pela unidade curricular.

Melhoria de classificação

Para quem tenha obtido aprovação no ano letivo de 2014/2015, a melhoria de nota pode ser tentada exclusivamente através de exame.

Observações

Artigo 13º do Regulamento Geral para Avaliação dos Discentes de Primeiros Ciclos, de Ciclos de Estudos Integrados de Mestrado e de Segundos Ciclos da U.Porto, aprovado em 19 de Maio de 2010 (cf. http://www.fc.up.pt/fcup/documentos/documentos.php?ap=3&ano=2011): "A fraude cometida na realização de uma prova, em qualquer das suas modalidades, implica a anulação da mesma e a comunicação ao órgão estatutariamente competente para eventual processo disciplinar."