Aller au contenu

Nombre pseudo-premier

Un article de Wikipédia, l'encyclopédie libre.

Un nombre pseudo-premier est un nombre premier probable (un entier naturel qui partage une propriété commune à tous les nombres premiers) qui n'est en fait pas premier. Les nombres pseudo-premiers peuvent être classés selon la propriété qu'ils satisfont.

Nombre pseudo-premier de Fermat

[modifier | modifier le code]

La plus importante classe de nombres pseudo-premiers provient du petit théorème de Fermat et donc, sont appelés les pseudo-premiers de Fermat. Ce théorème énonce que si p est premier et a est premier avec p, alors est divisible par p. Si un entier n > 1 divise et n'est pas premier, alors n est appelé un pseudo-premier de base a (notons qu'il est forcément premier avec a). Un nombre n pseudo-premier pour toutes les valeurs de a qui sont premières avec n est appelé nombre de Carmichael.

La propriété « n divise » impliquant « n divise  », un entier n > 1 vérifiant cette dernière propriété pour une base a > 1 quelconque est dit faiblement pseudo-premier de base a. Lorsque a et n sont premiers entre eux, les deux notions se confondent.

Le plus petit nombre pseudo-premier de Fermat pour la base 2 est 341. Il n'est pas premier, car il est égal à 11 × 31, mais il satisfait la conclusion du petit théorème de Fermat : 2340 ≡ 1 (mod 341).

Il existe une infinité de nombres pseudo-premiers de Fermat (ainsi qu'une infinité de nombres de Carmichael), mais ils sont plutôt rares. Il existe seulement trois pseudo-premiers de base 2 inférieurs à 1 000 et 245 inférieurs à 1 000 000. Les nombres faiblement pseudo-premiers de base 2 sont les nombres de Poulet (suite A001567 de l'OEIS). Le tableau suivant donne les cinquante premiers nombres de Poulet, ainsi que les nombres de Carmichael en gras :

n n n n n
1 341 = 11 · 31 11 2 821 = 7 · 13 · 31 21 8 481 = 3 · 11 · 257 31 15 709 = 23 · 683 41 30 121 = 7 · 13 · 331
2 561 = 3 · 11 · 17 12 3 277 = 29 · 113 22 8 911 = 7 · 19 · 67 32 15 841 = 7 · 31 · 73 42 30 889 = 17 · 23 · 79
3 645 = 3 · 5 · 43 13 4 033 = 37 · 109 23 10 261 = 31 · 331 33 16 705 = 5 · 13 · 257 43 31 417 = 89 · 353
4 1 105 = 5 · 13 · 17 14 4 369 = 17 · 257 24 10 585 = 5 · 29 · 73 34 18 705 = 3 · 5 · 29 · 43 44 31 609 = 73 · 433
5 1 387 = 19 · 73 15 4 371 = 3 · 31 · 47 25 11 305 = 5 · 7 · 17 · 19 35 18 721 = 97 · 193 45 31 621 = 103 · 307
6 1 729 = 7 · 13 · 19 16 4 681 = 31 · 151 26 12 801 = 3 · 17 · 251 36 19 951 = 71 · 281 46 33 153 = 3 · 43 · 257
7 1 905 = 3 · 5 · 127 17 5 461 = 43 · 127 27 13 741 = 7 · 13 · 151 37 23 001 = 3 · 11 · 17 · 41 47 34 945 = 5 · 29 · 241
8 2 047 = 23 · 89 18 6 601 = 7 · 23 · 41 28 13 747 = 59 · 233 38 23 377 = 97 · 241 48 35 333 = 89 · 397
9 2 465 = 5 · 17 · 29 19 7 957 = 73 · 109 29 13 981 = 11 · 31 · 41 39 25 761 = 3 · 31 · 277 49 39 865 = 5 · 7 · 17 · 67
10 2 701 = 37 · 73 20 8 321 = 53 · 157 30 14 491 = 43 · 337 40 29 341 = 13 · 37 · 61 50 41 041 = 7 · 11 · 13 · 41

Un nombre de Poulet dont tous les diviseurs d divisent 2 d – 2 est appelé supernombre de Poulet. Il existe une infinité de nombres de Poulet qui ne sont pas des supernombres de Poulet.

Les premiers plus petits nombres pseudo-premiers et strictement supérieurs à leur base a, pour les bases ≤ 200 sont donnés dans la table suivante ; les couleurs indiquent le nombre de facteurs premiers.

a le plus petit p-p a le plus petit p-p a le plus petit p-p a le plus petit p-p
    51 65 = 5 · 13 101 175 = 5² · 7 151 175 = 5² · 7
