Dépasser les frontières de l'aléatoire et du calculable – RaCAF

Les suites aléatoires sont cruciales pour l'informatique moderne. Utilisées pour la sécurité et la cryptographie, elles sont aussi au cœur de l'algorithmique randomisée. En pratique, on utilise des suites pseudo-aléatoires générées par ordinateur; ces suites pseudo-aléatoires ont des régularités plus ou moins gênantes suivant l'utilisation qu'on en fait. La compréhension de l'impact de leurs défauts nécessite une étude fine des liens entre calcul et aléatoire. Ces liens sont des propriétés `à l'infini' qui nous incitent à étudier des modèles de calcul étendus (sur le temps de calcul ou sur la nature des éléments de base). Depuis quelques années, les physiciens fabriquent des générateurs de nombres aléatoires `parfaits' à partir de phénomènes quantiques, combinés à des traitements algorithmiques secrets (dont la faisabilité parait douteuse). Nous projetons d'analyser ces suites en utilisant des méthodes algorithmiques évoluées issues de nos travaux théoriques ainsi que de certaines constructions d'algorithmique randomisée.