Sari la conținut

Logaritm discret

De la Wikipedia, enciclopedia liberă

În matematică, pentru numerele reale date a și b, logaritmul logb a este un număr x astfel încât bx = a. Analog, în orice grup G, se poate defini pentru orice număr întreg k puterea bk, iar logaritmul discret logba este un număr întreg k astfel încât bk = a. În teoria numerelor, termenul cel mai frecvent utilizat este cel de indice: putem scrie x = indr a (mod m) (se citește „indicele lui a în baza r modulo m”) pentru rxa (mod m ) dacă r este o rădăcină primitivă a lui m și cmmdc (a, m) = 1.

Logaritmii discreți sunt rapid calculabili în câteva cazuri speciale. Totuși, nu se cunoaște nicio metodă eficientă pentru a-i calcula în general. Câțiva algoritmi importanți din criptografia cu cheie publică își bazează securitatea pe presupunerea că problema logaritmului discret în cadrul unor grupuri alese cu atenție nu are o soluție eficientă.

Fie G orice grup. Notăm operația de grup a acestuia cu semnele de înmulțire și elementul său neutru cu 1. Fie b orice element al lui G. Pentru orice număr întreg pozitiv k, expresia bk reprezintă produsul lui b cu el însuși de k ori:

În mod similar, fie bk produsul lui b−1 cu sine însuși de k ori. Pentru k=0, puterea k este elementul neutru 0: b0=1.

Fie a un element al lui G. Un întreg k, care rezolvă ecuația bk = a se numește logaritmul discret (sau pur și simplu logaritmul, în acest context) din a în bază b. Se scrie k = logb a .

Puterile lui 10

[modificare | modificare sursă]

Puterile lui 10 formează o submulțime infinită G = {…, 0,001, 0,01, 0,1, 1, 10, 100, 1000, …} a numerelor raționale. Această mulțime G este un grup ciclic⁠(d) în raport cu înmulțirea, iar 10 este generatorul. Pentru orice element a al grupului, se poate calcula log10a. De exemplu, log10 10000 = 4 și log10 0,001 = −3. Acestea sunt exemple ale problemei logaritmului discret.

Alți logaritmi în bază 10 din numerele reale nu sunt exemple ale problemei logaritmului discret, deoarece implică exponenți neîntregi. De exemplu, ecuația log10 53 = 1,724276... înseamnă că 10 1,724276... = 53. În timp ce exponenții întregi pot fi definiți în orice grup folosind produse și inverse, exponenții arbitrari din numerele reale necesită alte concepte, cum ar fi funcția exponențială.

Puterile unui număr real fix

[modificare | modificare sursă]

Un exemplu similar este valabil pentru orice număr real diferit de zero b. Puterile formează un subgrup multiplicativ G = {…, b −3, b −2, b −1, 1, b 1, b 2, b 3, …} al numerelor reale nenule. Pentru orice element a din G, se poate calcula logb a.

Aritmetica modulară

[modificare | modificare sursă]

Una dintre cele mai simple contexte pentru logaritmii discreți este grupul (Zp)×⁠(d). Acesta este grupul înmulțirii modulo⁠(d) p, cu p număr prim. Elementele sale sunt clase de congruență⁠(d) modulo p, iar produsul de grup a două elemente poate fi obținut prin înmulțirea obișnuită a elementelor întregi, urmată de reducerea modulo p.

Puterea k a unuia dintre numerele din acest grup poate fi calculată prin ridicarea la puterea k și apoi găsirea restului împărțirii acestuia la p. Când numerele implicate sunt mari, este mai eficient să se reducă modulo p de mai multe ori pe parcursul calculului. Indiferent de algoritmul specific utilizat, această operație se numește exponențiere modulară⁠(d). De exemplu, fie (Z17)× . Pentru a calcula 34 în acest grup, se calculează 34 = 81, apoi se împarte 81 la 17, obținând restul 13. Astfel 34 = 13 în grupul (Z17)×.

Logaritmul discret este doar operația inversă. De exemplu, considerăm ecuația 3k ≡ 13 (mod 17) pentru k. Din exemplul de mai sus, o soluție este k = 4, dar nu este singura soluție. Deoarece 316 ≡ 1 (mod 17) — după cum rezultă din mica teoremă a lui Fermat — rezultă, de asemenea, că dacă n este un număr întreg, atunci 34+16n ≡ 34 × (316)n ≡ 13 × 1 n ≡ 13 (mod 17). Prin urmare, ecuația are un număr infinit de soluții de forma 4 + 16n. Mai mult, deoarece 16 este cel mai mic număr întreg pozitiv m care satisface relația 3m ≡ 1 (mod 17), acestea sunt singurele soluții. În mod echivalent, mulțimea tuturor soluțiilor posibile poate fi exprimată prin constrângerea ca k ≡ 4 (mod 16).

Puterile elementului neutru

[modificare | modificare sursă]

În cazul special în care b este elementul neutru 1 al grupului G, logaritmul discret logb a este nedefinit pentru a diferit de 1, și orice număr întreg k este un logaritm discret pentru a = 1.

Proprietăți

[modificare | modificare sursă]

Puterile se supun identității algebrice obișnuite bk+l = bkbl . Cu alte cuvinte, funcția

definită prin f(k) = bk este un omomorfism de grup definit pe numerele întregi Z în raport cu operația de adunare, cu valori în subgrupul H al lui G generat⁠(d) de b. Pentru orice a din H, există logb a. În schimb, logb a nu există pentru a care nu sunt din H.

Dacă H este infinit, atunci logb a este, de asemenea, unic, iar logaritmul discret echivalează cu un izomorfism de grup⁠(d)

