 | | |
| MATH0064-1 | Discrete mathematics II
|
|
| Duration : | 30h Th, 30h Pr |
|
| Number of credits : |
|
|
| Lecturer : | Michel Rigo |
|
Language(s) of instruction :
|
| French language |
|
Organisation and examination :
|
| Teaching in the second semester |
|
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 : delivery round, flows and networks, colorings, 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. For introductory lectures on graph theory, several topics may be treated: shortest path, connectedness, topological sort, Perron-Frobenius theory, Page Rank, covering trees, planar graphs, colorings, Ramsey theory. |
|
Learning outcomes of the course :
|
| At the end of this course, the student will master fundamental notions seen during the lectures and arising in graph theory, 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 graph 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 and finite fields. |
|
Planned learning activities and teaching methods :
|
| Theoretical lectures using "blackboard and chalk" interacting with students. During exercises sessions, students are facing exercises that must be solved and situations that must be modeled on a computer. |
|
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/
Some complementary material:
- R. Diestel, Graph Theory, 3rd Edition, Graduate Text in Math. 173, Springer, (2005).
- C. Berge, Graphes et hypergraphes, Dunod, Paris, (1970).
- C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Text in Math. 207, Springer (2001).
- C. Meyer, A. Langville, Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, (2006).
- E. Seneta, Non-Negative Matrices, An Introduction to Theory and Applications,
George Allen and Unwin Ltd, London, (1973).
- J. Buchmann, Introduction to cryptography, Second edition, Undergraduate Texts in
Mathematics, Springer, (2002).
- R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics, A foundation for
computer science, Second edition, Addison Wesley, (1994).
- A. Salomaa, Public-Key Cryptography, Second edition, Texts in Theoretical Computer
Science, An EATCS Series, Springer, (1996).
- J. Talbot, D. Welsh, Complexity and Cryptography, An Introduction, Cambridge Univ.
Press (2006).
- H. Wilf, Generatingfunctionology, Academic Press (1994).
|
|
Assessment methods and criteria :
|
| The final examination is in two parts. An oral part devoted to the theory (mainly statements and proofs of theorems and discussion) but also direct applications of the theory. The written part is dedicated to the resolution of exercises and problems. |
|
Work placement(s) :
|
| |
|
Organizational remarks :
|
| Some useful informations are given on
http://www.discmath.ulg.ac.be/
In particular, one has access to the log of the year and also the ones of previous years. |
|
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 : |
|
|
| |
