Biztonságos prímek

A számelmélet területén a biztonságos prímek (safe prime) olyan, 2p + 1 alakban felírható prímszámok, ahol p maga is prím. (A p prímet ilyenkor Sophie Germain-prímnek nevezik.) Az első néhány biztonságos prímszám:

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... (A005385 sorozat az OEIS-ben)

A 7 kivételével a biztonságos prím q mindig 6k − 1 alakban írható fel, vagy ezzel ekvivalens módon: q ≡ 5 (mod 6) – ha p > 3 (lásd Sophie Germain-prím). Ehhez hasonlóan, az 5 kivételével minden q biztonságos prím a 4k − 1 vagy az ezzel ekvivalens q ≡ 3 (mod 4) alakban írható fel – ami triviálisan igazolható, hiszen a (q − 1) / 2 számnak páratlan természetes számnak kell lennie. A két képletet kombinálva – lkkt (6,4) = 12 – meghatározható, hogy bármely q > 7 biztonságos prímet 12k−1, vagy a megegyező q ≡ 11 (mod 12) alakban lehet felírni.

Alkalmazásai

A prímszámok a „biztonságos” jelzőt az erős prímszámokhoz való kapcsolatuk miatt kapták. Egy q prím akkor erős, ha q + 1 és q − 1 is nagy prímtényezőkkel rendelkezik. Egy biztonságos q = 2p + 1 prím esetében a q − 1-nek természetesen adódik egy nagy prímtényezője, méghozzá p, ezért a q biztonságos prím már az erős prímszámok kritériumai egy részének megfelel. Egy q prímtényezővel osztható összetett szám prímtényezőkre bontásához szükséges idő egyes algoritmusok esetében függ q − 1 prímtényezőinek méretétől. Ez igaz a Pollard ró algoritmusra, a Pollard (p – 1) algoritmusra és Williams p+1 algoritmusára is. Bár a leghatékonyabb ismert faktorizáló algoritmusok futásideje nem függ q + 1 prímtényezőinek méretétől, a kriptográfia területén ez mégis fontos tényező: például az ANSI X9.31 szabvány^[1] megköveteli, hogy az RSA algoritmus modulusai erős (ne csak biztonságos) prímek legyenek.

A biztonságos prímek a kriptográfia területén a diszkrét logaritmus-alapú technikákban is szerepet kapnak, például a Diffie–Hellman kulcscsere algoritmusában. Ha 2p + 1 biztonságos prím, a modulo 2p + 1 számok multiplikatív csoportjának létezik olyan részcsoportja, aminek a rendje nagy prímszám. Általában ez a prím rendű részcsoport, amit el kívánunk érni, és azért érdemes biztonságos prímeket használni hozzá, hogy a modulus p-hez képest a lehető legkisebb lehessen.

A bizonyos kongruenciáknak eleget tevő biztonságos prímek felhasználhatók pszeudovéletlen számoknak Monte Carlo-szimulációkban.

A biztonságos prímek megtalálása időigényesebb az erős prímekénél, ezért kevésbé használják őket – a számítógépek teljesítményének növekedésével azonban egyre többször. Egy 500 jegyű biztonságos prímszám, mint pl. a ${\displaystyle 2\cdot (1,416,461,893+10^{500})+1}$ megkeresése most már a praktikum világába tartozik. A nehézség az, hogy a biztonságos prímek kb. az ikerprímekhez hasonlóan meglehetősen ritkák. Például a legkisebb k, amire a 2²⁵ + k biztonságos prím a k = 1989, ami azt jelenti, hogy a megtalálásához kb. 1989 számon kell prímtesztet végezni. A ritkaságuktól eltekintve programozástechnikailag egyszerűbb megtalálni őket, mint az erős prímeket. Nem szükséges megpróbálni p−1 felbontását. (Ha p−1 nehezen felbontható, akkor p-t elvetjük, és p+2-vel próbálkozunk. Ezt addig csináljuk, amíg p−1 könnyen felbontható. Ez valószínűleg hamarabb fog megtörténni, mint hogy p biztonságos prím legyen, mivel az olyan p prímek, amire p−1 könnyen faktorizálható viszonylag sűrűn helyezkednek el.) A fentieket az teszi lehetővé, hogy extrém gyors prímtesztek állnak rendelkezésünkre, mint pl. a Miller–Rabin-prímteszt.

További tulajdonságok

Nem ismert olyan speciális prímteszt a biztonságos prímek keresésére, mint ami a Fermat-prímek és a Mersenne-prímekre létezik. A Pocklington-kritérium segítségével azonban bizonyítható 2p+1 prím volta, ha p már bizonyítottan prím.

Az 5 kivételével nincs olyan Fermat-prím, ami egyben biztonságos prímszám is lenne. Mivel a Fermat-prímek F = 2ⁿ + 1, alakba írhatók, ebből következően (F − 1)/2 kettő hatványa.

A 7 kivételével nincs olyan Mersenne-prím, ami biztonságos prím lenne. Ez abból a fent említett állításból következik, hogy 7 kivételével minden biztonságos prím felírható 6k − 1 alakban. A Mersenne-prímek 2^m − 1 alakúak, de 2^m − 1 = 6k − 1, amiból az következne, hogy 2^m osztható 6-tal, ami képtelenség.

Az első fajta Cunningham-láncok az utolsó kivételével minden eleme Sophie Germain-prím, az első kivételével minden eleme pedig biztonságos prím. A 7-re végződő (10n + 7 alakban felírható) biztonságos prímek mindig az utolsó elemek az ilyen láncokban, hiszen 2(10n + 7) + 1 = 20n + 15 osztható 5-tel.

Ha egy q biztonságos prím 8-cal osztva 7 maradékot ad, akkor osztója annak a Mersenne-számnak, aminek a kitevője a q-hoz tartozó Sophie Germain-prím.

Rekordok

2012 októberében a legnagyobb ismert biztonságos prímszám a 18 543 637 900 515 × 2^666 668 - 1. Ezt és a hozzá tartozó Sophie Germain-prímet 2012 áprilisában találták meg.^[2]

Jegyzetek

Fordítás

• Ez a szócikk részben vagy egészben a Safe prime című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Safe prime cikk a PlanetMath-on
• szerk.: M. Abramowitz, I. A. Stegun: Handbook of Mathematical Functions, Tenth Printing, Applied Math. Series, National Bureau of Standards, 870. o. (1972)