discrete logarithm

discrete logarithm (tsz. discrete logarithms)

1. (informatika) diszkrét logaritmus

A discrete logarithm (diszkrét logaritmus) a klasszikus logaritmus moduláris aritmetikai megfelelője – egy központi fogalom a kriptográfiában, különösen nyilvános kulcsú titkosítási rendszerek (mint a Diffie–Hellman, ElGamal, DSA) alapjául szolgál. A diszkrét logaritmus problémája nehezen megoldható, így kriptográfiai biztonságot nyújt.

Adott egy prím ${\textstyle p}$, egy moduláris alaprendszer ${\textstyle \mathbb {Z} _{p}^{*}}$ (vagy más néven ciklikus csoport), egy generátor ${\textstyle g}$, és egy érték ${\textstyle y}$, akkor a diszkrét logaritmus ${\textstyle x}$ az alábbi egyenlet megoldása:

$${\displaystyle g^{x}\equiv y\mod p}$$

Azt mondjuk:

„A diszkrét logaritmus ${\textstyle \log _{g}y\mod p}$ az az egész szám ${\textstyle x}$, amelyre ${\textstyle g^{x}\equiv y\mod p}$.”

Klasszikus logaritmus	Diszkrét logaritmus
${\textstyle b^{x}=y\Rightarrow x=\log _{b}y}$	${\textstyle g^{x}\equiv y\mod p\Rightarrow x=\log _{g}y\mod p}$
Folytonos számhalmazon	Egész számokon, modulóval
Könnyen kiszámolható	Nehéz visszafelé

A diszkrét logaritmus problémára nincs ismert hatékony (polinomiális idejű) algoritmus, ha a prím ${\textstyle p}$ elég nagy (pl. 2048 bites). Ezért kriptográfiai biztonságot nyújt.

Legyen ${\textstyle p=23}$, ${\textstyle g=5}$, ${\textstyle y=8}$. Keressük azt az ${\textstyle x}$-et, amelyre:

$${\displaystyle 5^{x}\equiv 8\mod 23}$$

Próbálgatással:

• ${\textstyle 5^{1}=5}$
• Értelmezés sikertelen (formai hiba): {\textstyle 5^2 = 25 ≡ 2 \mod 23}
• ${\textstyle 5^{3}=10}$
• ${\textstyle 5^{4}=4}$
• ${\textstyle 5^{5}=20}$
• ${\textstyle 5^{6}=8}$

✅ Megvan: ${\textstyle x=6}$, mert Értelmezés sikertelen (formai hiba): {\textstyle 5^6 ≡ 8 \mod 23}

• Próbáld ki ${\textstyle g^{x}\mod p}$ minden ${\textstyle x=1,2,...,p-1}$-re
• Időkomplexitás: ${\textstyle O(p)}$

• Téridő kompromisszum
• Idő és memória: ${\textstyle O({\sqrt {p}})}$

• Ha ${\textstyle p-1}$ faktorizálható kis prímekre, akkor gyors

• Nagy prímekre gyorsabb, de nem működik kis csoportokban
• Nem alkalmazható pl. elliptikus görbéknél

def discrete_log(g, y, p):
    for x in range(1, p):
        if pow(g, x, p) == y:
            return x
    return None

print(discrete_log(5, 8, 23))  # → 6

Tulajdonság	Diszkrét logaritmus (DLOG)	Elliptikus DLOG (ECDLOG)
Strukturált csoport	${\textstyle \mathbb {Z} _{p}^{*}}$	Elliptikus görbe pontjai
Index calculus hatékony	✅ Igen	❌ Nem működik
Biztonság bitméretenként	Kevésbé kompakt	Sokkal erősebb

Fogalom	Leírás
Diszkrét logaritmus	${\textstyle g^{x}\equiv y\mod p}$ probléma megoldása
Nehézségi szint	NP-intermediális (nincs ismert gyors algoritmus)
Alkalmazások	Kriptográfia, digitális aláírás, kulcscsere
Algoritmusok	Naiv, BSGS, Pohlig–Hellman, Index calculus
Védelem	Nagy ${\textstyle p}$, jól választott generátor

• discrete logarithm - Szótár.net (en-hu)
• discrete logarithm - Sztaki (en-hu)
• discrete logarithm - Merriam–Webster
• discrete logarithm - Cambridge
• discrete logarithm - WordNet
• discrete logarithm - Яндекс (en-ru)
• discrete logarithm - Google (en-hu)
• discrete logarithm - Wikidata
• discrete logarithm - Wikipédia (angol)