Bezpečné prvočíslo: Porovnání verzí

Z Wikipedie, otevřené encyklopedie
Smazaný obsah Přidaný obsah
4k+1 opraveno na 4k-1, 12+1 opraveno na 12k-1
Bez shrnutí editace
Řádek 2: Řádek 2:
[[5 (číslo)|5]], [[7 (číslo)|7]], [[11 (číslo)|11]], [[23 (číslo)|23]], [[47 (číslo)|47]], [[59 (číslo)|59]], [[83 (číslo)|83]], [[107 (číslo)|107]], [[167 (číslo)|167]], [[179 (číslo)|179]], [[227 (číslo)|227]], [[263 (číslo)|263]], [[347 (číslo)|347]], [[359 (číslo)|359]], [[383 (číslo)|383]], [[467 (číslo)|467]], [[479 (číslo)|479]], [[503 (číslo)|503]], [[563 (číslo)|563]], [[587 (číslo)|587]], [[719 (číslo)|719]], [[839 (číslo)|839]], [[863 (číslo)|863]], [[887 (číslo)|887]], [[983 (číslo)|983]]<ref>{{OEIS|A005385}}</ref>
[[5 (číslo)|5]], [[7 (číslo)|7]], [[11 (číslo)|11]], [[23 (číslo)|23]], [[47 (číslo)|47]], [[59 (číslo)|59]], [[83 (číslo)|83]], [[107 (číslo)|107]], [[167 (číslo)|167]], [[179 (číslo)|179]], [[227 (číslo)|227]], [[263 (číslo)|263]], [[347 (číslo)|347]], [[359 (číslo)|359]], [[383 (číslo)|383]], [[467 (číslo)|467]], [[479 (číslo)|479]], [[503 (číslo)|503]], [[563 (číslo)|563]], [[587 (číslo)|587]], [[719 (číslo)|719]], [[839 (číslo)|839]], [[863 (číslo)|863]], [[887 (číslo)|887]], [[983 (číslo)|983]]<ref>{{OEIS|A005385}}</ref>


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


== Použití ==
== Použití ==

Verze z 2. 10. 2020, 10:32

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 číselmetodě 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 . 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 225 + 1 bezpečné prvočíslo, je k = 1989, 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.