Problém diskrétního logaritmu

Motivace:

• V reálných číslech je výpočet mocniny i logaritmu stejně náročný
• V konečné grupě např. v s operací je mocnina rychlá (algoritmus S&M), ale logaritmus náročný (brute-force)

S použitím algoritmu Square & Multiply

Nechť je grupa

je mocninou prvku

Potom diskrétní logaritmus prvku o základu je každé číslo takové, že , značíme ho

Nalezení se nazývá PDL

Grupy, aditivní (řešena Euklidem), multiplikativní (náročná)

Cyklická grupa - existuje minimálně 1 generátor

Využíván např. u Diffie-Hellmana, RSA nebo El-Gamal