La course aux nombres premiers

Comme vous l'avez vu pour le codage RSA, la cryptographie est grande consommatrice de nombres premiers, les plus imposants possibles évidemment. Un moyen de trouver de grands nombres premiers est de les chercher parmi les nombres dits «de Mersenne», autrement dit sous la forme $2^k-1$. Pourquoi ? Parce qu'il existe un test de primalité extrêmement simple pour de tels nombres : le test de Lucas-Lehmer. Considérons la suite définie par $a_0=4$ et pour $k>0$, $a_k=a_{k-1}^2-2$. Il se trouve que pour $k>2$, le nombre $2^{k}-1$ est premier si et seulement si il divise $a_{k-2}$. Essayez pour les premiers termes :

$\bullet$

$2^3-1=7$ divise $a_1=14$

$\bullet$

$2^4-1=15$ ne divise pas $a_2=194$

$\bullet$

$2^5-1=31$ divise $a_3=37634$

...  étonnant non ? Avec un peu d'astuce, le test peut être implémenté en
$O(p^2\ln(p)\ln(\ln(p)))$ opérations pour un nombre de $p$ bits, ce qui est bien plus rapide que tous les algorithmes généraux connus. Un gigantesque effort collaboratif de calcul distribué (Great Internet Mersenne Prime Search) vise à trouver des nombres de Mersenne premiers les plus grands possibles. Le plus grand connu à ce jour est $2^{43112609}-1$ qui a plus de 12 millions de chiffres en écriture décimale. Rien de vous empêche de participer en offrant le temps de calcul de votre ordinateur. Vous ferez progresser le calcul distribué, mais pas la cryptographie : les nombres de Mersenne sont trop connus pour offrir un niveau de sécurité suffisant. S'il suffisait de tester quelques nombres de Mersenne pour décomposer une clé publique en deux facteurs premiers, le code RSA perdrait beaucoup de son intérêt. Gauss écrivait :

Le problème de distinguer les nombres premiers des nombres composés, et de décomposer ces derniers en facteurs premiers est connu pour être un des plus importants et des plus utiles en arithmétique. Il a engagé l'industrie et la sagesse des géomètres anciens et modernes à un tel point que la dignité de la science elle-même requiert que tous les moyens possibles soient explorés pour la résolution d'un problème si important et si célèbre.

La véritable difficulté est de tester des nombres quelconques, et donc de disposer d'un algorithme permettant de décider de façon certaine si un nombre est premier ou non. Ératosthène (276-194 av. J.C.) savait déjà comment énumérer tous les nombres premiers inférieurs à un nombre $n$ donné. L'algorithme, qui porte le nom de «Crible d'Ératosthène», est bien connu : $2$ est le plus petit nombre premier. On peut éliminer tous les multiples de $2$. On itère ensuite en conservant le plus petit entier qui n'a pas encore été éliminé et en éliminant tous ses multiples. Mais pour décider si $n$ est premier en utilisant cet algorithme, le nombre d'opérations est gigantesque, beaucoup trop grand pour la pratique. Une autre manière de tester la primalité est d'utiliser le théorème de Wilson : $n$ est premier si et seulement si $(n\!-\!1)!$ est congru à $-\!1$ modulo $n$. Cela requiert de l'ordre de $n$ multiplications modulo $n$, ce qui est encore beaucoup trop lent.

Quand en 2002 Agrawal, Kayal et Saxena ont annoncé «PRIMES is in P», la nouvelle a fait sensation. Enfin un test de primalité, dont on peut démontrer qu'il décide de façon certaine si $n$ est premier, en un nombre d'opérations polynomial en $\ln(n)$. L'article original était théorique, mais très vite des implémentations ont suivi, avec des raffinements et des améliorations. Les algorithmes AKS sont maintenant toute une famille et sont couramment utilisés. Deux points méritent d'être soulignés dans cette histoire. Le premier est que l'algorithme utilise un résultat d'arithmétique vieux de deux siècles élaboré dans la quête du Dernier Théorème de Fermat, précisément celui qui porte le nom de Sophie Germain. L'autre est que Neeraj Kayal et Nitin Saxena, à l'époque de leur découverte, étaient deux étudiants en Btech (équivalent d'un Master Professionnel) d'Informatique à l'Indian Institute of Technology de Kampur, effectuant leur mémoire sous la direction de Manindra Agrawal.