Bezpečné prvočíslo

Bezpečné prvočíslo je prvočíslo ve tvaru 2p + 1, kde p je také prvočíslo. Číslo p tedy patří mezi prvočísla Sophie Germainové. Bezpečná prvočísla menší než 1000 jsou: 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^[1]

Kromě 7 jsou všechna bezpečná prvočísla q ve tvaru 6k-1 (k∈N); s výjimkou 5 jsou všechna ve tvaru 4k-1, z čehož lze použitím nejmenšího společného násobku, že je také lze zapsat jako 12k-1.

Použití

Tato prvočísla se nazývají bezpečná díky jejich vztahu k silným prvočíslům. Prvočíslo q je silné, pokud q-1 a q+1 mají velké prvočíselné dělitele. Pro každé bezpečné prvočíslo q=2p + 1 má číslo q - 1 má velkého prvočíselného dělitele p.

Bezpečná prvočísla jsou důležitá v kryptografii pro jejich využití v postupech založených na diskrétních logaritmech jako je například Diffieho-Hellmanova výměna klíčů.

Některá bezpečná prvočísla mohou být použita ke generování pseudonáhodných čísel v metodě Monte Carlo.

Bezpečná prvočísla vyžadují mnohem více času na nalezení než silná prvočísla a proto jsou méně často používána. S tím, jak se počítače zrychlují, je jejich použití stále běžnější. Využívají se například 500ciferná bezpečná prvočísla jako je 2 · (1416461893 + 10⁵⁰⁰) + 1. Problém je v tom, že hustota bezpečných prvočísel je podobně nízká jako hustota prvočíselných dvojic. Například nejmenší k, pro které je 2²⁵ + 1 bezpečné prvočíslo, je k = 1989,^[ujasnit] což znamená, že jeho nalezení vyžaduje otestovat 1989 čísel na prvočíselnost. I přes jejich nízkou hustotu je lze nalézt snáze než silná prvočísla, protože příslušné programy jsou jednodušší.

Další vlastnosti

Neexistuje žádný zvláštní test prvočíselnosti bezpečných prvočísel, tak jak je tomu u Fermatových a Mersennových prvočísel.

S výjimkou čísla 5 neexistuje Fermatovo prvočíslo, které by bylo také bezpečné prvočíslo.

Kromě 7 neexistují žádná Mersennova bezpečná prvočísla.

Reference

V tomto článku byl použit překlad textu z článku Safe prime na anglické Wikipedii.