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 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 Mp=2p-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 Sn en posant S1=4, et par la formule de récurrence : Sn=(Sn-1)2-2. Alors, pour p>2, on peut prouver que Mp est premier si et seulement si Mp divise Sp. Bien sûr, on réalise les calculs successifs des puissances seulement sur les restes!

  Les records des plus grands nombres premiers sont depuis des années réalisés à partir des nombres de Mersenne. A titre d'exemple, M13466917 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.


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(10500) 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 racinde de n, et vérifier s'ils divisent ou non n. Mais cet algorithme est bien trop naïf, car il nécessite 10250 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/2100.


Exemples



Et encore, dans la cryptographie expliquée...


Sommaire de la Cryptographie Expliquée - Plan du site - Retour à la BibM@th - Nous écrire - Tous droits réservés - Frédéric Bayart -