Number Theory and Applications

Code:

M3015

Acronym:

M3015

Level:

300

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2017/2018 - 1S

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:CC	1	Plano de estudos a partir de 2014	2	-	6	56	162
			3
L:F	0	Official Study Plan	2	-	6	56	162
			3
L:G	1	study plan from 2017/18	3	-	6	56	162
L:M	47	Official Study Plan	2	-	6	56	162
			3
L:Q	1	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

1 Divisibility
  Division algorithm
  Greatest Common Divisor
  Euclidean Algorithm (extended)
  Prime numbers and composite numbers
  The Fundamental Theorem of Arithmetic

2 Modular Arithmetic
  Congruences
  Basic applications of congruences
    Divisibility criteria
    Remainder computation
    Error detection in identification systems
  Modular inverses
  Fermat's little theorem
  The ring of the integers modulo m
  Chinese remainder theorem
  Euler's theorem
  The RSA cryptosystem
  Fermat numbers and Mersenne numbers

3 Computational number theory
  Modular exponentiation
  Primality tests
    Fermat's test
    Strong pseudo-primes and witnesses
Carmichael numbers
  Factorization algorithms
    Trial division
    Fermat's factorization method
    Pollard's p-1 method
  The RSA cryptosystem (again)
    Creating an RSA key
    Digital signatures using RSA

4 Primitive roots and applications
  Primitive roots
    Existence of primitive roots
    Korselt criterion (for Carmichael numbers)
    The discrete Logarithm problem
  Applications
    Diffie-Helmann's protocol
    ElGamal cipher
    Zero knowledge protocol

5 Quadratic reciprocity
  Quadratic residues and reciprocity
    Legendre's symbol
    The quadratic reciprocity law
    Jacobi's symbol
Quadratic congruences
  Applications
    The flip-coin protocol
    Zero knowledge proof
    A primality test

Mandatory literature

Manuel Delgado e António Machiavelo; Teoria dos números - uma introdução com aplicações, 2017

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

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.