Logaritm discret

În matematică și în special în algebră și aplicațiile sale, logaritmii discreți sunt echivalentul logaritmilor obișnuiți pentru aritmetica modulară .

Problema calculului logaritmilor discreți are asemănări remarcabile cu cea a factorizării numerelor întregi , deoarece se presupune că ambele probleme sunt dificile (nu sunt cunoscuți algoritmi care să le rezolve în timp polinomial ), algoritmii unuia sunt adesea adaptați la celălalt și invers, și ambele au fost utilizate ca bază teoretică pentru construirea sistemelor criptografice . În special, logaritmul discret găsește aplicația în criptografie bazată pe curbe eliptice . Astfel de sisteme criptografice își bazează securitatea pe presupusa dificultate a unor astfel de probleme.

Definiție informală

Așa cum logaritmul este operația inversă a exponențialei , în același mod logaritmul discret este operația inversă a puterii discrete .

Să presupunem că avem o mulțime A care conține numerele între 0 și p - 1 , unde p este un număr prim :

$A=\{0,1,2,\dots ,p-1\}$ ${\ displaystyle A = \ {0,1,2, \ dots, p-1 \}}$ ${\ displaystyle A = \ {0,1,2, \ dots, p-1 \}}$ .

Definim o operațiune pe care pentru comoditate o vom denumi aici $\otimes$ ${\ displaystyle \ otimes}$ $\ otimes$ pe două numere $a,b\in A$ ${\ displaystyle a, b \ în A}$ ${\ displaystyle a, b \ în A}$ :

$a\otimes b=a^{b}{\bmod {p}}$ ${\ displaystyle a \ otimes b = a ^ {b} {\ bmod {p}}}$ ${\ displaystyle a \ otimes b = a ^ {b} {\ bmod {p}}}$

unde mod este operația modulului . Această operațiune $\otimes$ ${\ displaystyle \ otimes}$ $\ otimes$ este puterea discretă menționată anterior.

Prin urmare, definim „logaritmul discret al unui număr x bazat pe ” ca acel număr b astfel încât $a\otimes b=x$ ${\ displaystyle a \ otimes b = x}$ ${\ displaystyle a \ otimes b = x}$ , acesta este $a^{b}{\bmod {p}}=x$ ${\ displaystyle a ^ {b} {\ bmod {p}} = x}$ ${\ displaystyle a ^ {b} {\ bmod {p}} = x}$ .

Exemplu

Contextul în care este probabil mai ușor de înțeles logaritmii discreți este cel al grupului multiplicativ de numere întregi modulo p $\mathbb {Z} _{p}^{*}$ ${\ displaystyle \ mathbb {Z} _ {p} ^ {*}}$ ${\ mathbb {Z}} _ {p} ^ {*}$ (cu p număr prim ), adică mulțimea numerelor întregi $\{1,\dots ,p-1\}$ ${\ displaystyle \ {1, \ dots, p-1 \}}$ ${\ displaystyle \ {1, \ dots, p-1 \}}$ cu operația de multiplicare modulo p ; așa că , dacă vrem k puterea unui element al grupului , putem calcula k-lea de putere ca un întreg și apoi să ia restul împărțirii de p. Acest proces este denumit putere discretă . De exemplu, să luăm în considerare $\mathbb {Z} _{17}^{*}$ ${\ displaystyle \ mathbb {Z} _ {17} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {17} ^ {*}}$ ; a obtine $3^{4}$ ${\ displaystyle 3 ^ {4}}$ ${\ displaystyle 3 ^ {4}}$ în acest grup, calculăm mai întâi $3^{4}=81$ ${\ displaystyle 3 ^ {4} = 81}$ ${\ displaystyle 3 ^ {4} = 81}$ și împarte 81 la 17, obținând 4 cu restul de 13; deci în grup $\mathbb {Z} _{17}^{*}$ ${\ displaystyle \ mathbb {Z} _ {17} ^ {*}}$ ${\ displaystyle \ mathbb {Z} _ {17} ^ {*}}$ Și $3^{4}=13$ ${\ displaystyle 3 ^ {4} = 13}$ ${\ displaystyle 3 ^ {4} = 13}$ .

