S1- Cours spécifiques aux mentions

Ce module est une coproduction du département de mathématiques et du département d'informatique.
L'objectif de cette UE est d'initier les étudiants à la fois au formalisme mathématique, aux structures de données et à la programmation.
On y apprendra à rédiger une preuve par un raisonnement déductif, par contraposée, par l'absurde, par disjonction des cas, par récurrence.

La partie théorique porte sur les aspects algorithmiques de l'arithmétique élémentaire, ainsi que de l'arithmétique modulaire élémentaire et de quelques applications.

* Divisibilité dans Z, division euclidienne. Numérotation en base b. Application à la représentation d'entiers (naturels ou relatifs) sur 2^n bits
* Exponentiation rapide
* PGCD et algorithme d'Euclide
* Congruences et opérations.
* Applications : cryptographie, générateurs aléatoires.

TP d'implémentation en Python 3.