Amélioration des algorithmes de crible. Application à la factorisation des entiers.

Le Crible Algébrique (NFS) est l’algorithme de pointe pour la factorisation des entiers, et le crible est une étape cruciale du NFS. Il s’agit d’une opération qui prend beaucoup de temps et dont le but est de collecter de nombreuses relations. Son but final est de générer des entiers lisses aléatoires mod N avec leur décomposition en facteurs premiers, où le caractère lisse est défini sur les côtés rationnel et algébrique en fonction de deux bases de facteurs premiers. Dans les outils de factorisation modernes, tels que Cado-NFS, le crible est divisé en différentes étapes en fonction de la taille des nombres premiers, mais la définition de bons paramètres pour toutes les étapes est basée sur des arguments heuristiques et pratiques. Au début, les candidats sont criblés par de petits nombres premiers des deux côtés, et s’ils réussissent le test, ils passent aux étapes suivantes avec des nombres premiers plus grands, jusqu’à la dernière où nous factorisons la partie restante à l’aide de l’algorithme ECM. D’une part, les premières étapes sont rapides, mais laissent passer de nombreux faux positifs ce qui ralentit l’algorithme. D’autre part, les étapes finales prennent plus de temps mais produisent moins de relations. Il n’est pas facile d’évaluer la performance de la meilleure stratégie sur l’ensemble de l’étape de crible car elle dépend de la distribution des nombres qui résulte de chaque étape. Dans cette thèse, nous essayons d’examiner différentes stratégies de crible pour accélérer cette étape puisque de nombreuses améliorations ont été apportées à toutes les autres étapes du NFS. Sur la base des relations collectées lors de la factorisation du module RSA-250 et de tous les paramètres, nous essayons d’étudier différentes stratégies pour mieux comprendre cette étape.