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³⁴⁰ ≡ 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⁴ · 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⁴	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.

Voir aussi

Lien externe

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

(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 ».

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

Nombre pseudo-premier