 |  |  |  |  |
| | |
||||
| MATH0245-2 | Discrete structures | |||||
| ||||||
| Duration : | 30h Th, 10h Pr | |||||
| ||||||
| Credits/ECTS : |
| |||||
| ||||||
| Holder(s) : | Michel Rigo | |||||
| ||||||
| ||||||
| 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, ... For the part dealing with cryptography, we present some usual cryptosystems with secret key but also public key cryptosystems like RSA or built on the discrete logarithm problem. | |||||
| ||||||
| Course objective : | 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,... 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. | |||||
| ||||||
| Prerequisites : | We assume a good knowledge of the concepts of groups, rings and vector spaces. | |||||
| ||||||
| Organization : | 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. | |||||
| ||||||
| Written notes : | Lecture notes are available (in french). | |||||
| ||||||
| Assessment : | 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). The expected knowledge needed for this examination will be officially announced during the year. | |||||
| ||||||
| 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 | |||||
| ||||||
| Remarks : | Some useful informations are given on http://www.discmath.ulg.ac.be/ | |||||
| ||||||
ULg : Students and Studies Administration - Academic Affairs
Contact : Monique Marcourt, direction A.E.E.
Date of data : 27/02/2006
Developed by SEGI