Diskrétní logaritmus

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

Externí odkazy

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