Institut de Mathématiques de Luminy

Stages 2002-2003

( + propositions de mémoires DEA et proposition de stage DEA)

François Rodier :
IML, équipe ATI
Amélioration des codes de Goppa.

Résumé : Divers auteurs ont présenté des amélioration des codes de Goppa. Sur certaines courbes, on a pu obtenir une meilleure borne sur la distance, grâce au travaux de Feng et Rao sur le décodage. Je propose de lire des articles sur ce sujet, et de dégager les méthodes en oeuvre dans cette amélioration.
Références :
[1] T. Hoholdt, J.H. van Lint et R. Pellikaan, Algebraic geometry codes, in Handbook of coding theory, éditeurs: Huffman et Pless, Elsevier Sciences, 1998.
[2] Blake, Heegard, Hoholdt, Wei, Algebraic-Geometry Codes, in IEEE transactions of information theory, Vol 44, no 6, octobre 1998.

Serge Vladut :
IML, équipe ATI
1 - Suites équiréparties, théorie de codage et courbes algébriques.

Il s'agit d'initiation dans le domaine en vite expansion qui permet de construire des suites multidimensionnelles très bien équiréparties (beaucoup utilisées dans la math. appli) à partir de codes correcteur d'erreurs et de courbes algébriques sur les corps finis, et aussi dans les nouveaux liens entre eux, qui en découlent.
Références:
- Niederreiter, H. Nets, (t,s)-sequences, and algebraic curves over finite fields with many rational points. Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998). Doc. Math. 1998, Extra Vol. III, 377--386.
- Skriganov, M. Coding theory and uniform distributions. Algebra i Analiz 13 (2001), no. 2, 191--239 Rozenbloom M. and Tsfasman M. Codes for the m-metric, Problems Inform.Transmission 33, no. 1, 45--52, 1997.
2 - Bons et mauvais usages de courbes elliptiques dans la cryptographie.
Il s'agit de faire un bilan des avantages et des desavantages des applications de courbes elliptiques aux fins cryptographiques base sur un tout nouvel papier du fondateur du domaine : N. Koblitz, "Good and bad uses of elliptic curves in cryptography", 25 pp., à paraitre dans Moscow Mathematical Journal (2002).

Xavier Bresssaud :
IML, équipe DAC

Formes normales et dynamique symbolique.

Un groupe G de présentation finie est décrit par un ensemble fini S de générateurs soumis à un ensemble fini R de relations. Tout mot fini sur l'alphabet S décrit un élément du groupe. Un élément g de G a, a priori, plusieurs écritures comme mot sur S ; on passe de l'une à l'autre à l'aide d'une suite finie de relations de R. Parmi celles ci, on considère celles qui sont de longueur minimale. Si on fixe un ordre sur S, on peut associer à tout g de G, une écriture unique, celle qui est de longueur minimale et qui est minimale pour l'ordre lexicographique. Soit L le sous ensemble de S* image de G. On vérifie que l'adhérence de L est un sous shift.
L'objet de ce stage est d'explorer les liens entre la structure de ce sous shift et les propriétés du groupe G. Une premiere étape consiste à comprendre les propriétés du sous shift qui dépendent de l'ordre choisi, puis celles qui dépendent de la famille de générateurs choisie.
Pour se familiariser avec les groupes finiment engendrés, on pourra feuilleter "Combinatorial Group Theory" de Lyndon et Schupp (Springer, 1977).

Paul Ruet :
IML, équipe LDP
Modules de preuves non-commutatives.

Résumé : Le but du stage est d'introduire les notions de base de logique non-commutative : variétés d'ordres, réseaux [2,4]. On abordera ensuite les modules de preuves, introduits pour la logique linéaire dans [3] puis étendus dans [1] à la logique non-commutative. Le but du stage est de comprendre, et, peut-être, simplifier les résultats de [1].
Bibliographie :
[1] "Modules in non-commutative logic", V. M. Abrusci. TLCA'99. LNCS 1581 (1999).
[2] "Non-commutative logic I : the mutiplicative fragment", V. M. Abrusci, P. Ruet. APAL 101:29-64 (2000).
[3] "Multiplicatives", J.-Y. Girard. Rend. Sem. Mat. Univ. Pol. Torino:11-33 (1987).
[4] "Non-commutative logic II : sequent calculus and phase semantics", P. Ruet. MSCS 10:277-312 (2000).

Robert Rolland :
IML, équipe ATI

1 - L'utilisation des réseaux en cryptologie.

Références:
- A. Joux, J. Stern, Lattice Reduction : a Toolbox for the Cryptanalyst.
- P. Nguyen, J. Stern, The Two Faces of Lattices in Cryptology.
2 - Protocoles de Diffie-Hellman.
Référence principale : N.P. Smart, S. Siksek, A fast Diffie-Hellman Protocol in Genus 2.
Il s'agit tout d'abord de replacer le protocole de Diffie-Hellman dans le contexte de la cryptographie, de donner les résultats connus de complexité sur ce protocole. En particulier, on montrera l'existence d'un algorithme sous-exponentiel dans le cas de (Z/nZ)*.
On étudiera ensuite l'implémentation faite par Smart et Siksek utilisant les surfaces de Kummer.

