Number Theory and Criptography

Code:

M3032

Acronym:

M3032

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2023/2024 - 2S

Active?	Yes
Web Page:	https://moodle2324.up.pt/course/view.php?id=2086
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:B	2	Official Study Plan	3	-	6	48	162
L:CC	8	study plan from 2021/22	2	-	6	48	162
			3
L:F	0	Official Study Plan	3	-	6	48	162
L:G	0	study plan from 2017/18	2	-	6	48	162
			3
L:M	64	Official Study Plan	2	-	6	48	162
			3
L:MA	0	Official Study Plan	3	-	6	48	162
L:Q	0	study plan from 2016/17	3	-	6	48	162

Teaching language

Suitable for English-speaking students
Obs.: Poderá ser feito em inglês o esclarecimento de dúvidas de estudantes que não dominem o português.

Objectives

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

Learning outcomes and competences

Upon completing this curricular unit, the student should know the basic concepts and results of Number Theory, as well as some of its computational aspects and cryptographical applications.

Working method

Presencial

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

Basic notions of Linear Algebra and Programming

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

Complementary Bibliography

William Stein; Elementary Number Theory: Primes, Congruences, and Secrets , Springer, 2009
Kenneth Ireland; A classical introduction to modern number theory. ISBN: 0-387-90625-8
Alfred J. Menezes; Handbook of applied cryptography. ISBN: 0-8493-8523-7
Victor Shoup; A computational introduction to number theory and algebra. ISBN: 0-521-85154-8

Teaching methods and learning activities

Presentation of the course material and examples by the teacher; solution of exercises by the students with the teacher's advice.

Software

GAP (https://www.gap-system.org/)
Sage (https://www.sagemath.org/)

Evaluation Type

Distributed evaluation with final exam

Assessment Components

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

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	114,00
Frequência das aulas	48,00
Total:	162,00

Eligibility for exams

Course registration is the only requirement.

Calculation formula of final grade

In practical classes, four sets of exercises will be carried out, on dates to be announced.
The first three sets of exercises have a weight of 3 points each and the two best-ranked ones contribute towards the final grade.
The fourth set of exercises has a weight of 5 points, which can contribute towards the final grade.
The classifications obtained in the exercises can be used in the exam, as described below.

Approval of the curricular unit is obtained in the final exam.

The final exam will have three parts.
The first part corresponds to the first three sets of exercises and its weight is 6 points.
The second corresponds to the fourth set of exercises and its weight is 5 points.
The student may choose not to solve one or both of these parts of the exam, with each unsolved part being assigned the classification obtained by the student in the corresponding sets of exercises.
The third part of the exam has a weight of 9 points.

Special assessment (TE, DA, ...)

Any type of special student evaluation takes the form of a written examination.

Classification improvement

Grade improvement can be attempted only through examination.