Sujets de projets SFPN de M1 2014-2015

Attribution des sujets et contrôle des connaissances acquises

Il convient de contacter rapidement les encadrants du sujet choisi, en leur indiquant le nom des étudiants concernés, typiquement celui des deux étudiants d'un binôme. Un mail ne mentionnant qu'un seul nom ne sera pas pris en compte.

Il peut y avoir un dialogue entre les encadrants d'un projet et plusieurs binômes qui souhaitent traiter ce sujet. Le binôme retenu n'est pas nécessairement le premier qui a pris contact avec les encadrants.

Les encadrants font connaître leur réponse quelques jours plus tard, par un mail destiné aux binômes et à moi. L'attribution est définitive à la réception de la confirmation du binôme par mail aux encadrants et à moi en indiquant clairement le sujet concerné.

Il est souhaitable que le travail commence dès la fin des examens répartis et de tirer au mieux parti des deux semaines d'inter-semestres pour prendre connaissance du sujet et des documents éventuels que les encadrants vous demanderont de lire.

Les soutenances auront lieu après les vacances de printemps entre le 4 et le 15 mai. Les dates seront précisées davantage ultiérieurement. Il est conseillé de préparer sa soutenance suffisamment à l'avance et avec ses encadrants.

Il pourra y avoir une pré-soutenance de mi-parcours au libre choix des encadrants, mais il n'y aura rien de systématique au niveau global de l'UE PSFPN.

Les nombres réels sont modélisés sur ordinateur par l'ensemble discret des nombres flottants. Les humains sont habitués à manipuler des nombres décimaux, alors que les ordinateurs utilisent des nombres binaires [1]. La première utilisation de la conversion binaire vers décimal est l'affichage des flottants [2].

Pendant le boot du noyau du système d'exploitation, il faut afficher des nombres flottants en décimal. Mais durant cette phase, les bibliothèques d'arithmétique flottante ne sont pas encore initialisées, on a besoin donc de réaliser cet affichage sans utiliser d'opération flottante.

Dans ce projet il s'agit de concevoir un algorithme pour l'affichage des flottants en manipulant les exposants et les mantisses sous forme d'entiers. Il faut d'abord convertir la représentation binaire vers la représentation décimale, composer la chaîne de caractères puis l'afficher.

1. "IEEE Standard for Floating-Point Arithmetic," IEEE Std 754-2008, pp.1-70, Aug. 29 2008.
2. Committee Draft, International C Standard. ISO/IEC 9899:201x, 2011.

Les nombres réels sont modelisés sur ordinateur par l'ensemble discret des nombres flottants. Chaque opération d'arithmétique flottante rend un résultat entâché d'erreur. Pour obtenir le résultat du calcul avec une erreur inférieure à une borne fixée à l'avance (erreur cible), il peut être nécessaire de faire ce calcul en arithmétique multi-précision.

Pour approcher la fonction f sur un intervalle I on peut utiliser l'interpolation[1]. Le théorème de Weierstrass montre qu'une fonction continue sur un intervalle I peut être approchée par un polynôme p avec une erreur que l'on peut faire tendre vers zéro[2].

Pour ce projet il faut établir les relations entre les paramètres d'interpolation (degré, précision, etc.) et l'erreur cible de l'interpolation. Il s'agit de concevoir un algorithme d'interpolation polynomiale avec contrôle d'erreur. Il faut calculer l'interpolation avec une erreur inférieure à l'erreur cible.

Pour le calcul de flottants multi-précision on utilisera la bibliothèque MPFR[3] et pour le calcul sur les intervalles flottants on utilisera MPFI[4]. Il n'y a aucun pré-requis d'utilisation de ces bibliothèques, il suffit de lire la documentation pendant ce projet pour pouvoir les utiliser. Les bibliothèques mentionnées sont installées dans les salles de la PPTI.

1. Cheney, Elliott Ward "Introduction to Approximation Theory", AMS Chelsea publishing, 1982.
2. Franck Jedrzejewski "Introduction aux méthodes numériques" Springer-Verlag France, Paris 2005
3. MPFR
4. MPFI

