Number Theory and Cryptography

Code:

M242

Acronym:

M242

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2012/2013 - 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	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	46	Plano de estudos a partir de 2009	1	-	7,5	-
			2
			3
L:Q	0	Plano de estudos Oficial	3	-	7,5	-
PGMP	0	PE da PG em Matemática para Professores	1	-	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

Program

1) Divisibility in commutative rings, with special emphasis in the ring of integers and in rings of polynomials over a field; prime and composite numbers; the greatest common divisor and the Euclidean algorithm in some of the most common and simple Euclidean rings. The fundamental theorem of Arithmetic and its extension to some arithmetically important rings.

2) Congurences. The theorems of Fermat and Euler. Modular inverses. The Chinese remainder theorem.

3) The RSA cipher and some of its applications. Fast modular exponentiation. 

4) An introduction to the basics on primality tests and integer factorization algorithms.

5) Primitive roots and the Diffie-Hellman key exchange protocol.

6) Quadratic residues. Quadratic reciprocity law. Remote coin flip protocol. Pépin test for Fermat numbers.

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

Teaching methods and learning activities

Lectures on the concepts and results of the subject matter, with many examples, and exercise solving classes.

Software

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

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	85,00	0,00
Final exam with credits obtained in tests	Exame	3,00	100,00
	Total:	-	100,00

Calculation formula of final grade

There will be two tests, that will take place in the TP classes, on dates to be announced. Each will have a duration of one hour.

Each test has a weight of four points towards the final classification, and these can be used independently as credits in the final exam, which will consist of 3 parts, two of which corresponding to the tests.

The final grade will be the one obtained on the final exam.