Pseŭdoprimo
En nombroteorio, pseŭdoprimo estas verŝajna primo (entjero, kiu havas propraĵojn komunajn al ĉiuj primoj), kiu estas ne reale primo. Pseŭdoprimoj povas esti klasifikitaj laŭ propraĵoj, kiujn ili kontentigas.
La plej grava klaso de pseŭdoprimoj venas de malgranda teoremo de Fermat kaj de ĉi tie estas nomataj kiel pseŭdoprimoj de Fermat. Ĉi tiu teoremo diras: se p estas primo kaj a estas interprimo al p, 1≤a<p, tiam ap-1-1 estas dividebla per p. Se nombro x estas ne primo, a estas interprimo al x, 1≤a<x kaj x dividas na ax-1-1, tiam x estas pseŭdoprimo al bazo a. Nombro x, kiu estas pseŭdoprimo por ĉiu valoro de a (a estu interprimo al x), estas nombro de Carmichael.
La plej malgranda pseŭdoprimo de Fermat por la bazo 2 estas 341. Ĝi estas ne primo pro tio, ke egalas al 11·31, sed ĝi verigas malgrandan teoremon de Fermat: 2340≡1 (mod 341).
La malofteco de ĉi tia pseŭdoprimoj havas gravajn praktikajn implikaciojn. Ekzemple publiko-ŝlosila ĉifrikaj algoritmoj tiaj kiel RSA postulas eblecon rapide trovi grandajn primojn. La kutima algoritmo por generi primojn estas generi hazardajn neparajn nombrojn kaj provi 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, do eblas uzi la multe pli rapidan kaj pli simplan primeca provo de Fermat.
Alia maniero estas uzi pli rafinitajn nociojn de pseŭdoprimeco, ekzemple forta pseŭdoprimoj aŭ eŭlero-jakobiaj pseŭdoprimoj, por kiu ne estas analogaj de nombroj de Carmichael. Ĉi tiu kondukas al probablecaj algoritmoj, ekzemple primeca provo de Solovay-Strassen kaj primeca provo de Miller-Rabin, kiuj produktas tion, kio estas sciata 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 |
Vidu ankaŭ[redakti | redakti fonton]
- Eŭlera pseŭdoprimo
- Eŭlero-jakobia pseŭdoprimo
- Pseŭdoprimo de Fibonacci
- Pseŭdoprimo de Lucas
- Pseŭdoprimo de Perrin
- Pseŭdoprimo de Somer-Lucas
- Forta pseŭdoprimo
- Forta pseŭdoprimo de Frobenius
- Forta pseŭdoprimo de Lucas
- Superflua forta pseŭdoprimo de Lucas