Wikipedia

Liczby pseudopierwsze

liczby naturalne o niektórych własnościach liczb pierwszych

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.

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 = 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

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

Linki zewnętrzne

edytuj
Źródło: „https://pl.wiki.x.io/w/index.php?title=Liczby_pseudopierwsze&oldid=75120038”