Bezpečné prvočíslo je prvočíslo ve tvaru 2p + 1, kde p je také prvočíslo (a naopak, p je prvočíslo Sophie Germainové ). Prvních několik bezpečných prvočísel je:
5 , 7 , 11 , 23 , 47 , 59, 83 , 107 , 167, 179 , 227, 263, 347, 359, 383, 467, 479, 503, 883, 37 98 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, … ( A005385 )S výjimkou 7 má bezpečné prvočíslo q tvar 6 k − 1 nebo ekvivalentně q ≡ 5 ( mod 6) - kde p > 3. Stejně tak, s výjimkou 5, bezpečné prvočíslo číslo q je reprezentovatelné ve tvaru 4 k − 1 nebo ekvivalentně q ≡ 3 (mod 4) je triviální tvrzení, protože ( q − 1) / 2 musí být liché přirozené číslo . Kombinací obou tvarů pomocí LCM (6,4) dostaneme, že bezpečné prvočíslo q > 7 musí být také reprezentovatelné jako 12k −1 nebo ekvivalentně q ≡ 11 (mod 12).
Prvočísla tohoto druhu se nazývají bezpečná kvůli jejich spojení se silnými prvočísly . Prvočíslo q se nazývá striktní prvočíslo, jestliže q + 1 a q − 1 mají oba velké prvočíselné dělitele[ specifikovat ] . Pro bezpečné prvočíslo q = 2p + 1 má číslo q − 1 přirozeně velkého dělitele, a to p , takže q částečně splňuje kritérium silného prvočísla. Průběh některých metod dělení čísla s q jako dělitele závisí částečně na velikosti prvočíselných dělitelů q − 1. To platí například pro Pollardův ρ-algoritmus +1 a −1 metody. Ačkoli většina známých účinných metod rozkladu nezávisí na velikosti prvočíselných dělitelů při rozkladu q - 1, považuje se to přesto za důležité pro šifrování: například standard ANSI X9.31 vyžaduje, aby byla silná prvočísla (nikoli bezpečná prvočísla ) . používá se pro RSA .
Bezpečná prvočísla jsou také důležitá v kryptografii pro jejich použití v přístupech založených na diskrétním logaritmu , jako je Diffie-Hellmanův algoritmus . Pokud je 2p + 1 bezpečné prvočíslo, multiplikativní skupina čísel modulo 2p + 1 má podskupinu vysokého řádu . Toto je obvykle podskupina, kterou chcete, a důvodem pro použití bezpečných prvočísel je, že modul je malý vzhledem k p .
Bezpečná prvočísla, která také splňují určité podmínky , lze použít ke generování pseudonáhodných čísel pro použití v metodě Monte Carlo .
Neexistuje žádný test pro bezpečná prvočísla jako pro Fermatova čísla a Mersennova čísla . Pocklingtonův test však lze použít k testování primality 2 p + 1, když je nastavena primálnost p .
S výjimkou 5 neexistují žádná Fermatova prvočísla, která jsou také bezpečná. Protože Fermatova prvočísla mají tvar m F = 2 n + 1, vyplývá z toho, že ( F − 1)/2 je mocnina dvou .
S výjimkou 7 neexistují žádná Mersennova prvočísla, která jsou také bezpečná. Vyplývá to z výše uvedeného faktu, že všechna bezpečná prvočísla kromě 7 jsou ve tvaru 6 k − 1. Mersennova čísla jsou ve tvaru 2 m − 1, ale pak 2 m − 1 = 6 k − 1, což znamená, že 2 m je dělitelné 6, což je nemožné.
Všechny prvky Cunninghamské sekvence kromě prvního jsou čísla Sophie Germainové prvního druhu, takže všechny prvky kromě prvního v řetězci jsou bezpečná prvočísla. Prvočísla končící na 7, tedy tvaru 10 n + 7, pokud se v takových řetězcích vyskytují, jsou vždy poslední, protože 2(10 n + 7) + 1 = 20 n + 15 je dělitelné 5.
Je-li bezpečné prvočíslo q 7 mod 8, je to dělitel Mersennova čísla , které odpovídá číslu Sophie Germain (používá se jako mocnina).
V březnu 2010 je největší známé bezpečné číslo 183027 2 265441 −1. Toto číslo, stejně jako odpovídající největší známé číslo Sophie Germainové, našel Tom Wu 22. března 2010 pomocí programů sgsieve a LLR [1] .
5. února 2007 byl vypočten modul diskrétního logaritmu 160místného (530bitového) bezpečného prvočísla. Viz záznamy pro diskrétní logaritmy .