Teoria dos Números e Criptografia

Código:

M242

Sigla:

M242

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

Ocorrência: 2013/2014 - 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	2	Plano de Estudos a partir de 2008	3	-	7,5	-
L:B	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:CC	1	Plano de estudos de 2008 até 2013/14	3	-	7,5	-
L:F	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:G	0	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	42	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 os 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)

M141 Álgebra Linear I

M142 Álgebra Linear II

CC101 Introdução à Programação

Programa

1) Divisibilidade em anéis comutativos, com especial ênfase no anel dos inteiros e em anéis de polinómios sobre um corpo; números primos e números compostos; o máximo divisor comum e o algoritmo de Euclides em alguns anéis (ditos) Euclidianos mais comuns. O teorema fundamental da Aritmética e a sua extensão a alguns anéis aritmeticamente importantes.

2) Congruências. Os teoremas de Fermat e Euler. Inversos modulares. Teorema chinês dos restos.

3) A cifra RSA e algumas das suas aplicações. Exponenciação modular rápida. 

4) Rudimentos sobre testes de primalidade e algoritmos de factorização de números inteiros.

5) Raízes primitivas e o protocolo para distribuição de chaves Diffie-Hellman.

6) Resíduos quadráticos. Lei de reciprocidade quadrática. Protocolo para "atirar uma moeda ao ar à distância" (remote coin flip protocol). Teste de Pépin para números de Fermat.

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)
Ireland Kenneth; A classical introduction to modern number theory. ISBN: 0-387-90625-8

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)

Métodos de ensino e atividades de aprendizagem

Aulas de exposição dos conceitos e resultados, com exemplos diversos, e aulas de resolução de exercícios.

Software

PARI: http://pari.math.u-bordeaux.fr

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	60,00
Participação presencial	0,00
Teste	40,00
Total:	100,00

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

Haverão dois testes, que decorrerão nas aulas práticas, em datas a anunciar, tendo cada um a duração de uma hora.

Cada teste terá um peso de 4 valores na nota final, podendo as respectivas classificações ser usadas, independentemente, como créditos no exame final, que terá 3 partes, duas das quais correspondendo aos testes.

A classificação final será a obtida no exame final.