Le calcul d'éléments propres, c'est-à-dire de valeurs et vecteurs propres, pour des matrices données est une brique de base pour un grand nombre d'applications en calcul scientifique, fouille de données etc.

Des bibliothèques bien connues comme LAPACK [1] existent pour ce calcul d'éléments propres en virgule flottante. Toutefois, elles n'offrent que des fonctions couvrant les précisions IEEE754 [2] classiques, telles que simple et double précision.

Certaines applications demandent pourtant de manipuler des matrices à entrées plus précises que la double précision et, surtout, une détermination des éléments propres avec une grande précision.

L'arithmétique flottante de base (addition, soustraction, multiplication etc.) en grande précision est fournie par des bibliothèques de calcul flottant multiprecision, telles que GNU MPFR et GNU MPC.

Les algorithmes classiques pour les éléments propres [3] peuvent être implantés pour n'importe quelle précision de calcul et fournissent, avec une adaptation adéquate du nombre d'itérations pour les méthodes itératives, des résultats en multiprécision. Le sujet de stage est l'implantation multiprécision d'une ou deux de ces méthodes en multiprécision.

Le stage se passera en cinq temps. Les étudiant(e)s commenceront par une lecture de livres et articles scientifiques de référence sur le sujet. Ils procéderont ensuite à une lecture des codes disponibles dans des implémentation Open Source de LAPACK. Puis, les étudiant(e)s implémenteront quelques fonctionnalités de base en algèbre linéaire multiprécision en se servant des bibliothèques de virgule flottante multiprécision (complexe) GNU MPFR et GNU MPC (multiplication de matrices, normalisation de vecteurs, décomposition QR etc.) Sur cette base, les étudiant(e)s implémenteront un ou deux algorithmes de calculs de valeurs et vecteurs propres (itération de Krylov et algorithme QR). Finalement, s'il reste du temps, ils testeront leur implémentation sur un ensemble de tests pertinents à développer conjointement avec l'encadrant.

1. LAPACK
2. IEEE Standard for Floating-Point Arithmetic," IEEE Std 754-2008, pp.1-70, Aug. 29 2008
3. Golub, G. H. and Van Loan, C. F.: Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996.

Du fait de leur précision finie, l'utilisation de nombres à virgule flottante pour représenter les nombres réels introduit des erreurs d'arrondi dans les calculs numériques. La propagation de ces erreurs peut alors dégrader très significativement la qualité numérique des résultats. Le logiciel CADNA permet de valider numériquement des codes scientifiques en estimant le nombre de chiffres significatifs exacts des résultats. Avec le développement actuel du calcul haute performance et des nouvelles architectures de calcul massivement parallèles, cette validation numérique devient cruciale pour de nombreux codes dans les centres de calcul académiques et industriels.

Mais l'utilisation de CADNA introduit un surcoût en temps d'exécution et en mémoire. Nous avons récemment proposé une nouvelle version de CADNA qui permet de limiter ce surcoût en temps, et nous souhaitons déployer (le plus efficacement possible) cette nouvelle version de CADNA sur différentes architectures parallèles.

Dans un premier temps, on visera les architectures de type CPU multi-coeurs à l'aide du standard de programmation multi-thread OpenMP. On visera notamment deux approches pour instrumentaliser un code avec CADNA : une première approche basée sur le changement explicite des types de données et l'utilisation explicite des fonctions CADNA dans le code source, et une deuxième approche (non intrusive et plus légère) basée sur l'utilisation de directives de compilation. Cette deuxième approche pourra alors être étendue si nécessaire. Des tests pertinents pour montrer l'intérêt de coupler CADNA et OpenMP sur des exemples jouets ou sur des simulations réelles devront ensuite être effectués. On pourra pour cela s'appuyer sur un serveur doté de 16 coeurs de calcul (32 threads matériels) ou sur un nouveau processeur Intel Xeon Phi à 60 coeurs (240 threads matériels).

Dans un second temps, on pourra s'intéresser à un premier déploiement de la nouvelle version de CADNA sur un GPU (Graphics Processing Unit), de type NVIDIA K20 à 2496 «coeurs GPU», en utilisant le langage CUDA.

