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 · 3312 561 = 3 · 11 · 17 12 3277 = 29 · 113 22 8911 = 7 · 19 · 67 32 15841 = 7 · 31 · 73 42 30889 = 17 · 23 · 793 645 = 3 · 5 · 43 13 4033 = 37 · 109 23 10261 = 31 · 331 33 16705 = 5 · 13 · 257 43 31417 = 89 · 3534 1105 = 5 · 13 · 17 14 4369 = 17 · 257 24 10585 = 5 · 29 · 73 34 18705 = 3 · 5 · 29 · 43 44 31609 = 73 · 4335 1387 = 19 · 73 15 4371 = 3 · 31 · 47 25 11305 = 5 · 7 · 17 · 19 35 18721 = 97 · 193 45 31621 = 103 · 3076 1729 = 7 · 13 · 19 16 4681 = 31 · 151 26 12801 = 3 · 17 · 251 36 19951 = 71 · 281 46 33153 = 3 · 43 · 2577 1905 = 3 · 5 · 127 17 5461 = 43 · 127 27 13741 = 7 · 13 · 151 37 23001 = 3 · 11 · 17 · 41 47 34945 = 5 · 29 · 2418 2047 = 23 · 89 18 6601 = 7 · 23 · 41 28 13747 = 59 · 233 38 23377 = 97 · 241 48 35333 = 89 · 3979 2465 = 5 · 17 · 29 19 7957 = 73 · 109 29 13981 = 11 · 31 · 41 39 25761 = 3 · 31 · 277 49 39865 = 5 · 7 · 17 · 6710 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ŭ 
 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

 Eksteraj ligiloj 
  pseŭdoprimoj al bazo 2 (nombroj de Poulet)
  - bazo-2 fortaj pseŭdoprimoj
  - bazo-2 eŭleraj pseŭdoprimoj
  - bazo-2 eŭlero-jakobiaj pseŭdoprimoj
  - bazo-3 eŭlero-jakobiaj pseŭdoprimoj
 Pseŭdoprimoj supren ĝis 5000

Kategorio:Kvazaŭprimoj

nl:Kleine stelling van Fermat#Pseudo-priemgetallen