 | | |
| MATH0064-1 | Discrete mathematics II
|
|
| Duration : | 30h Th, 30h Pr |
|
| Number of credits : |
|
|
| Lecturer : | Michel Rigo |
|
Language(s) of instruction :
|
| French language |
|
Course contents :
|
| In this lecture on discrete mathematics, we are concerned with the following topics : study of linear recurrent sequences (on an arbitrary ring), introduction to cryptography and error-correcting codes. These subjects have a lot of applications : enumeration problems in combinatorics, secure electronic merchandising, authentification problem, secrets sharing, ...
Assuming classical knowledge on algebra obtained during the first two years at a University level, we study linear recurrent sequences (over a ring, a field or a finite field). We give some methods for solving such recurrence relations (exact methods but also approximate methods using elementary asymptotics). As an application, we survey some counting problems like counting the number of well-parenthesed words. Next, we present some classical aspects of modern cryptography : secret key cryptosystems, public key cryptosystem, RSA cryptosystem, discrete logarithm problem, cryptanalysis, random generation of large prime numbers, factoring algorithms, hash function,... (Depending on the schedule, we could also present some cryptosystems built upon an elliptic curve.) We are in particular interested in the involved algorithms and their complexity. To enlighten this lecture, implementation of the various concepts is given through the use of Mathematica. Finally, we give a short presentation of error-correcting codes. This lecture is mainly focused on theoretical aspects, applications are only sketched. |
|
Learning outcomes of the course :
|
| At the end of this course, the student will master fundamental notions seen during the lectures and arising in the study of finite fields (structure, generators, construction of finite fields), in cryptography (RSA in practice, discrete logarithm,...) and for linear recurrent sequences (formal series, generating series, companion matrix, finite field, Catalan numbers,...) as well as the corresponding proofs. In particular, the student will integrate the structure of finite fields and the concepts of private/public cryptosystem and ciphering. He/she will be able to explain and make use of the various techniques to get a closed formula for a linear recurrent sequence. |
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| We assume a good knowledge of the concepts of groups, rings and vector spaces. |
|
Mode of delivery (face-to-face ; distance-learning) :
|
| Lectures are mainly dedicated to theoretical aspects. Pratical sessions are devoted to solve exercises and to enlighten the concepts presented during the lecture. It could be considered to implement some cryptographic notions in a computational software like Mathematica. Detailed schedule will be given at the beginning of the academic year. |
|
Recommended or required readings :
|
| Lecture notes are available (in french) and can be downloaded from http://www.discmath.ulg.ac.be/ (http:///) |
|
Assessment methods and criteria :
|
| The final examination is an oral one devoted to the theory (mainly proofs of theorems) but also direct applications of the theory (student may be asked to solve a small exercise on the blackboard or on a sheet of paper). |
|
Organizational remarks :
|
| Some useful informations are given on
http://www.discmath.ulg.ac.be/ |
|
Contacts :
|
| M. Rigo
Institute of Mathematics (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
|
| Items online : |
|
|
| |
