Diskrétní logaritmus

Šablona:Upravit Nechť $p,g,k,Y$ jsou přirozená čísla, pro něž platí $Y\equiv g^k(\mathrm{mod}p)$. Potom každé číslo $k$ odpovídající uvedené rovnici nazveme diskrétní logaritmus o základu $g$ z $Y$ vzhledem k modulu $p$. Tato definice nedefinuje číslo $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 $m$, diskrétní logaritmus je zobecnění klasického logaritmu pro konečné cyklické grupy.

Praktické užití

Zatímco spočíst $Y$ ze znalosti $k,p,g$ je snadné, spočíst diskrétní logaritmus $k$ ze znalosti $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 $p$ (například 1024 bitů) na podgrupu $q$ (160 bitů).

Externí odkazy

• Šablona:MathWorld
• https://web.archive.org/web/20121029133807/http://www.wimp.com/howencryption/