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

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  és  is nagy prímtényezőkkel rendelkezik. Egy biztonságos  prím esetében a -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  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  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 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  biztonságos prím, a modulo  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  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 225 + 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 = 2n + 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 2m − 1 alakúak, de 2m − 1 = 6k − 1, amiból az következne, hogy 2m 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  × 2 - 1. Ezt és a hozzá tartozó Sophie Germain-prímet 2012 áprilisában találták meg.

Jegyzetek

Fordítás

További információk
 Safe prime cikk a PlanetMath-on
 

Prímszámok
Kriptográfia
A számelmélet területén a biztonságos prímek ( safe prime ) olyan , +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 : \ ... Akivételével a biztonságos prím q mindig − 1 alakban írható fel , vagy ezzel ekvivalens módon : q ≡( mod– ha p >( lásd Sophie Germain-prím ) . Ehhez hasonlóan , azkivételével minden q biztonságos prím a − 1 vagy az ezzel ekvivalens q ≡( modalakban írható fel – ami triviálisan igazolható , hiszen a ( q − 1 ) / számnak páratlan természetes számnak kell lennie . A két képletet kombinálva – lkkt4 ) =– meghatározható , hogy bármely q >biztonságos prímet−1 , vagy a megegyező q ≡( modalakban 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 és is nagy prímtényezőkkel rendelkezik . Egy biztonságos prím esetében a -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 prímtényezőinek méretétől . Ez igaz a Pollard ró algoritmusra , a Pollard ( p –algoritmusra és Williams p+1 algoritmusára is . Bár a leghatékonyabb ismert faktorizáló algoritmusok futásideje nem függ 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 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 biztonságos prím , a modulo 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 . Egyjegyű biztonságos prímszám , mint pl. a 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+ k biztonságos prím a k = ami azt jelenti , hogy a megtalálásához kb.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ó+1 prím volta , ha p már bizonyítottan prím . Azkivételével nincs olyan Fermat-prím , ami egyben biztonságos prímszám is lenne . Mivel a Fermat-prímek F = + 1 , alakba írhatók , ebből következően ( F − 1) /2 kettő hatványa . Akivé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 , hogykivételével minden biztonságos prím felírható − 1 alakban . A Mersenne-prímek − 1 alakúak , de − 1 = − 1 , amiból az következne , hogy osztható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 . Are végződő + 7 alakban felírható ) biztonságos prímek mindig az utolsó elemek az ilyen láncokban , hiszen10n + 7 ) + 1 = + 15 oszthatótel . Ha egy q biztonságos prímcal osztvamaradé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 × 2 - 1. Ezt és a hozzá tartozó Sophie Germain-prímetáprilisában találták meg . Jegyzetek Fordítás További információk Safe prime cikk a PlanetMath-on Prímszámok Kriptográfia