A part peut-être Gauss, on a tous commencé par tester la primalité d'un entier de façon naïve. Rappelons que :

un entier n est premier si et seulement si ses seuls diviseurs sont 1 et n.

Il suffit donc de parcourir tous les entiers entre 2 et n-1, puis de tester si cet entier divise n. Bien sûr, il est facile d'améliorer cet algorithme : si n n'est pas premier, un de ces diviseurs est plus petit que . Il ne suffit donc que de tester les entiers entre 2 et . La complexité de l'algorithme (le nombre d'opérations qu'il doit faire) est donc en : Ceci est beaucoup plus grand que le C(log n)^k voulu : l'algorithme est ici exponentiel.

  Dans le même ordre d'idées, citons le crible d'Erathostène, qui permet de fabriquer tous les premiers entre 2 et n. Rappelons comment il fonctionne : on écrit tous les entiers entre 2 et n. Le premier entier écrit est 2 : il est premier, et on barre tous ses multiples. L'entier suivant non barré est 3 : il est premier et on barre tous ses multiples. On continue ainsi de suite, les entiers non barrés (et donc premiers) suivants sont : 5,7,...

  Les divisions et le crible d'Erathotène sont assez efficaces pour de petits entiers. Mais dès que ces entiers dépassent 50 chiffres, ils deviennent inutilisables : ils sont donc insuffisants puisque on a besoin couramment de fabriquer des nombres premiers à plusieurs milliers de chiffres. Pour de tels nombres, il faut totalement changer de méthode.

  Ces nombres de Mersenne ne sont pas tous premiers (ce serait trop faciles), et d'ailleurs il y en a relativement peu qui le sont effectivement : on ne sait même pas s'il y en a une infinité. En revanche, on dispose d'un test particulièrement efficace pour tester s'ils sont premiers, le test de Lucas-Lehmer : Avec des notations plus mathématiques, M_p est premier si, et seulement si, S_p=0 (mod M_p).

  Ce test est polynômial en le nombre de chiffres de M_p, puisqu'il faut calculer p termes de la suite, et que p est justement de l'ordre du nombre de chiffres de M_p. En outre, son implémentation informatique exploitant au mieux les particularités de l'arithmétique binaire est particulièrement efficace. C'est pourquoi le record du plus grand nombre premier jamais obtenu est toujours battu à l'aide de nombres de Mersenne. A titre d'exemple, M_13466917 possède 4 053946 chiffres décimaux!

  Pourtant, ces nombres premiers ne sont jamais utilisés pour la cryptographie. Ils sont bien trop particuliers, puisque l'on sait que (M_p+1) est une puissance de 2. Les chasseurs de code auraient alors beaucoup trop d'informations! Non, pour de telles applications, il n'y a rien de mieux qu'un nombre premier choisi totalement au hasard. Et pour cela, il n'y a rien de mieux que de tirer aléatoirement un nombre de 1000 chiffres, puis de tester s'il est premier. Nous revoici à notre point de départ....

Version imprimable