Teoria de Números e Aplicações

Código:

M3015

Sigla:

M3015

Nível:

300

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

Ocorrência: 2017/2018 - 1S

Ativa?	Sim
Unidade Responsável:	Departamento de Matemática
Curso/CE Responsável:	Licenciatura em Biologia

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	0	Plano de Estudos Oficial	3	-	6	56	162
L:CC	1	Plano de estudos a partir de 2014	2	-	6	56	162
			3
L:F	0	Plano de Estudos Oficial	2	-	6	56	162
			3
L:G	1	Plano estudos a partir do ano letivo 2017/18	3	-	6	56	162
L:M	47	Plano de Estudos Oficial	2	-	6	56	162
			3
L:Q	1	Plano estudos a partir do ano letivo 2016/17	3	-	6	56	162

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)

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-Helmann
    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, 2017 (Texto a disponibilizar aos estudantes)

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)
Ireland Kenneth; A classical introduction to modern number theory. ISBN: 0-387-90625-8
Shoup Victor; A computational introduction to number theory and algebra. ISBN: 0-521-85154-8 (Disponível gratuitamente em http://www.shoup.net/ntb)

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.
Existirá um horário regular de atendimento para apoio e esclarecimento de dúvidas.
Serão disponibilizadas 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 (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 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.