Pe de altă parte, dacă H este finit de ordinul n, atunci logb a este unic numai până la congruența modulo n⁠(d), iar logaritmul discret echivalează cu un izomorfism de grup

unde cu Zn se notează grupul aditiv de numere întregi modulo n.

Formula familiară de schimbare a bazei pentru logaritmii obișnuiți rămâne valabilă: Dacă c este un alt generator al lui H, atunci

Problemă nerezolvată în informatică:

Poate fi logaritmul discret calculat în timp polinomial pe un computer clasic?

Problema logaritmului discret este considerată netractabilă computațional. Adică, nu este cunoscut un algoritm clasic eficient pentru calculul logaritmilor discreți în general.

Un algoritm general pentru calculul logb a în grupuri finite G este de a ridica b la puteri din ce în ce mai mari k până când se găsește a. Acest algoritm este uneori numit înmulțire de încercare. Este nevoie de timp de rulare liniar în raport cu dimensiunea grupului G și, prin urmare, exponențial în raport cu numărul de cifre din dimensiunea grupului. Prin urmare, este un algoritm în timp exponențial, care este practic doar pentru grupuri G mici.

Există algoritmi mai sofisticați, de obicei inspirați de algoritmi similari pentru factorizarea întregilor. Acești algoritmi rulează mai repede decât algoritmul naiv, unii dintre ei fiind proporționali cu rădăcina pătrată a mărimii grupului și astfel exponențial la jumătate din numărul de cifre din dimensiunea grupului. Totuși, niciuna dintre ele nu rulează în timp polinomial (în numărul de cifre din dimensiunea grupului).

Există un algoritm cuantic eficient datorat lui Peter Shor⁠(d).[1]

Algoritmi clasici eficienți există și în anumite cazuri speciale. De exemplu, în grupul numerelor întregi modulo p în raport cu adunarea, puterea bk devine un produs bk, iar egalitatea înseamnă congruență modulo p în numerele întregi. Algoritmul lui Euclid extins⁠(d) găsește rapid p.

Cu Diffie–Hellman se folosește un grup ciclic modulo un număr prim p, ceea ce permite un calcul eficient al logaritmului discret cu Pohlig–Hellman dacă ordinul grupului (fiind p−1) este suficient de neted⁠(d), adică nu are factori primi mari.

Comparație cu factorizarea întregilor

[modificare | modificare sursă]

Calculul logaritmilor discreți și factorizarea numerelor întregi sunt probleme distincte, dar cele două au unele proprietăți în comun:

Există grupuri pentru care calculul logaritmilor discreți pare a fi deosebit de dificil. În unele cazuri (de exemplu, subgrupuri de ordin număr prim mare ale grupurilor (Zp)× ) nu numai că nu există un algoritm eficient cunoscut pentru cel mai rău caz, dar se poate demonstra că complexitatea cazului mediu este aproximativ la fel de dificilă ca și cel mai rău caz folosind autoreductibilitatea aleatorie⁠(d).

În același timp, problema inversă a exponențierii discrete nu este dificilă (poate fi calculată eficient folosind exponențiarea prin ridicarea la pătrat⁠(d), de exemplu). Această asimetrie este analogă cu cea dintre factorizarea numerelor întregi și înmulțirea lor. Ambele asimetrii (și alte posibile funcții unidirecționale⁠(d)) au fost exploatate în construcția sistemelor criptografice.

Opțiunile populare pentru grupul G în criptografia cu logaritmi discreți (DLC) sunt grupurile ciclice (Zp)× (de ex. Criptarea ElGamal⁠(d), schimbul de chei Diffie–Hellman⁠(d) și Digital Signature Algorithm) și subgrupurile ciclice ale curbelor eliptice pe corpuri finite.

Deși nu există un algoritm public cunoscut pentru rezolvarea problemei logaritmului discret în general, primii trei pași ai algoritmului ciurului algebric depind doar de grupul G, nu de elementele specifice ale lui G al căror logaritm finit este dorit. Prin precalcularea⁠(d) acestor trei pași pentru un grup specific, trebuie doar să se efectueze ultimul pas, care este mult mai puțin costisitor din punct de vedere computațional decât primii trei, pentru a obține un logaritm specific în acel grup.[2]

Se dovedește că mare parte din traficul de Internet utilizează unul dintre puținele grupuri care sunt de ordinul a 1024 de biți sau mai puțin, de exemplu grupuri ciclice de ordinul numere prime Oakley specificate în RFC 2409 . Atacul Logjam⁠(d) a folosit această vulnerabilitate pentru a compromite o varietate de servicii de internet care au permis utilizarea unor grupuri al căror ordin era un număr prim de 512 biți, așa-numitul export grade⁠(d).[2]

Autorii atacului Logjam estimează că precalcularea mult mai dificilă necesară pentru a rezolva problema logaritmului discret pentru un număr prim de 1024 de biți s-ar încadra în bugetul unei mari agenții naționale de informații,⁠(d) cum ar fi National Security Agency (NSA) din SUA. Autorii Logjam speculează că această precalculare împotriva unor numere prime 1024 DH reutilizate pe scară largă s-ar afla în spatele afirmațiilor din documentele NSA scurse cum că NSA ar fi capabilă să spargă o mare parte din criptografia actuală.[2]

  1. ^ Shor, Peter (). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing. 26 (5): 1484–1509. doi:10.1137/s0097539795293172. 
  2. ^ a b c Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel (octombrie 2015). „Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” (PDF). 
  • Rosen, Kenneth H. (). Elementary Number Theory and Its Application (ed. 6th). Pearson. p. 368. ISBN 978-0321500311. 
  • Weisstein, Eric W. „Discrete Logarithm”. MathWorld. Wolfram Web. Accesat în . 

Lectură suplimentară

[modificare | modificare sursă]