discrete logarithm

Angol

Főnév

discrete logarithm (tsz. discrete logarithms)

(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.

🧠 1. Alapdefiníció

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

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

Azt mondjuk:

„A diszkrét logaritmus

\log_{g} y mod p

az az egész szám

x

, amelyre

g^{x} \equiv y mod p

.”

📌 2. Összehasonlítás a szokásos logaritmussal

Klasszikus logaritmus	Diszkrét logaritmus
$b^{x} = y \Rightarrow x = \log_{b} y$	$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é

🔒 3. Miért fontos?

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

🧮 4. Példa

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

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

Próbálgatással:

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

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

📊 5. Megoldási algoritmusok

Naiv keresés

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

Baby-step Giant-step (BSGS)

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

Pohlig–Hellman algoritmus

Ha $p - 1$ faktorizálható kis prímekre, akkor gyors

Index calculus

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

🧰 6. Python példa – diszkrét logaritmus keresése (naiv mód)

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

🧪 7. Kriptográfiai alkalmazások

Algoritmus	Felhasználás
Diffie–Hellman	Kulcscsere protokoll
ElGamal	Nyilvános kulcsú titkosítás
DSA	Digitális aláírás
Elliptikus görbéken	EC-DH, ECDSA → még nehezebb DLOG-probléma

⛰️ 8. DLOG vs. ECDLOG

Tulajdonság	Diszkrét logaritmus (DLOG)	Elliptikus DLOG (ECDLOG)
Strukturált csoport	$ℤ_{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

🧾 9. Összefoglalás

Fogalom	Leírás
Diszkrét logaritmus	$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 $p$ , jól választott generátor

További információk

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)

v t e Number-theoretic algorithms
primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	sieve of Atkin sieve of Eratosthenes sieve of Pritchard sieve of Sundaram wheel factorization
integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system