Diskrétní logaritmus

Technology

12 hours ago

Author

Nechť p, g, k, Y jsou přirozená čísla, pro něž platí Y \equiv g^{k} \pmod 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. +more Ale standard NIST redukuje grupu pro p (například 1024 bitů) na podgrupu q (160 bitů).