Erős álprímek – Wikipédia
A számelmélet területén a valószínű prímek olyan számok, melyek átmennek egy prímteszten, az erősen valószínű prímek pedig olyan számok, melyek átmennek egy prímteszt erős változatán. Az erős álprímek vagy erős pszeudoprímek (strong pseudoprimes) olyan összetett számok, amik átmennek egy prímteszt erős változatán. Minden prímszám átmegy ezeken a teszteken, de az összetett számoknak egy kis része is fals pozitívként – ezek az álprímek.
A Fermat-álprímektől eltérően, melyeknél léteznek minden relatív prím alapra nézve álprímek (a Carmichael-számok), nem léteznek olyan összetett számok, melyek minden alapra nézve erős álprímek lennének.
Formális definíció
[szerkesztés]Egy n = d · 2s + 1 páratlan összetett szám, ahol d szintén páratlan akkor nevezhető erős (Fermat-) álprímnek egy relatív prím a alapra nézve, ha a következő feltételek teljesülnek:
vagy
(Ha egy n szám kielégíti a fenti feltételek valamelyikét, de nem tudjuk, hogy prímszám-e, akkor precízebb az a alapra nézve erős valószínű prímnek hívni. De ha ismert, hogy n nem prímszám, akkor helyénvaló az erős pszeudoprím kifejezés használata.)
Az erős álprím meghatározása függ a választott alaptól, különböző alapokhoz különböző erős álprímek tartoznak. A definíció feltétele triviálisan teljesül, ha a ≡ ±1 mod n, így ezekkel a triviális alapokkal sokszor nem számolnak.
Guy tévesen csak az első feltételt adja meg definíciójában, mely azonban nem minden prímszámra teljesül.[1]
Az erős álprímek tulajdonságai
[szerkesztés]Egy a alapra vonatkozó erős álprím minden esetben Euler–Jacobi-álprím, Euler-álprím,[2] valamint Fermat-álprím arra az alapra nézve, de nem igaz, hogy minden Euler- és Fermat-álprím erős álprím lenne. A Carmichael-számok például egyes alapokra nézve erős álprímek lehetnek – például az 561 erős álprím 50-es alapot tekintve – de nem az összesre.
Egy n összetett szám az n-nél kisebb alapok legfeljebb egynegyedére lehet erős álprím;[3][4] ezért nem léteznek „erős Carmichael-számok”, melyek minden alapra erős álprímek lennének. Ebből következik, hogy annak valószínűsége, hogy egy véletlenszerűen kiválasztott alapra egy szám erős álprím legyen ¼-nél kevesebb, ami a széles körben használt Miller–Rabin-prímteszt alapja. Arnault azonban megad[5] egy 397-jegyű összetett számot, ami erős álprím minden 307-nél kisebb alapra. Annak megakadályozására, hogy egy ilyen számot tévesen prímnek minősítsenek, szokásos az erős álprím-teszt kombinálása egy Lucas-álprímteszttel, ahogy például a Baillie–PSW-prímtesztben történik.
Bármilyen alapot tekintve végtelen sok álprím létezik.[2]
Példák
[szerkesztés]Az első néhány erős álprím 2-es alapra nézve:
- 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... (A001262 sorozat az OEIS-ben).
Az első néhány erős álprím 3-as alapra nézve:
- 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... (A020229 sorozat az OEIS-ben).
Az első néhány erős álprím 5-ös alapra nézve:
- 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (A020231 sorozat az OEIS-ben).
A 4-es alapra lásd (A020230 sorozat az OEIS-ben), 6-tól 100-ig pedig lásd az (A020232 sorozat az OEIS-ben) és (A020326 sorozat az OEIS-ben) közötti sorozatokat.
A feltételeket egynél több alapra tesztelve valamivel erősebb prímtesztet kapunk, mint egyetlen alapra. Például összesen 13 olyan szám van 25·109 alatt, ami egyszerre erős álprím 2, 3 és 5 alapra nézve. Ezeket a 7. táblázat sorolja fel itt.[2] A legkisebb ilyen szám a 25 326 001. Ez azt jelenti, hogy ha n<25326001 és n erős álprím 2, 3 és 5 alapra, akkor n prímszám.
Ezt továbbfejlesztve, a 3825123056546413051 a legkisebb szám, ami egyszerre erős álprím a következő 9 alapra nézve: 2, 3, 5, 7, 11, 13, 17, 19 és 23.[6][7] Tehát ha n<3825123056546413051 és n erős álprím erre a 9 alapra nézve, akkor n prím.
Ha nem az első n prím alapot használjuk a teszteléshez, jobb tesztek is konstruálhatók, melyekben csak 7 alapra nézve kell tesztelni az összes 64 bites bemenetet.[8]
A legkisebb erős álprím n alapra
[szerkesztés]n | Legkisebb SPSP | n | Legkisebb SPSP | n | Legkisebb SPSP | n | Legkisebb SPSP |
1 | 9 | 33 | 545 | 65 | 33 | 97 | 49 |
2 | 2047 | 34 | 33 | 66 | 65 | 98 | 9 |
3 | 121 | 35 | 9 | 67 | 33 | 99 | 25 |
4 | 341 | 36 | 35 | 68 | 25 | 100 | 9 |
5 | 781 | 37 | 9 | 69 | 35 | 101 | 25 |
6 | 217 | 38 | 39 | 70 | 69 | 102 | 133 |
7 | 25 | 39 | 133 | 71 | 9 | 103 | 51 |
8 | 9 | 40 | 39 | 72 | 85 | 104 | 15 |
9 | 91 | 41 | 21 | 73 | 9 | 105 | 451 |
10 | 9 | 42 | 451 | 74 | 15 | 106 | 15 |
11 | 133 | 43 | 21 | 75 | 91 | 107 | 9 |
12 | 91 | 44 | 9 | 76 | 15 | 108 | 91 |
13 | 85 | 45 | 481 | 77 | 39 | 109 | 9 |
14 | 15 | 46 | 9 | 78 | 77 | 110 | 111 |
15 | 1687 | 47 | 65 | 79 | 39 | 111 | 55 |
16 | 15 | 48 | 49 | 80 | 9 | 112 | 65 |
17 | 9 | 49 | 25 | 81 | 91 | 113 | 57 |
18 | 25 | 50 | 49 | 82 | 9 | 114 | 115 |
19 | 9 | 51 | 25 | 83 | 21 | 115 | 57 |
20 | 21 | 52 | 51 | 84 | 85 | 116 | 9 |
21 | 221 | 53 | 9 | 85 | 21 | 117 | 49 |
22 | 21 | 54 | 55 | 86 | 85 | 118 | 9 |
23 | 169 | 55 | 9 | 87 | 247 | 119 | 15 |
24 | 25 | 56 | 55 | 88 | 87 | 120 | 91 |
25 | 217 | 57 | 25 | 89 | 9 | 121 | 15 |
26 | 9 | 58 | 57 | 90 | 91 | 122 | 65 |
27 | 121 | 59 | 15 | 91 | 9 | 123 | 85 |
28 | 9 | 60 | 481 | 92 | 91 | 124 | 25 |
29 | 15 | 61 | 15 | 93 | 25 | 125 | 9 |
30 | 49 | 62 | 9 | 94 | 93 | 126 | 25 |
31 | 15 | 63 | 529 | 95 | 1891 | 127 | 9 |
32 | 25 | 64 | 9 | 96 | 95 | 128 | 49 |
Jegyzetek
[szerkesztés]- ↑ Guy, Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.
- ↑ a b c Carl Pomerance, John L. Selfridge, Samuel S. Wagstaff, Jr. (1980. július 1.). „The pseudoprimes to 25·109”. Mathematics of Computation 35 (151), 1003–1026. o. DOI:10.1090/S0025-5718-1980-0572872-7.
- ↑ Monier, Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms. Theoretical Computer Science, 12 pp. 97-108, 1980.
- ↑ Rabin, Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12 pp. 128-138, 1980.
- ↑ F. Arnault (1995. augusztus 1.). „Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases”. Journal of Symbolic Computation 20 (2), 151–161. o. DOI:10.1006/jsco.1995.1042.
- ↑ Zhenxiang Zhang, Min Tang (2003). „Finding Strong Pseudoprimes to Several Bases. II”. Mathematics of Computation 72 (244), 2085–2097. o. DOI:10.1090/S0025-5718-03-01545-X.
- ↑ Jiang, Yupeng; Deng, Yingpu (2012). "Strong pseudoprimes to the first 9 prime bases"
- ↑ SPRP Records. (Hozzáférés: 2015. június 3.)