Aller au contenu

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 lui-même un nombre premier (p est alors appelé un nombre premier de Sophie Germain).

Les nombres premiers sûrs sont : 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587etc. (suite A005385 de l'OEIS).

Les plus petits sont classés dans les deux tableaux ci-dessous[Interprétation personnelle ?], ordonnés sous la forme Si inscrite en gras sous leur occurrence dans la liste complète des nombres premiers p, et associés à leur nombre de Sophie Germain Gi inscrit dans la cellule immédiatement au-dessus.

Applications

[modifier | modifier le code]

Ces nombres premiers sont appelés « sûrs » à cause de leur application dans les algorithmes de cryptologie tels que l'algorithme de Diffie-Hellman. Cependant, 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.

Autres propriétés

[modifier | modifier le code]

Il n'existe pas de test de primalité spécial pour les nombres premiers sûrs comme ceux qui existent 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 2. 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 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.

De même que chaque terme, excepté le dernier, d'une chaîne de Cunningham de première espèce est un nombre premier de Sophie Germain, 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.

Référence

[modifier | modifier le code]
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Safe prime » (voir la liste des auteurs).