Nombre premier sûr

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un nombre premier sûr est un nombre premier, noté « S » dans cet article, de la forme « S = 2p + 1 », où « p » est lui-même un nombre premier. Autrement dit, un nombre premier S est sûr si (S – 1)/2 est aussi premier.

Réciproquement, un nombre premier « p » qui permet de construire un nombre premier sûr « 2p + 1 » est alors appelé nombre premier de Sophie Germain, noté « G » dans cet article ainsi que dans l'article connexe dédié à ces nombres premiers particuliers.

Listes de nombres premiers sûrs[modifier | modifier le code]

Les premiers nombres premiers sûrs, rangés dans les tableau 1 et tableau 2 ci-dessous, sont (voir suite A005385 de l'OEIS) :
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, 1 019, 1 187, 1 283, 1 307, 1 319, 1 367, 1 439, 1 487, 1 523, 1 619, 1 823, 1 907, 2 027, 2 039, 2 063

Nombres premiers sûrs compris entre 0 et 127[modifier | modifier le code]

Dans le « tableau 1 » ci-dessous, les nombres premiers sûrs notés « S », construits à partir des entiers de l'intervalle [0, 127], sont tous présentés en gras dans les lignes « S », ordonnés sous la forme « Si= » et associés à leur antécédent nombre premier de Sophie Germain « Gi » inscrit dans la cellule immédiatement au-dessus. Ils sont également signalés par leur repère « Si » inscrit en gras sous leur occurrence dans la liste complète des nombres premiers « p ».

Tableau 1 : Tous les nombres premiers « p » compris entre 0 et 127, dont les premiers de Sophie Germain « G » ; leurs premiers sûrs résultants « S = 2.G + 1 ».
décades
d'entiers n
première
décade
deuxième
décade
troisième
décade
quatrième
décade
cinquième
décade
sixième
décade
septième
décade
huitième
décade
neuvième
décade
dixième
décade
onzième
décade
douzième
décade
treizième
décade
entiers n = 00 à 09 10 à 19 20 à 29 30 à 39 40 à 49 50 à 59 60 à 69 70 à 79 80 à 89 90 à 99 100 à 109 110 à 119 120 à 127
premiers dont Gi et Si -[1] 11
G4 et S3
23
G5 et S4
31 41
G7
53
G8
61 71 83
G9 et S7
97 101 113
G11
127
S -[1] S4=23 S5=47 - S7=83 S8=107 - - S9=167 - - S11=227 -
premiers dont Gi et Si -[2] 13 29
G6
37 43 59
S6
67 73 89
G10
103   (131)
(G12)
S -[2] - S6=59 - - - - - S10=179 - (S12=263)
premiers dont Gi et Si 2
G1
17 47
S5
79 107
S8
(173)
(G13)
S S1=5 - - - (S13=347)
premiers dont Gi et Si 3
G2
19 109 (179)
(S10 et G14)
S S2=7 - - (S14=359)
premiers dont Gi et Si 5
G3 et S1
(191)
(G15)
S S3=11 (S15=383)
premiers dont Gi et Si 7
S2
(233)
(G16)
S - (S16=467)
premiers dont Gi et Si
S
sous-totaux des p, Gi, Si, par décade 4 p
3 G
2 S
4 p
1 G
1 S
2 p
2 G
1 S
2 p
0 G
0 S
3 p
1 G
1 S
2 p
1 G
1 S
2 p
0 G
0 S
3 p
0 G
0 S
2 p
2 G
1 S
1 p
0 G
0 S
4 p
0 G
1 S
1 p
1 G
0 S
1 p
0 G
0 S
Totaux et ratios A - A1 -
25 soit 25 % de nombres premiers « p » parmi les 100 entiers « n » compris entre 0 et 99, à comparer à :

10 soit 10 % de nombres premiers de Sophie Germain « G » parmi les 100 entiers « n » compris entre 0 et 99.
7 soit 7 % de nombres premiers sûrs « S » parmi les 100 entiers « n » compris entre 0 et 99.
- A2 -
46 soit 23 % de nombres premiers « p » parmi les 200 entiers « n » compris entre 0 et 199, à comparer à :
15 soit 7,5 % de nombres premiers de Sophie Germain « G » parmi les 200 entiers « n » compris entre 0 et 199.
10 soit 5 % de nombres premiers sûrs « S » dilués parmi les 200 entiers « n » compris entre 0 et 199.

 
Totaux et ratios B - B1 -
31 soit 24 % de nombres premiers « p » parmi les 128 entiers « n » compris entre 0 et 127, à comparer à :

11 soit 8,6 % de nombres premiers de Sophie Germain « G » parmi les 128 entiers « n » compris entre 0 et 127.
8 soit 6,25 % de nombres premiers sûrs « S » parmi les 128 entiers « n » compris entre 0 et 127.
- B2 -
54 soit 21 % de nombres premiers « p » parmi les 256 entiers « n » compris entre 0 et 255, à comparer à :
18 soit 7 % de nombres premiers de Sophie Germain « G » parmi les 256 entiers « n » compris entre 0 et 255[3].
11 soit 4,3 % de nombres premiers sûrs « S » dilués parmi les 256 entiers « n » compris entre 0 et 255.

Les seize premiers nombres premiers sûrs, classés dans le tableau 1 ci-dessus sont également rappelés ci-après (voir suite A005385 de l'OEIS) :
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467.
À partir de « (131) », les nombres premiers ordinaires « p » intermédiaires ne sont plus indiqués.

Nombres premiers sûrs compris entre 0 et 1023[modifier | modifier le code]

Dans le « tableau 2 » ci-dessous, tous les nombres premiers sûrs construits à partir des nombres premiers de l'intervalle [0, 1023] sont présentés en gras dans les lignes marquées « S » au-dessous de leur antécédent « Gi ». Ils sont également signalés par leur repère « Si » inscrit en gras sous leur occurrence dans la liste complète des nombres premiers « p ».

Tableau 2 : Tous les nombres premiers « p » compris entre 0 et 1023, dont les premiers de Sophie Germain « G » ; leurs premiers sûrs résultants « S = 2.G + 1 ».
centaines d'entiers n premier
cent
deuxième
cent
troisième
cent
quatrième
cent
cinquième
cent
sixième
cent
septième
cent
huitième
cent
neuvième
cent
dixième
cent
+ 23

1023
Typ Qté 00 10 20 00 10 20 00 10 00 10 00 10 00 10 00 10 00 10 00 10 00 10 00
p
Gi
Si
01 2
G1
31 73 101 151 199 211 269 307 367 401 461 503

S18
577 601 659
G30
701 769 809
G35
863

S23
907 977 1009
S   S1=5 - - - - - - - - - - - - - - S30=1319 - - S35=1619 - - - -
p
Gi
Si
02 3
G2
37 79 103 157   223 271 311 373 409 463 509
G26
587

S20
607 661 709 773 811 877 911
G36
983

S25
1013
G38
S   S2=7 - - - -   - - - - - - S26=1019 - - - - - - - S36=1823 - S38=2027
p
Gi
Si
03 5
G3
S1
41
G7
83
G9
S7
107

S8
163   227

S11
277 313 379 419
G22
467

S16
521 593
G27
613 673 719
G32
S21
787 821 881 919 991 1019
G39
S26
S   S3=11 S7=83 S9=167 - -   - - - - S22=839 - - S27=1187 - - S32=1439 - - - - - S39=2039
p
Gi
Si
04 7

S2
43 89
G10
109 167

S9
  229 281
G19
317 383

S15
421 479

S17
523 599 617 677 727 797 823 883 929 997 1021
S   - - S10=179 - -   - S19=563 - - - - - - - - - - - - - - -
p
Gi
Si
05 11
G4
S3
47

S5
97 113
G11
173
G13
  233
G16
283 331 389 431
G23
487 541   619 683
G31
733   827 887

S24
937   (1031)
(G40)
S   S4=23 - - S11=227 S13=347   S16=467 - - - S23=863 - -   - S31=1367 -   - - -   (S40= 2063)
p
Gi
Si
06 13 53
G8
127 179
G14
S10
  239
G17
293
G20
337 397 433 491
G25
547   631 691 739   829   941   (1049)
(G41)
S   - S8=107   - S14=359   S17=479 S20=587 - - - S25=983 -   - - -   - -   (S41= 2099)
p
Gi
Si
07 17 59

S6
  131
G12
181   241   347

S13
  439 499 557   641
G28
  743
G33
  839

S22
  947   (1103)
(G42)
S   - -   S12=263 -   -   -   - - -   S28=1283   S33=1487   -   -   (S42= 2207)
p
Gi
Si
08 19 61   137 191
G15
  251
G18
  349   443
G24
  563

S19
  643   751   853   953
G37
  (1223)
(G43)
S   - -   - S15=383 S18=503   -   S24=887   -   -   -   -   S37=1907   (S43= 2447)
p
Gi
Si
09 23
G5
S4
67   139 193   257   353   449   569   647   757   857   967   (1229)
(G44)
S   S5=47 -   - -   -   -   -   -   -   -   -   -   (S44= 2459)
p
Gi
Si
10 29
G6
71   149 197   263

S12
  359
G21
S14
  457   571   653
G29
  761
G34
  859   971   (1289)
(G45)
S   S6=59 -   - -   -   S21=759   -   -   S29=1307   S34=1523   -   -   (S45= 2579)
ss-totaux et ratios par cent 25 p → 25 %
10 G → 10 %
7 S → 7 %
21 p → 21 %
5 G → 5 %
3 S → 3 %
16 p → 16 %
5 G → 5 %
2 S → 2 %
16 p → 16 %
1 G → 1 %
3 S → 3 %
17 p → 17 %
4 G → 4 %
2 S → 2 %
14 p → 14 %
2 G → 2 %
3 S → 3 %
16 p → 16 %
4 G → 4 %
0 S → 0 %
14 p → 14 %
3 G → 3 %
1 S → 1 %
15 p → 15 %
1 G → 1 %
3 S → 3 %
14 p → 14 %
2 G → 2 %
1 S → 1 %
4 p
2 G
1 S
Totaux et ratios A - A1 -
168 soit 16,8 % de nombres premiers « p » parmi les 1000 entiers « n » compris entre 0 et 999, à comparer à :

37 soit 3,70 % de nombres premiers de Sophie Germain « G » parmi les 1000 entiers « n » compris entre 0 et 999.
25 soit 2,50 % de nombres premiers sûrs « S » parmi les 1000 entiers « n » compris entre 0 et 999.
- A2 -
303 soit 15,2 % de nombres premiers « p » parmi les 2000 entiers « n » compris entre 0 et 1999, à comparer à :
? soit ? % de nombres premiers de Sophie Germain « G » parmi les 2000 entiers « n » compris entre 0 et 1999.
37 soit 1,85 % de nombres premiers sûrs « S » dilués parmi les 2000 entiers « n » compris entre 0 et 1999.

 
Totaux et ratios B - B1 -
172 soit 16,8 % de nombres premiers « p » parmi les 1024 entiers « n » compris entre 0 et 1023, à comparer à :

39 soit 3,81 % de nombres premiers de Sophie Germain « G » parmi les 1024 entiers « n » compris entre 0 et 1023.
26 soit 2,54 % de nombres premiers sûrs « S » parmi les 1024 entiers « n » compris entre 0 et 1023.
- B2 -
309 soit 15,1 % de nombres premiers « p » parmi les 2048 entiers « n » compris entre 0 et 2047, à comparer à :
? soit ? % de nombres premiers de Sophie Germain « G » parmi les 2048 entiers « n » compris entre 0 et 2047.
39 soit 1,90 % de nombres premiers sûrs « S » dilués parmi les 2048 entiers « n » compris entre 0 et 2047.

Les quarante-cinq nombres premiers sûrs classés dans le tableau 2 ci-dessus sont (voir suite A005385 de l'OEIS) :
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, 1 019, 1 187, 1 283, 1 307, 1 319, 1 367, 1 439, 1 487, 1 523, 1 619, 1 823, 1 907, 2 027, 2 039, 2 063, 2 099, 2 207, 2 447, 2 459, 2 579
À partir de « (1031) », les nombres premiers ordinaires « p » intermédiaires ne sont plus indiqués.

Utilité des nombres premiers sûrs[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. 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.

Propriétés des nombres premiers sûrs[modifier | modifier le code]

Test de primalité[modifier | modifier le code]

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.

Premier sûr de Fermat[modifier | modifier le code]

À 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.

Premier sûr de Mersenne[modifier | modifier le code]

À 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 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.

Premier sûr et chaîne de Cunningham[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

  1. a et b Le nombre « 0 » n'est pas premier car il est divisible par plus de deux nombres, à savoir tous les autres entiers ; de plus il n'est pas divisible par lui-même. Par conséquent « 1 » = 2x0 + 1 n'est pas un nombre premier sûr.
  2. a et b Le nombre « 1 » n'est pas premier car il ne possède qu'un seul diviseur. Par conséquent « 3 » = 2x1 + 1 n'est pas un nombre premier sûr.
  3. Les deux nombres premiers de Sophie Germain complémentaires, inférieurs à 256, qui n'apparaissent pas dans le tableau sont : G17=239 et G18=251.