Jean-Claude König (konig@lirmm.fr, tél. 04.67.41.86.28),
LIRMM, équipe : Département IFA.
Diffusion contrainte dans un groupe.
(mots clefs : réseaux, algorithmes de communication, optimisation combinatoire).
La technique classique pour gérer les communications multipoints (c'est-à-dire des communications entre les membres d'un groupe partageant une application comme par exemple une visioconférence) consiste à allouer au groupe "une bonne structure" dans le réseau sous-jacent, toutes les communications du groupe passant par cette structure. Classiquement, la structure choisie est un arbre couvrant les membres du groupe. Le choix de cette topologie est lié à la nécessité de simplicité dans la gestion du groupe et en particulier pour l'algorithme de routage utilisé entre les membres du groupe. Pour des contraintes de qualités de service (temps réel notamment) et de coût (le groupe utilise des ressources du réseau), il est nécessaire d'optimiser certains paramètres dans la construction de l'arbre. Par exemple le problème de construire un arbre ayant un minimum de liens a été très étudié. Ce problème appelé "problème de l'arbre de Steiner" est NP-complet et on connait des algorithmes rho-approchants pour le résoudre. Le but du stage est d'étudier la complexité d'une variante du problème précédent : les communications entre un émetteur et les membres du groupes doivent passer par un noeud capable de rendre un service, dans la suite nous appelerons ces noeuds des traducteurs. La complexité dépend évidemment du nombre de traducteurs dans le réseau, le nombre maximum de traducteurs autorisés dans un arbre de diffusion, le nombre de membres du groupe.
Le problème sera donc regardé dans un premier temps avec des petites valeurs pour ces paramètres ou sur des réseaux de topologie particulière.

Olivier Cogis et Jean-Claude König (cogis@lirmm.fr, tél. 04.67.41.85.42),
LIRMM, équipe : Département IFA.
Problèmes de connexité dans les communications de groupe.
(mots clefs : réseaux, communications de groupe, connexité).
En général, un réseau, pour rendre un service donné, doit posséder certaines propriétés. Il est persistant relativement à une propriété et un ensemble de modifications potentielles s'il conserve cette propriété après de telles modifications. L'exemple simple, déjà abondamment étudié, de ce type de problèmes est : la transmission de messages entre chaque paire de routeurs. La propriété requise est la connexité, la 2-connexité du graphe modélisant le réseau permet de conserver la connexité en cas de panne (la modification autorisée) d'un routeur. Les algorithmes de routage du monde Internet permettent de remettre dans un état cohérent les tables de routages de façon distribuée. Le but de ce stage est de généraliser cet exemple aux communications de groupe. Une structure, incluse dans le graphe modélisant le réseau physique, permet de communiquer dans le groupe. La protection des communications en cas de pannes nécessite des structures plus complexes qu'un arbre : par exemple deux arbres par groupe ou un groupe connecté par un graphe 2-connexe. L'existence, la recherche, l'optimisation de telle structure pose de nombreux problèmes de natures théoriques ou algorithmes.


La courbe de Klein.

Gilles Lachaud et Michael Tsfasman.
Bibliographie :
The eightfold way, Cambridge, 1999.
Cryptosystème à clef publique sur des groupes finis non abéliens
Yves Aubry
L'essentiel des cryptosystèmes à clef publique est basé, ou bien sur la difficulté de factoriser des grands nombres (type R.S.A.), ou bien sur le problème du logarithme discret dans des groupes abéliens. Le sujet du mémoire porte sur un nouveau cryptosystème, présenté au congrès international CRYPTO en août 2001, construit sur des groupes finis NON abéliens (plus précisément, sur le problème du logarithme discret dans le groupe des automorphismes intérieurs d'un groupe fini non abélien).
Références :
[1] I. Blake, G. Seroussi & N. Smart. Elliptic curves in cryptographie, London Math. Soc., Lect. Notes Series 265, Cambridge university press, 1999.
[2] S.-H. Paeng, K.-C. Ha, J. H. Kim, S. Chee & C. Park. New public key cryptosystem using finite non abelian groups, Advances in Cryptology - CRYPTO 2001, Lecture notes in computer science 2139, Springer 2001, p. 470-485.

Coloration de graphes appliquée à l'allocation de fréquences.
Projet Mascotte, INRIA Sophia-Antipolis

Description : L'allocation de fréquences est un problème récurrent en télécommunications. Il consiste à allouer des fréquences à des transmetteurs de manière à éviter les interférences et en utilisant le moins de fréquences possibles.
Une première modélisation de ce problème en terme de coloration d'un graphe est la suivante : les sommets du graphe représentent les transmetteurs, deux sommets sont reliés par une arête si les transmetteurs correspondant peuvent interférer et les couleurs représentent les fréquences. Affecter les longueurs d'onde revient à trouver une bonne coloration du graphe.
Les zones d'émission des transmetteurs étant très généralement des cercles, nous étudions la coloration des graphes d'intersection de disques dans le plans. Par exemple, voir l'étude du cas particulier du réseau triangulaire : http://www-sop.inria.fr/mascotte/personnel/Frederic.Havet/rech/alloc.html
Cette modélisation est une première étape vers une modélisation plus réaliste qui impose des contraintes comme des interférences possibles entre deux longueurs d'ondes voisines si les transmetteurs ne sont pas assez éloignés.
Bibliographie :
- F. Havet, Channel assignment and multicolouring of the induced subgraphs of the triangular lattice, Discrete Mathematics 233 (1-3), 219-231 (2001).
- F. Havet and J. Zerovnik, Finding a five bicolouring of a triangle-free subgraph of the triangular lattice, Discrete Mathematics, to appear.
- J. van den Heuvel, R. A. Leese and M. A. Shepherd, Graph labelling and radio channel assignment, J. Graph Theory 29:263-283, 1998.
- C. McDiarmid and B. Reed, Channel assignment.

Des sujets de stage vous sont proposés à l'INRIA Sophia dans chaque équipe d'accueil: Certilab, Lemme, Meije, Oasis, Saga et Sloop. Vous pouvez aussi consulter la page générale des stages proposés à l'INRIA Sophia-Antipolis.

Semaine intensive à Sophia-Antipolis du 26 au 28 novembre 2001

Mise à jour le 17 novembre 2003, EL