2 341 = 11 · 31 52 85 = 5 · 17 102 133 = 7 · 19 152 153 = 3² · 17
3 91 = 7 · 13 53 65 = 5 · 13 103 133 = 7 · 19 153 209 = 11 · 19
4 15 = 3 · 5 54 55 = 5 · 11 104 105 = 3 · 5 · 7 154 155 = 5 · 31
5 124 = 2² · 31 55 63 = 3² · 7 105 451 = 11 · 41 155 231 = 3 · 7 · 11
6 35 = 5 · 7 56 57 = 3 · 19 106 133 = 7 · 19 156 217 = 7 · 31
7 25 = 5² 57 65 = 5 · 13 107 133 = 7 · 19 157 186 = 2 · 3 · 31
8 9 = 3² 58 133 = 7 · 19 108 341 = 11 · 31 158 159 = 3 · 53
9 28 = 2² · 7 59 87 = 3 · 29 109 117 = 3² · 13 159 247 = 13 · 19
10 33 = 3 · 11 60 341 = 11 · 31 110 111 = 3 · 37 160 161 = 7 · 23
11 15 = 3 · 5 61 91 = 7 · 13 111 190 = 2 · 5 · 19 161 190 = 2 · 5 · 19
12 65 = 5 · 13 62 63 = 3² · 7 112 121 = 11² 162 481 = 13 · 37
13 21 = 3 · 7 63 341 = 11 · 31 113 133 = 7 · 19 163 186 = 2 · 3 · 31
14 15 = 3 · 5 64 65 = 5 · 13 114 115 = 5 · 23 164 165 = 3 · 5 · 11
15 341 =" 11" · 13 65 112 = 24 · 7 115 133 = 7 · 19 165 172 = 2² · 43
16 51 = 3 · 17 66 91 = 7 · 13 116 117 = 3² · 13 166 301 = 7 · 43
17 45 = 3² · 5 67 85 = 5 · 17 117 145 = 5 · 29 167 231 = 3 · 7 · 11
18 25 = 5² 68 69 = 3 · 23 118 119 = 7 · 17 168 169 = 13²
19 45 = 3² · 5 69 85 = 5 · 17 119 177 = 3 · 59 169 231 = 3 · 7 · 11
20 21 = 3 · 7 70 169 = 13² 120 121 = 11² 170 171 = 3² · 19
21 55 = 5 · 11 71 105 = 3 · 5 · 7 121 133 = 7 · 19 171 215 = 5 · 43
22 69 = 3 · 23 72 85 = 5 · 17 122 123 = 3 · 41 172 247 = 13 · 19
23 33 = 3 · 11 73 111 = 3 · 37 123 217 = 7 · 31 173 205 = 5 · 41
24 25 = 5² 74 75 = 3 · 5² 124 125 = 3³ 174 175 = 5² · 7
25 28 = 2² · 7 75 91 = 7 · 13 125 133 = 7 · 19 175 319 = 11 · 19
26 27 = 3³ 76 77 = 7 · 11 126 247 = 13 · 19 176 177 = 3 · 59
27 65 = 5 · 13 77 247 = 13 · 19 127 153 = 3² · 17 177 196 = 2² · 7²
28 45 = 3² · 5 78 341 = 11 · 31 128 129 = 3 · 43 178 247 = 13 · 19
29 35 = 5 · 7 79 91 = 7 · 13 129 217 = 7 · 31 179 185 = 5 · 37
30 49 = 7² 80 81 = 34 130 217 = 7 · 31 180 217 = 7 · 31
31 49 = 7² 81 85 = 5 · 17 131 143 = 11 · 13 181 195 = 3 · 5 · 13
32 33 = 3 · 11 82 91 = 7 · 13 132 133 = 7 · 19 182 183 = 3 · 61
33 85 = 5 · 17 83 105 = 3 · 5 · 7 133 145 = 5 · 29 183 221 = 13 · 17
34 35 = 5 · 7 84 85 = 5 · 17 134 135 = 3³ · 5 184 185 = 5 · 37
35 51 = 3 · 17 85 129 = 3 · 43 135 221 = 13 · 17 185 217 = 7 · 31
36 91 = 7 · 13 86 87 = 3 · 29 136 265 = 5 · 53 186 187 = 11 · 17
37 45 = 3² · 5 87 91 = 7 · 13 137 148 = 2² · 37 187 217 = 7 · 31
38 39 = 3 · 13 88 91 = 7 · 13 138 259 = 7 · 37 188 189 = 3³ · 7
39 95 = 5 · 19 89 99 = 3² · 11 139 161 = 7 · 23 189 235 = 5 · 47
40 91 = 7 · 13 90 91 = 7 · 13 140 141 = 3 · 47 190 231 = 3 · 7 · 11
41 105 = 3 · 5 · 7 91 115 = 5 · 23 141 355 = 5 · 71 191 217 = 7 · 31
42 205 = 5 · 41 92 93 = 3 · 31 142 143 = 11 · 13 192 217 = 7 · 31
43 77 = 7 · 11 93 301 = 7 · 43 143 213 = 3 · 71 193 276 = 2² · 3 · 23
44 45 = 3² · 5 94 95 = 5 · 19 144 145 = 5 · 29 194 195 = 3 · 5 · 13
45 76 = 2² · 19 95 141 = 3 · 47 145 153 = 3² · 17 195 259 = 7 · 37
46 133 = 7 · 19 96 133 = 7 · 19 146 147 = 3 · 7² 196 205 = 5 · 41
47 65 = 5 · 13 97 105 = 3 · 5 · 7 147 169 = 13² 197 231 = 3 · 7 · 11
48 49 = 7² 98 99 = 3² · 11 148 231 = 3 · 7 · 11 198 247 = 13 · 19
49 66 = 2 · 3 · 11 99 145 = 5 · 29 149 175 = 5² · 7 199 225 = 3² · 5²
50 51 = 3 · 17 100 153 = 3² · 17 150 169 = 13² 200 201 = 3 · 67

Applications

[modifier | modifier le code]

Il existe des applications en cryptographie asymétrique telles que RSA qui ont besoin de grands nombres premiers. L'algorithme commun pour générer les nombres premiers consiste en plusieurs générations de nombres aléatoires impairs et des tests concernant leur primalité. Néanmoins, les tests de primalité déterministes sont lents. Si l'utilisateur ne requiert pas que le test soit complètement exact (autrement dit, il devrait tolérer une très petite chance qu'un nombre composé soit déclaré premier), il existe des algorithmes probabilistes rapides comme le test de primalité de Fermat, le test de primalité de Solovay-Strassen, et le test de primalité de Miller-Rabin.

Références

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

puis renommé « Fermat pseudoprime ».

Articles connexes

[modifier | modifier le code]

Lien externe

[modifier | modifier le code]

Nombres pseudo-premiers forts de base 2 (suite A001262 de l'OEIS)