Nombre pseudo-premier
# Nombre pseudo-premier

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

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 $a^{p-1}-1$ est divisible par p. Si un entier n > 1 divise $a^{n-1}-1$ 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 $a^{n-1}-1$» impliquant « n divise $a^{n}-a$ », 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 : $2^{340}$ ≡ 1 (mod 341).

Il existe une infinité de nombres pseudo-premiers de Fermat (même 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 = $2^4$ · 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 = $3^4$ | 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

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.

