Erős álprímek

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ó

Egy n = d · 2^s + 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:

$a^{d}\equiv 1\mod n$

vagy

$a^{d\cdot 2^{r}}\equiv -1\mod n\quad {\mbox{ valamely }}0\leq r<s.$

(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.

Az erős álprímek tulajdonságai

Egy a alapra vonatkozó erős álprím minden esetben Euler–Jacobi-álprím, Euler-álprím, 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; 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 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.

Példák

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·10⁹ alatt, ami egyszerre erős álprím 2, 3 és 5 alapra nézve. Ezeket a 7. táblázat sorolja fel itt. 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. 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.

A legkisebb erős álprím n alapra

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