Number Theory and Cryptography

Code:

M242

Acronym:

M242

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2015/2016 - 2S

Active?	Yes
Responsible unit:	Department of Mathematics
Course/CS Responsible:	Bachelor in Mathematics

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
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	-

Teaching language

Suitable for English-speaking students

Objectives

To introduce the basic concepts and results of Number Theory, together with some of its computational aspects. To give some of its cryptographical applications. 

Learning outcomes and competences

To know the basic concepts and results of Number Theory, as well as some of its computational aspects and some of its cryptographical applications. 

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Álgebra Linear

Introdução à Programação

Program

[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.

Mandatory literature

Shoup Victor; A computational introduction to number theory and algebra. ISBN: 0-521-85154-8

Complementary Bibliography

Vinogradov I. M.; Elements of number theory. ISBN: 0-486-60259-1
Menezes Alfred J.; Handbook of applied cryptography. ISBN: 0-8493-8523-7
Endler O.; Teoria dos Números Algébricos
Ireland Kenneth; A classical introduction to modern number theory. ISBN: 0-387-90625-8

Teaching methods and learning activities

1. Lectures: presentation of the course material and of examples by the teacher; solution of exercises by the students with the advice of the teacher.
2. Regular office hours for student advice and clarification of doubts.
3. Besides the bibliography list, slides of the lecture notes are published online.

Software

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

keywords

Physical sciences > Mathematics > Number theory

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	100,00
Total:	100,00

Eligibility for exams

Course registration is the only requirement.

Calculation formula of final grade

There will a number N of optional midterm sets of exercises, of which count the N-1 best classified. The exercises will take place in the TP classes, on dates to be announced.

The final exam consists of two parts, the first corresponding to the sets of exercises, with weight three quarters. The remaining quarter is the weight of the second part. At the student option, for the classification of the first part it may be used the classification obtained through the sets of exercises.

The classification obtained through the sets of exercises can not be used in the remaining exams.

Special assessment (TE, DA, ...)

Any type of special student evaluation may take one of the following forms: exclusively an oral examination; an oral examination plus a written examination, the student being required to pass both of them; only a written examination. The option for one of them is of sole responsibility of the professors in charge of the course unit.

Classification improvement

For students approved in 2014/2015, grade improvement can be attempted only through examination.

Observations

Article 13 of General Regulations for Student Evaluation at the levels of First Cycle, Integrated Masters, and Second Cycle at U.Porto, approved on May 19, 2010 (cf. http://www.fc.up.pt/fcup/documentos/documentos.php?ap=3&ano=2011): "Fraud committed during an exam, in any form, implies the annulment of the exam and the communication to the statutorily competent organ for possible disciplinary action."