În matematică, pentru numerele reale date și , logaritmul este un număr astfel încât . Analog, în orice grup G, se poate defini pentru orice număr întreg puterea bk, iar logaritmul discret logb a este un număr întreg k astfel încât . În teoria numerelor, termenul cel mai frecvent utilizat este cel de indice: putem scrie x = indr a (mod m) (se citește „indicele lui în baza r modulo m”) pentru rx ≡ a (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ă.

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

În mod similar, fie produsul lui cu sine însuși de ori. Pentru , puterea este elementul neutru 0: .

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

Exemple

Puterile lui 10 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 în raport cu înmulțirea, iar 10 este generatorul. Pentru orice element al grupului, se poate calcula . 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 Un exemplu similar este valabil pentru orice număr real diferit de zero . 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 din G, se poate calcula .

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

Puterea a unuia dintre numerele din acest grup poate fi calculată prin ridicarea la puterea și apoi găsirea restului împărțirii acestuia la . Când numerele implicate sunt mari, este mai eficient să se reducă modulo de mai multe ori pe parcursul calculului. Indiferent de algoritmul specific utilizat, această operație se numește . 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 . 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 În cazul special în care este elementul neutru 1 al grupului G, logaritmul discret este nedefinit pentru diferit de 1, și orice număr întreg este un logaritm discret pentru .

Proprietăți Puterile se supun identității algebrice obișnuite . Cu alte cuvinte, funcția

definită prin 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 de . Pentru orice din H, există . În schimb, nu există pentru care nu sunt din H.

Dacă H este infinit, atunci este, de asemenea, unic, iar logaritmul discret echivalează cu un

Pe de altă parte, dacă H este finit de ordinul , atunci este unic numai până la , iar logaritmul discret echivalează cu un izomorfism de grup

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

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

Algoritmi

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 în grupuri finite G este de a ridica la puteri din ce în ce mai mari până când se găsește . 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 .

Algoritmi clasici eficienți există și în anumite cazuri speciale. De exemplu, în grupul numerelor întregi modulo în raport cu adunarea, puterea devine un produs , iar egalitatea înseamnă congruență modulo în numerele întregi. găsește rapid .

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

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

ambele sunt cazuri speciale ale pentru grupuri abeliene finite, ambele probleme par a fi dificile (nu sunt cunoscuți algoritmi eficienți pentru calculatoarele necuantice), pentru ambele probleme sunt cunoscuți algoritmi eficienți pe calculatoarele cuantice, algoritmii dintr-o problemă sunt adesea adaptați la cealaltă și dificultatea ambelor probleme a fost folosită pentru a construi diverse sisteme criptografice.

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

În același timp, problema inversă a exponențierii discrete nu este dificilă (poate fi calculată eficient folosind , de exemplu). Această asimetrie este analogă cu cea dintre factorizarea numerelor întregi și înmulțirea lor. Ambele asimetrii (și alte posibile ) 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. , ș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 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.

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

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, 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ă.

Note

Bibliografie

Lectură suplimentară ; . Chapter 5, Prime Numbers: A computational perspective, ed. a 2-a, Springer. 978-1-58488-508-5

Categorie:Logaritmi Categorie:Criptografie Categorie:Teoria grupurilor Categorie:Pagini cu traduceri nerevizuite