Erős álprímek

Aszámelméletterületén avalószínű prímekolyan számok, melyek átmennek egyprímteszten,az erősen valószínű prímek pedig olyan számok, melyek átmennek egy prímteszt erős változatán. Azerős álprímekvagyerő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.

AFermat-álprímektőleltérően, melyeknél léteznek mindenrelatív prímalapra nézveálprímek(aCarmichael-számok), nem léteznek olyan összetett számok, melyek minden alapra nézve erős álprímek lennének.

Formális definíció

Egyn=d· 2^s+ 1 páratlan összetett szám, aholdszintén páratlan akkor nevezhető erős (Fermat-) álprímnek egyrelatív prímaalapra 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 egynszám kielégíti a fenti feltételek valamelyikét, de nem tudjuk, hogy prímszám-e, akkor precízebb azaalapra nézve erősvalószínű prímnekhívni. De ha ismert, hogynnem 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.

Guyté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

Egyaalapra vonatkozó erős álprím minden esetbenEuler–Jacobi-álprím,Euler-álprím,valamintFermat-álprímarra az alapra nézve, de nem igaz, hogy minden Euler- és Fermat-álprím erős álprím lenne. ACarmichael-számokpé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.

Egynösszetett szám azn-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áltMiller–Rabin-prímtesztalapja. Arnault azonban megadegy 397-jegyű összetett számot, ami erős álprímminden307-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 egyLucas-álprímteszttel,ahogy például aBaillie–PSW-prímtesztbentö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,... (A001262sorozat azOEIS-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,... (A020229sorozat azOEIS-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,... (A020231sorozat azOEIS-ben).

A 4-es alapra lásd (A020230sorozat azOEIS-ben), 6-tól 100-ig pedig lásd az (A020232sorozat azOEIS-ben) és (A020326sorozat azOEIS-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 han<25326001 ésnerős álprím 2, 3 és 5 alapra, akkornprí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 han<3825123056546413051 ésnerős álprím erre a 9 alapra nézve, akkornprím.

Ha nem az elsőnprí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ímnalapra

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