Liczby pseudopierwsze

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Liczba pseudopierwsza to liczba naturalna która spełnia niektóre własności charakteryzujące liczby pierwsze, ale sama nie jest liczbą pierwszą. Liczby pseudopierwsze można kategoryzować ze względu na własności jakie spełniają.

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