discrete logarithm

Üdvözlöm, Ön a discrete logarithm szó jelentését keresi. A DICTIOUS-ban nem csak a discrete logarithm szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a discrete logarithm szót egyes és többes számban mondani. Minden, amit a discrete logarithm szóról tudni kell, itt található. A discrete logarithm szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Adiscrete logarithm és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Főnév

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.



🧠 1. Alapdefiníció

Adott egy prím , egy moduláris alaprendszer (vagy más néven ciklikus csoport), egy generátor , és egy érték , akkor a diszkrét logaritmus az alábbi egyenlet megoldása:

Azt mondjuk:

„A diszkrét logaritmus az az egész szám , amelyre .”



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

Klasszikus logaritmus Diszkrét logaritmus
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 elég nagy (pl. 2048 bites). Ezért kriptográfiai biztonságot nyújt.



🧮 4. Példa

Legyen , , . Keressük azt az -et, amelyre:

Próbálgatással:

  • Értelmezés sikertelen (formai hiba): {\textstyle 5^2 = 25 ≡ 2 \mod 23}

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



📊 5. Megoldási algoritmusok

Naiv keresés

  • Próbáld ki minden -re
  • Időkomplexitás:

Baby-step Giant-step (BSGS)

  • Téridő kompromisszum
  • Idő és memória:

Pohlig–Hellman algoritmus

  • Ha 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 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 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 , jól választott generátor