Number Theory and Applications

Code:

M3015

Acronym:

M3015

Level:

300

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2016/2017 - 2S

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

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:B	0	Official Study Plan	3	-	6	56	162
L:M	29	Official Study Plan	2	-	6	56	162
			3
L:Q	0	study plan from 2016/17	3	-	6	56	162

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)

Basic notions of Linear Algebra and Programming
Álgebra Linear

Program

">[0] Introduction / motivation
">A brief introduction to  GAP.

">The RSA cipher.

">[I.] Basic notions.
">Division algorithm.
">Prime numbers and composite numbers.

">The Fundamental Theorem of Arithmetic.

">[II.] Congruences.
Introduction to modular arithmetic; ">applications.
">Theorems of Fermat and Euler.
">Fermat numbers and Mersenne numbers.
">Modular exponentiation.

">Chinese remainder theorem.

">[III.] Basics on primality tests and factorization algorithms.
">Considerations on the distribution of primes.
">Fermat pseudo-primes.
">Carmichael numbers.
">Strong pseudo-primes and witnesses.

">Fermat's factorization method.

">[IV.] Euclidean algorithm and applications.
">Euclidean algorithm.
">Extended Euclidean algorithm / Bézout identity.

">Modular inverses.

">[V.] Primitive roots.
">Primitive root modulus an integer.

">Application: the Diffie-Hellman key exchange protocol.

">[VI.] Quadratic Residues.
">Legendre symbol.
">The quadratic reciprocity law.

">Applications.

">[VIII.] Further applications.">
">The RSA cryptosystem.
Considerations on other cryptographic systems.

Mandatory literature

Shoup Victor; A computational introduction to number theory and algebra. ISBN: 0-521-85154-8
Manuel Delgado e António Machiavelo; Teoria dos números - uma introdução com aplicações, 2016

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

Presentation of the course material and of examples by the teacher; solution of exercises by the students with the advice of the teacher.
There will be regular office hours for student advice and clarification of doubts.
Lecture notes will be made availlable.

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 takes the form of written examination.

Classification improvement

Grade improvement can be attempted only through examination.