Crible Algébrique : Distribution, Optimisation. – CADO

Le crible algébrique (NFS) est l'algorithme le plus performant à l'heure actuelle pour factoriser de grands entiers du type modules RSA ; cet algorithme est constamment amélioré et devient à la fois de plus en plus complexe et de plus en plus efficace. L'évaluation de sa performance optimale est donc d'une grande importance pour contrôler la sécurité de pans entiers de la cryptologie à clé publique. Nous proposons d'étudier divers aspects de l'algorithme ainsi que d'en écrire une implantation libre et générale, à la fois optimisée pour des nombres de 100-150 chiffres et pouvant servir de terrain d'expérience pour des tailles d'entiers supérieures. En particulier, chaque phase devra pouvoir tirer profit de capacités de calcul distribué. Cela doit contribuer à nous permettre de mieux élucider le comportement théorique et pratique de NFS. L'architecture du projet reprend ces trois objectifs. D'une part, une étude algorithmique en profondeur sera entreprise. Elle prendra en compte diverses idées théoriques qui nécessitent une optimisation importante pour porter leurs fruits, comme l'utilisation simultanée de plusieurs polynômes ou l'idée de « factoring factory ». Plus généralement, les différentes phases de l'algorithme seront étudiées, en particulier celles où il nous semble subsister le plus de possibilités d'amélioration. Nous pensons en particulier à la sélection polynomiale, au post-traitement suivant le crible, ou à la distribution de l'algèbre linéaire, qui pourrait ouvrir la voie à l'utilisation de grilles de calcul pour l'ensemble du processus de factorisation. En parallèle, une étude théorique sera entreprise pour tenter de s'approcher d'une étude de complexité rigoureuse. L'étude portera aussi sur divers problèmes de modélisation devant permettre de simuler le fonctionnement de différentes phases de l'algorithme pour des tailles trop grandes pour être traitées aujourd'hui mais importante en cryptographie. D'autre part, une implantation de l'algorithme sera réalisée. Cette implantation servira à la fois de terrain d'expérience pour les participants au projet et de produit final du projet, à disposition de la communauté. L'objectif est à la fois qu'elle se comporte bien dans le domaine praticable (100-150 chiffres) et puisse être utilisée dans un avatar distribué pour s'attaquer à des factorisations conséquentes, voire des records. Dans un premier temps, nous nous réservons la possibilité d'utiliser du code existant pour certaines phases de l'algorithme, afin de pouvoir commencer rapidement les expériences. Les critères de succès que nous nous fixons correspondent aux résultats que nous nous attendons à obtenir : * Que notre étude de la sélection polynomiale débouche sur une proposition de polynômes pour les prochains records (RSA-768, RSA-1024) ; * Qu'une meilleure compréhension de l'algorithme résulte en une meilleure estimation des temps de calcul. * Que le post-traitement après crible soit mieux compris et optimisé, et que son influence sur les limites du crible soit étudiée ; * Que l'étude de l'algèbre linéaire débouche sur un ensemble de critère permettant de décider en fonction des données et des moyens de calcul lequel des algorithmes de Lanczos et Wiedemann est préférable ; * Enfin, qu'une implantation efficace dans l'intervalle 100-150 chiffres et distribuable soit écrite et rendue disponible.