CTL
21 juin 2010 - 14h00
Nouveaux algorithmes génériques pour la résolution de sacs-à-dos
par Joux Antoine de PRISM Equipe Crypto Université de Versailles
Résumé : Le problème du sac-à-dos est fréquemment rencontré en cryptographie. Il s'agit d'un problème difficile dans le cas général (bien que certains cas particuliers soient faciles) pour lequel le meilleur algorithme connu capable de résoudre les sacs-à-dos les plus difficiles à n éléments nécessite un temps de l'ordre de 2^(n/2) et une mémoire de taille 2^(n/4).
Nous présentons ici un nouvel algorithme de complexité 2^(0.311... n).