1. CADNA
2. OpenMP
3. CUDA

Sujet 5: Évaluation précise de fractions rationnelles

Sujet 6: Factorisation et la résolution d'équations polynomiales

Pour prouver qu'un polynôme est positif sur les nombres réels, il suffit de pouvoir l'écrire comme une somme de carrés. Ce projet consiste à étudier les algorithmes existants et à les implanter. On commencera par étudier les algorithmes de résolution d'inégalités matricielles qui permettent d'effectuer de telles décompositions pour des polynômes en plusieurs variables. Si le temps le permet, on étudiera des techniques spécifiques au cas univarié.

Énoncé plus détaillé à venir

On étudiera des algorithmes pour la résolution de systèmes polynomiaux en deux variables. Ces algorithmes sont rapides du point de vue théorique et il s'agira de mettre en place l'infrastructure logicielle pour concrétiser sur des résultats pratiques ces résultats théoriques.

Énoncé plus détaillé à venir

Le monde moderne est complètement dépendant des technologies numériques. Toutes les données sont stockées et transmises sous forme électronique. Ceci expose potentiellement ces données à de graves menaces. La cryptographie est une collection de techniques mathématiques utilisées pour sécuriser la transmission et le stockage de l’information. L’un des problèmes fondamentaux de la cryptographie est d’évaluer la sécurité des systèmes cryptographiques avec les techniques les plus puissantes. À cette fin, plusieurs méthodes générales ont été proposées : la cryptanalyse linéaire, cryptanalyse différentielle, etc. L’objectif du projet est de se familiariser avec une autre méthode générale : la cryptanalyse algébrique. L’idée directrice est de modéliser un algorithme cryptographique sous la forme d’un système d’équations non-linéaires. Le système est construit de manière à établir une correspondance entre les solutions de ce système et une information secrète du cryptosystème en question (par exemple, la clef privée d’un chiffrement). On propose ici de mettre en œuvre une telle cryptanalyse sur un schéma à clef secrète.

Le Wired Equivalent Privacy (WEP) est un protocole permettant de sécuriser es réseaux de type Wi-Fi. Une brique de base du WEP est le chiffrement par flux RC4 qui est bien connu pour ses faiblesses. On propose ici d'étudier (et de reproduire) une attaque récente de Pouyan Sepehrdad, Petr Susil, Serge Vaudenay, Martin Vuagnoux: "Smashing WEP in a Passive Attack" qui proposent une nouvelle méthode pour exploiter les faiblesses de RC4.

Sujet 11: Cryptographie Multivariée: Un Second Regard sur HFE

Sujet 12: Cryptologie Embarquée

Sujet 13: Programmation Cryptologique sur Carte à Puce et Iphone

Beaucoup de constructions cryptographiques sont composées de transformations inversibles sur des entiers de n bits. Les contraintes impliquées par la réalisation logicielle de ces constructions nous poussent plus particulièrement vers des transformations pouvant être implémentées comme des compositions d'instructions basiques.

On s'intéresse donc à trouver des bijections dans l'ensemble des entiers de n bits, c'est-à-dire modulo 2ⁿ. Un exemple de bijections trivial est l'ensemble des affines a*x + b avec a impair. Le but du projet est de dresser une liste exhaustive des bijections connues modulo 2ⁿ (voir par exemple les polynômes de permutation de Rivest [1] ou encore les T-fonctions de Klimov et Shamir [2]), et d'étudier les limites de ces dernières : est-il possible de trouver l'inverse d'une bijection en temps contraint, et sinon, pourquoi est-ce impossible ?

Le projet s'organisera donc en plusieurs temps : état de l'art des bijections existantes, calcul de l'inverse de celles-ci en temps contraint, implémentation d'un programme destiné à fournir une bijection aléatoire et son inverse.

1. Ronald R. Rivest, Permutation Polynomials Modulo 2^w
2. Alexander Klimov and Adi Shamir, A New Class of Invertible Mappings

Sujet 15: Y'a d'la crypto dans l'air...