Logaritmul discret este operația inversă: dată $3^{k}\equiv 13\mod 17$ ${\ displaystyle 3 ^ {k} \ equiv 13 \ mod 17}$ ${\ displaystyle 3 ^ {k} \ equiv 13 \ mod 17}$ , care k face expresia adevărată? Strict vorbind, ar exista infinite soluții întregi, datorită naturii modulare a problemei; în general, căutăm cea mai mică soluție non-negativă, care este $k=4$ ${\ displaystyle k = 4}$ ${\ displaystyle k = 4}$ .

Definiție formală

În general, fie G un grup ciclic finit de n elemente (să presupunem o scriere multiplicativă). Fie b un generator de G ; atunci orice element g al lui G poate fi scris în formă $g=b^{k}$ ${\ displaystyle g = b ^ {k}}$ ${\ displaystyle g = b ^ {k}}$ pentru un număr întreg k . De asemenea, dacă $b^{k}=g=b^{h}$ ${\ displaystyle b ^ {k} = g = b ^ {h}}$ ${\ displaystyle b ^ {k} = g = b ^ {h}}$ pentru doi numere întregi h și k , atunci h și k sunt modulo n congruent. Prin urmare, putem defini o funcție:

\log _{b}:\ G\ \rightarrow \ \mathbb {Z} _{n}

{\ displaystyle \ log _ {b}: \ G \ \ rightarrow \ \ mathbb {Z} _ {n}}

{\ displaystyle \ log _ {b}: \ G \ \ rightarrow \ \ mathbb {Z} _ {n}}

unde este $\mathbb {Z} _{n}$ ${\ displaystyle \ mathbb {Z} _ {n}}$ ${\ mathbb {Z}} _ {n}$ indică inelul de numere întregi modulo n , atribuindu-le fiecăruia $g\in G$ ${\ displaystyle g \ în G}$ $g \ în G$ clasa de congruență k modulo n . Această funcție este un izomorfism între grupuri , numit logaritm discret la baza b . b se mai numește și rădăcină primitivă .

Formula pentru schimbarea bazei logaritmilor obișnuiți rămâne valabilă: dacă c este un alt generator de G , avem că:

\log _{c}(g)=\log _{c}(b)\cdot \log _{b}(g)

{\ displaystyle \ log _ {c} (g) = \ log _ {c} (b) \ cdot \ log _ {b} (g)}

{\ displaystyle \ log _ {c} (g) = \ log _ {c} (b) \ cdot \ log _ {b} (g)}

Algoritmi

Nu există algoritmi eficienți cunoscuți pentru calcularea logaritmilor discreți. Un posibil algoritm este căutarea exhaustivă , efectuată prin creșterea b la puteri crescând treptat până când se obține g ; aceasta funcționează, dar necesită un timp de calcul care este liniar în raport cu dimensiunea grupului G și, prin urmare, exponențial în raport cu numărul de cifre ale dimensiunii grupului.

Există algoritmi mai sofisticați, în general inspirați de algoritmi similari pentru factorizarea numerelor întregi. Acestea sunt mai rapide decât precedentul, dar niciunul nu are timp de rulare polinomial .

Baby-step-giant-step
Algoritmul rho al lui Pollard
Algoritm Pohlig-Hellman
Algoritm de calcul al indexului
Număr general câmpuri sită
Cernă de câmp funcțional

Criptare

Calculul logaritmilor discreți pare o problemă dificilă (algoritmii eficienți nu sunt cunoscuți), în timp ce problema inversă a exponențierii discrete nu este. Această asimetrie este analogă cu cea dintre factorizarea numerelor întregi și multiplicarea numerelor întregi. Ambele asimetrii au fost utilizate pentru construirea sistemelor criptografice.

În criptografia discretă bazată pe logaritm, alegerile comune pentru grupul G sunt grupările ciclice $\mathbb {Z} _{p}^{*}$ ${\ displaystyle \ mathbb {Z} _ {p} ^ {*}}$ ${\ mathbb {Z}} _ {p} ^ {*}$ ; vezi ElGamal , Diffie-Hellman și Algoritmul semnăturii digitale .

Cele mai recente aplicații ale criptografiei utilizează logaritmi discreți în subgrupuri ciclice de curbe eliptice pe câmpuri finite ; vezi criptografia eliptică .

Elemente conexe

Portal de criptografie

Portalul de matematică