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: ap−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: 2340 ≡ 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.
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 = 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 = 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 = 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
Przypisy
↑Eric W.E.W.WeissteinEric W.E.W., Pseudoprime [online], mathworld.wolfram.com [dostęp 2022-02-15](ang.).strona główna serwisu