szó jelentését keresi. A DICTIOUS-ban nem csak a
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
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
é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)
- (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
|