Comment fabriquer de grands nombres premiers?

Les algorithmes à clé publique comme le RSA nécessitent la fabrication de très grands nombres premiers (de l'ordre de 500 chiffres décimaux par exemple). Il existe heureusement des procédés très efficaces pour cela.

Les plus grands nombres premiers du monde

Les nombres de Mersenne sont les nombres M_p=2^p-1, où p est premier. Ils ne sont pas tous premiers, mais on dispose d'un test particulièrement efficace (le test de Lucas-Lehmer) pour tester s'ils le sont :

On construit en effet une suite S_n en posant S₁=4, et par la formule de récurrence : S_n=(S_n-1)²-2. Alors, pour p>2, on peut prouver que M_p est premier si et seulement si M_p divise S_p. Bien sûr, on réalise les calculs successifs des puissances seulement sur les restes modulo M_p!

Les records des plus grands nombres premiers sont depuis des années réalisés à partir des nombres de Mersenne. A titre d'exemple, M_13466917 possède 4 053946 chiffres décimaux, bien plus que les 500 exigés! Pourtant, ces nombres de Mersenne ne sont jamais utilisés pour la cryptographie : ils sont bien trop particuliers, et il serait beaucoup plus facile de casser le code RSA si on les utilisait.

Tests de primalité

Pour le RSA, il n'y a rien de mieux qu'un premier aléatoire, sur lequel on n'a a priori aucune information. L'idée est alors de prendre un entier de 500 chiffres au hasard, et de tester s'il est premier : si c'est le cas, on le garde, sinon on choisit un autre nombre au hasard, jusqu'à finir par tomber sur un premier. Cela pose deux problèmes. D'abord, il faut que l'on puisse trouver un premier au bout d'un nombre raisonnable de tirages. Un théorème conjecturé par Gauss, et démontré par de la Vallée Poussin, affirme que si P(n) désigne le nombre de nombres premiers plus petits que n, alors :

Ainsi, si l'on choisit un nombre de 500 chiffres au hasard, on a environ un chance sur ln(10⁵⁰⁰) de tomber sur un premier, c'est-à-dire environ une chance sur 1150. Tout cela reste très raisonnable!

D'autre part, il faut que, étant donné un entier n, on puisse rapidement déterminer s'il est premier ou non. Il faut donc des tests de primalité efficaces. Le plus rudimentaire est de prendre tour à tour tous les nombres entre 2 et racine de de n, et de vérifier s'ils divisent ou non n. Mais cet algorithme est bien trop naïf, car il nécessite 10²⁵⁰ calculs environ pour un nombre de 500 chiffres. Impossible! On a donc recours à d'autres tests, les tests de Solovay-Strassen et Miller-Rabin. Leur particularité est d'être des algorithmes probabilistes : ils répondent "n est probablement premier", avec une probabilité très grande (et que l'on peut ajuster). En général, en cryptographie, on se contente de nombres dont on sait qu'ils sont premiers avec une probabilité supérieure à 1-1/2¹⁰⁰.

Exemples

Les deux applets suivantes mettent en oeuvre les algorithmes précédents. La première teste si un nombre est premier : la réponse n'est jamais "ce nombre est premier", car le test est prob}abiliste, mais "ce nombre est pro|bablement premier". La seconde fabrique un nombre avec un nombre arbitraire de chiffres qui est probablement premier. Dans les deux cas, la sensibilité est $2^{-100}$, c'est-à-dire que le nombre est premier avec une probabilité supérieure ou égale à 0,999…99, avec 30 fois le chiffre 9!

Consulter aussi