Coopération Mathématique Interuniversitaire Cambodge France,
PCSI (Programme de Coopération Interuniversitaire Scientifique)
de l'AUF (Agence Universitaire pour la Francophonie)
Course of Algebra
Phnom Penh, september 21/october 14, 2005 (60 hours)
This course follows the previous one given by Pierre Arnoux. We do not repeat what he said, apart from a few exceptions at the beginning (combinatorics, gcd and Euclid algorithm, Fermat's little Theorem) but we shall use the tools he already introduced.
We go further in the direction of primality tests, factorization algorithms, cryptography and error correcting codes. For this purpose we need to develop some more theory, especially on algebraic number theory and finite fields.
1. Sets and combinatorics
a) Generalities
b) Set of subsets. Induction
c) Counting injections and permutations
d) Binomial coefficients
e) Characteristic functions
2. Numeration
Decomposition of a number in a basis b. Binary expansion
3. Elementary arithmetic
a) Congruences
b) gcd. Euclid algorithm
c) Chinese remainder Theorem
d) The additive group Z/nZ and the multiplicative group (Z/nZ)*
4. Primality
a) Position of the problem
b) Fermat's little Theorem. Cryptography
c) Primality criteria. Carmichael numbers
5. Quadratic residues
a) Definition and properties. Legendre symbol
b) The law of quadratic reciprocity (Gauss)
c) Jacobi symbol
d) Probabilistic algorithms
6. Divisibility
a) Rings and ideals
b) Quotient rings
c) Polynomials
d) Euclidean rings
e) Continued fraction algorithm
7. Finite fields
a) Structure of finite fields
b) Cyclotomic polynomials
c) Construction of finite fields
d) Decomposition of polynomials over a finite field
8. Error correcting codes
a) Symmetric binary codes
b) Coding and decoding. Errors
c) Linear codes
d) Cyclic codes
References:
Maurice Mignotte - Algèbre appliquée à l'informatique. Presses Universitaires de France, 1987.
Michel Demazure - Cours d'Algèbre. Cassini, 1997.
Jacques Vélu - Méthodes mathématiques pour l'informatique. Dunod, 1999.
Neal Koblitz - A course in Number Theory and Cryptography. Springer Graduate Texts in Mathematics, 114, 1994.
Dominique Welsh - Codes and Cryptography. Oxford Science Publications, 1988.
Rudolf Lidl and Harald Niedereitter - Introduction to finite fields and their applications. Cambridge Univ. Press, 1994.
Examen écrit du 21 octobre 2005, sujet (en français) 100 Ko
Examen écrit du 21 octobre 2005, corrigé (en français) 88 Ko (mise à jour 5/11/2005)
Written exam, october 21, 2005 (in english) 100 Ko
Written exam, october 21, 2005, solution (in english) 80 Ko (update 5/11/2005)