Nombre premier sûr
Un article de Wikipédia, l'encyclopédie libre.
Un nombre premier sûr est un nombre premier de la forme 2p + 1, où p est aussi un nombre premier. Réciproquement, le nombre premier p est un nombre premier de Sophie Germain. Les premiers nombres premiers sûrs sont :
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907
Ces nombres premiers sont appelés « sûrs » à cause de leur application dans les algorithmes de cryptologie tels que l'algorithme de Diffie-Hellman. Il doit bien sûr être noté qu'aucun nombre premier inférieur à 1050 n'est réellement sécurisé du fait que n'importe quel ordinateur moderne avec un algorithme adapté peut déterminer leur primalité en un temps raisonnable. Mais les petits nombres premiers sûrs sont encore très utiles pour apprendre les principes de ces systèmes. Il n'existe pas de test de primalité spécial pour les nombres premiers sûrs comme ce qui existe pour les nombres premiers de Fermat et les nombres premiers de Mersenne.
À part 5, il n'y a pas de nombre premier de Fermat qui soit aussi un nombre premier sûr. En effet, si F est un nombre premier de Fermat, alors (F - 1)/2 est une puissance de deux. Pour être premier, ce nombre doit être égal à 2. Donc F=5.
À part 7, il n'y a pas de nombre premier de Mersenne qui soit aussi un nombre premier sûr. La démonstration est un petit peu plus compliquée, mais encore dans le domaine de l'algèbre de base. Il faut savoir que p doit être premier pour que 2p - 1 puisse l'être aussi. Pour que 2p-1 soit un nombre premier sûr, il faut que les deux nombres 2p-1 et ((2p - 1) - 1)/2 = 2p - 1 - 1 soient des nombres de Mersenne. Donc p et p-1 doivent être premiers tous les deux. Donc p=3 et 2p - 1 = 7.
Comme chaque terme, excepté le dernier, d'une chaîne de Cunningham de première espèce est un nombre premier de Sophie Germain, donc chaque terme excepté le premier d'une telle chaîne est un nombre premier sûr. Les nombres premiers sûrs finissant par 7, de la forme 10n + 7, sont les derniers termes dans de telles chaînes quand ils arrivent, puisque 2(10n + 7) + 1 = 20n + 15.
