|
GREYC
|
|
GREYC
|
Dans ma thèse, j'ai introduit de nouveaux outils, plus efficaces en moyenne, pour la réduction. Une suite naturelle est de profiter de l'efficacité de ces outils pour mettre au point des stratégies algorithmiques en fonction des applications précises (travail déjà commencé dans le dernier chapitre de ma thèse). Une collaboration est envisagée avec FREDERIC LEHOBEY(ATER à Rennes), pour appliquer ces réductions à une factorisation plus efficace de polynômes à coefficients entiers. Pour être opérationnelles, les stratégies algorithmiques de réduction devront intégrer également les autres améliorations déjà existantes dans le domaine de la réduction, en particulier les versions des algorithmes de réduction en flottant ou les versions parallèles. On devra aussi tenir compte de nombreuses considérations expérimentales, pas encore clairement comprises sur le plan théorique.
Je rappelle qu'un grand nombre de problèmes d'optimisation entière se réduisent bien à la recherche d'un vecteur court dans un réseau.
Il existe déjà des
heuristiques
dues à BABAI, à KANNAN et à
SCHNORR
en vue par exemple
d'obtenir un plus court vecteur d'un réseau, lorsque l'on dispose
d'une base Lovász-réduite. L'efficacité (en moyenne) des
heuristiques
précédentes pourrait être améliorée en considérant les
nouvelles réductions introduites dans ma thèse.
Cette année, j'ai proposé et j'encadre deux projets de DESS, tous deux concernant les applications de la réduction des réseaux et notamment des algorithmes introduits dans ma thèse. (L'un concerne la factorisation de polynôme à coefficients entiers, l'autre la cryptographie à base du problème sac-à-dos).
Par ailleurs, je suis invité à participer pendant un mois (cet été) au programme semestriel "Algorithmic number theory" au MSRI, à Berkeley. Je compte développer les stratégies algorithmiques de réductions, en collaboration avec des spécialistes du calcul formel et de cryptographie, tels que BUHLER, DWORK, LENSTRA, ODLYZKO ou POONEN.
