Erős álprímek

A Wikipédiából, a szabad enciklopédiából

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-as 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ím2, 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]

  1. Guy, Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.
  2. ^ 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.  
  3. Monier, Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms. Theoretical Computer Science, 12 pp. 97-108, 1980.
  4. Rabin, Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12 pp. 128-138, 1980.
  5. 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.  
  6. 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.  
  7. Jiang, Yupeng; Deng, Yingpu (2012). "Strong pseudoprimes to the first 9 prime bases"
  8. SPRP Records