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 [online], mathworld.wolfram.com [dostęp 2022-02-15] (ang.).
↑ Eric W.E.W. Weisstein Eric W.E.W., Fermat Pseudoprime [online], mathworld.wolfram.com [dostęp 2022-02-15] (ang.).

Linki zewnętrzne

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

Teoria liczb

ogólne typy liczb

naturalne
całkowite
- parzyste i nieparzyste
wymierne
- ułamki egipskie
rzeczywiste
- dodatnie i ujemne
- niewymierne

relacje

podzielność	dzielnik i wielokrotność cechy podzielności
zdefiniowane podzielnością	czynnik pierwszy względna pierwszość kongruencje liczby towarzyskie zaprzyjaźnione

działania

liczby pierwsze

podstawy	lemat Euklidesa liczby złożone
testy pierwszości	AKS APR cyklotomiczny ECPP Fermata Lucasa-Lehmera Millera-Rabina Solovaya-Strassena certyfikat pierwszości
sita	Eratostenesa Atkina
faktoryzacja	zasadnicze twierdzenie arytmetyki algorytmy Fermata rho Pollarda Shora GNFS metoda sita liczbowego sito kwadratowe
hipotezy	Gilbreatha Goldbacha słaba liczb pierwszych bliźniaczych Pólyi

równania
diofantyczne

liniowe	tożsamość Bézouta
kwadratowe	równanie Pitagorasa (trójek pitagorejskich) równanie Pella
wyższych stopni	równanie Fermata (wielkie twierdzenie Fermata) równanie Catalana (twierdzenie Mihăilescu)
układy równań	cegiełka Eulera prostopadłościan idealny
powiązane zagadnienia	dziesiąty problem Hilberta

twierdzenia
arytmetyki modularnej

inne zagadnienia

twierdzenia limitacyjne

pierwsze Gödla o niezupełności

Ciągi liczbowe

pojęcia
definiujące

ciągi ogólne	funkcja dziedzina liczby naturalne podzbiór
ciągi liczbowe	przeciwdziedzina liczba

typy ciągów

ogólne	skończone para uporządkowana krotka lista nieskończone różnowartościowe permutacje ograniczone okresowe monotoniczne niemalejące nierosnące rosnące superrosnące malejące stałe arytmetyczne geometryczne ułamki dziesiętne
nieskończone	nieograniczone Cauchy’ego zbieżne i rozbieżne rozbieżne do nieskończoności sumowalne metodą Cesàro szeregi liczbowe geometryczne harmoniczne naprzemienne Dirichleta ułamki dziesiętne nieskończone nieskończone iloczyny liczbowe ułamki łańcuchowe funkcje arytmetyczne addytywne multyplikatywne

przykłady ciągów
liczb naturalnych

niemalejące

inne

inne przykłady
ciągów liczb

twierdzenia

o granicach	Bolzana-Weierstrassa o dwóch ciągach o trzech ciągach o zbieżności ciągu monotonicznego o zbieżności średnich Stolza
inne	o ciągach jednomonotonicznych nierówność Czebyszewa