Diskrétní logaritmus

Tento článek potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

---

Konkrétní problémy: Neencyklopedické formulace, nevyhovuje standardům

Nechť ${\displaystyle p,g,k,Y}$ jsou přirozená čísla, pro něž platí ${\displaystyle Y\equiv g^{k}{\pmod {p}}}$. Potom každé číslo ${\displaystyle k}$ odpovídající uvedené rovnici nazveme diskrétní logaritmus o základu ${\displaystyle g}$ z ${\displaystyle Y}$ vzhledem k modulu ${\displaystyle p}$. Tato definice nedefinuje číslo ${\displaystyle k}$ jednoznačně, proto se někdy upravuje tak, že ze všech možných diskrétních logaritmů ve smyslu předchozí definice se vybere ten nejmenší.

Obecně se nemusí jednat přímo o přirozená čísla modulo ${\displaystyle m}$, diskrétní logaritmus je zobecnění klasického logaritmu pro konečné cyklické grupy.

Praktické užití

Zatímco spočíst ${\displaystyle Y}$ ze znalosti ${\displaystyle k,p,g}$ je snadné, spočíst diskrétní logaritmus ${\displaystyle k}$ ze znalosti ${\displaystyle Y,p,g}$ je velmi obtížné. To předurčuje tento problém k využití v asymetrické kryptografii. Ale standard NIST redukuje grupu pro ${\displaystyle p}$ (například 1024 bitů) na podgrupu ${\displaystyle q}$ (160 bitů).^[1]

Reference

1. http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf - Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography

Externí odkazy

• Diskrétní logaritmus v encyklopedii MathWorld (anglicky)
• https://web.archive.org/web/20121029133807/http://www.wimp.com/howencryption/

Portály: Matematika