Liczby pseudopierwsze

Liczby pseudopierwsze – liczby naturalne, które spełniają niektóre własności charakteryzujące liczby pierwsze, ale same nie są liczbami pierwszymi^[1].

Najbardziej istotną kategorią są liczby pseudopierwsze Fermata, które spełniają warunki małego twierdzenia Fermata: a^p−1 − 1 jest podzielne przez p dla pewnego a^[2]. Jeśli p nie jest pierwsza, to jest nazywana wtedy pseudopierwszą przy podstawie a. Liczba x, która jest pseudopierwsza przy każdej podstawie względnie pierwszej z x jest nazywana liczbą Carmichaela.

Najmniejszą liczbą pseudopierwszą przy podstawie 2 jest 341. Nie jest to liczba pierwsza, bo 341 = 11 • 31, ale spełnia warunki twierdzenia: 2³⁴⁰ ≡ 1 (mod 341).

Rzadkość występowania takich liczb ma znaczenie praktyczne. Przykładowo algorytmy kryptografii asymetrycznej takie jak RSA wymagają szybkiego znajdywania kilkusetcyfrowych liczb pierwszych. Standardowo generuje się w nich losową liczbę nieparzystą i testuje czy jest pierwsza. Ponieważ deterministyczne sprawdzanie tego trwałoby długo, korzysta się zwykle z probabilistycznych testów takich jak test pierwszości Fermata.

Innymi kategoriami liczb pseudopierwszych są liczby silnie pseudopierwsze i liczby pseudopierwsze Eulera-Jacobiego, dla których nie ma analogów liczb Carmichaela. Odpowiadają im algorytmy testowania Solovaya-Strassena i Millera-Rabina.

Istnieje nieskończenie wiele liczb pseudopierwszych przy danej podstawie (istnieje nawet nieskończenie wiele liczb Carmichaela), ale są one dosyć rzadkie. Przykładowo istnieją tylko 3 pseudopierwsze liczby przy podstawie 2 mniejsze od 1000, i tylko 245 takich liczb mniejszych od miliona. Liczby pseudopierwsze przy podstawie 2 nazywane są czasem liczbami Pouleta. Poniższa tabela zawiera pierwszych 50 takich liczb, z wytłuszczeniem tych, które są dodatkowo liczbami Carmichaela:

n		n		n		n		n
1	341 = 11 • 31	11	2821 = 7 • 13 • 31	21	8481 = 3 • 11 • 257	31	15709 = 23 • 683	41	30121 = 7 • 13 • 331
2	561 = 3 • 11 • 17	12	3277 = 29 • 113	22	8911 = 7 • 19 • 67	32	15841 = 7 • 31 • 73	42	30889 = 17 • 23 • 79
3	645 = 3 • 5 • 43	13	4033 = 37 • 109	23	10261 = 31 • 331	33	16705 = 5 • 13 • 257	43	31417 = 89 • 353
4	1105 = 5 • 13 • 17	14	4369 = 17 • 257	24	10585 = 5 • 29 • 73	34	18705 = 3 • 5 • 29 • 43	44	31609 = 73 • 433
5	1387 = 19 • 73	15	4371 = 3 • 31 • 47	25	11305 = 5 • 7 • 17 • 19	35	18721 = 97 • 193	45	31621 = 103 • 307
6	1729 = 7 • 13 • 19	16	4681 = 31 • 151	26	12801 = 3 • 17 • 251	36	19951 = 71 • 281	46	33153 = 3 • 43 • 257
7	1905 = 3 • 5 • 127	17	5461 = 43 • 127	27	13741 = 7 • 13 • 151	37	23001 = 3 • 11 • 17 • 41	47	34945 = 5 • 29 • 241
8	2047 = 23 • 89	18	6601 = 7 • 23 • 41	28	13747 = 59 • 233	38	23377 = 97 • 241	48	35333 = 89 • 397
9	2465 = 5 • 17 • 29	19	7957 = 73 • 109	29	13981 = 11 • 31 • 41	39	25761 = 3 • 31 • 277	49	39865 = 5 • 7 • 17 • 67
10	2701 = 37 • 73	20	8321 = 53 • 157	30	14491 = 43 • 337	40	29341 = 13 • 37 • 61	50	41041 = 7 • 11 • 13 • 41

Poniższa tabela przedstawia najmniejsze liczby pseudopierwsze przy podstawach a ≤ 200. Kolorami zaznaczono ilość czynników pierwszych.

a	smallest p-p	a	smallest p-p	a	smallest p-p	a	smallest p-p
		51	65 = 5 • 13	101	175 = 5² • 7	151	175 = 5² • 7
2	341 = 11 • 13	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 = 5³	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

Przypisy

↑ Eric W.E.W. Weisstein Eric W.E.W., Pseudoprime, mathworld.wolfram.com [dostęp 2022-02-15] (ang.).
↑ Eric W.E.W. Weisstein Eric W.E.W., Fermat Pseudoprime, mathworld.wolfram.com [dostęp 2022-02-15] (ang.).

Linki zewnętrzne

MikołajM. Rotkiewicz MikołajM., Liczby pseudopierwsze, [w:] pismo „Delta” [online], deltami.edu.pl, marzec 2022, ISSN 0137-3005 [dostęp 2022-03-15] (pol.).

[1] Eric W.E.W. Weisstein Eric W.E.W., Pseudoprime, mathworld.wolfram.com [dostęp 2022-02-15] (ang.).

[2] Eric W.E.W. Weisstein Eric W.E.W., Fermat Pseudoprime, mathworld.wolfram.com [dostęp 2022-02-15] (ang.).

[1]

[2]

Navigation

Nawigacja

Portale tematyczne

Liczby pseudopierwsze

Przypisy

Linki zewnętrzne