Pseŭdoprimo
En nombroteorio, pseŭdoprimo estas verŝajna primo (entjero, kiu havas econ validan por ĉiuj primoj), kiu, tamen, ne nepre estas primo. Pseŭdoprimoj estas klaseblaj laŭ ecoj, kiujn ili kontentigas.
La plej grava klaso de pseŭdoprimoj venas de malgranda teoremo de Fermat, kaj tiaj nombroj estas nomataj pseŭdoprimoj de Fermat. Laŭ tiu ĉi teoremo, se p estas primo kaj entjero a estas reciproke prima kun p, tiam ap-1-1 estas dividebla per p.
Entjero x reciproke prima kun entjero a, kiu estas divizoro de ax-1-1, nomiĝas pseŭdoprimo al bazo a.
Entjero x, kiu estas pseŭdoprimo por ĉiu valoro de a, kiu estas reciproke prima kun x, nomiĝas nombro de Carmichael.
La plej malgranda pseŭdoprimo de Fermat por la bazo 2 estas 341. Ĝi ne estas prima, ĉar ĝi egalas al 11·31, sed por ĝi validas la egalaĵo el la malgranda teoremo de Fermat: 2340≡1 (mod 341).
La malofteco de ĉi tiaj pseŭdoprimoj havas gravajn praktikajn implikaĵojn. Ekzemple, algoritmoj kiel RSA bazitaj sur publika ŝlosila ĉifrado postulas eblecon rapide trovi grandajn primojn. La kutima algoritmo por generi primojn estas generi hazardajn neparajn nombrojn kaj testi ilin por primeco. Tamen, determinismaj primecaj testoj estas malrapidaj. Se la uzanto konsentas toleri arbitre malgrandan ŝancon, ke la nombro trovita estas ne primo, sed pseŭdoprimo, tiam eblas uzi la multe pli rapidan kaj pli simplan primeco-teston de Fermat.
Alia maniero estas uzi pli rafinitajn nociojn de pseŭdoprimeco, ekzemple fortan pseŭdoprimecon aŭ eŭlero-jakobian pseŭdoprimecon, por kiuj ne ekzistas analogoj de nombroj de Carmichael. Ĉi tio kondukas al probablecaj algoritmoj kiel, ekzemple, primeco-testo de Solovay-Strassen kaj primeco-testo de Miller-Rabin, kiuj produktas tion, kio estas konata kiel industrio-gradaj primoj. Industrio-grada primo estas entjero, por kiu primeco ne estas rigore pruvita, sed estas nur arbitre malgranda probablo de komponigiteco.
Estas malfinie multaj pseŭdoprimoj al donita bazo (fakte, malfinie multaj nombroj de Carmichael), sed ili estas iom malofta. Estas nur 3 pseŭdoprimoj al bazo 2 pli sube de 1000, kaj estas nur 245 pli sube de miliono. Pseŭdoprimoj al bazo 2 estas nomataj ankaŭ kiel nombroj de Poulet aŭ iam nombroj de Sarrus. La nombroj de Poulet kaj nombroj de Carmichael (en grasa tiparo) supren ĝis 41041 estas:
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 |
Nombro de Poulet, ĉiuj el kies divizoroj d dividas na 2d-2, estas supernombro de Poulet. Estas malfinie multaj nombroj de Poulet, kiuj ne estas supernombroj de Poulet.
La unua plej malgrandaj pseŭdoprimoj por bazoj a≤200 estas donitaj en jena tabelo. La koloroj markigas la kvanton de primaj faktoroj.
a | plej malgranda p-p | a | plej malgranda p-p | a | plej malgranda p-p | a | plej malgranda 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 = 3³ | 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 |