Logaritm discret

În matematică, pentru numerele reale date Format:Math și Format:Math, logaritmul Format:Math este un număr Format:Math astfel încât Format:Math. Analog, în orice grup G, se poate defini pentru orice număr întreg Format:Math puterea b^k, iar logaritmul discret log_b a este un număr întreg k astfel încât Format:Nowrap. În teoria numerelor, termenul cel mai frecvent utilizat este cel de indice: putem scrie x = ind_r a (mod m) (se citește „indicele lui Format:Math în baza r modulo m”) pentru r^x ≡ 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 Format:Math orice grup. Notăm operația de grup a acestuia cu semnele de înmulțire și elementul său neutru cu 1. Fie Format:Math orice element al lui Format:Math. Pentru orice număr întreg pozitiv Format:Math, expresia Format:Math reprezintă produsul lui Format:Math cu el însuși de Format:Math ori:

$b^k=\underset{k\text{factori}}{\underbrace{b\cdot b\cdots b}}.$

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

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

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 Format:Ill-wd în raport cu înmulțirea, iar 10 este generatorul. Pentru orice element Format:Math al grupului, se poate calcula Format:Math. De exemplu, log₁₀ 10000 = 4 și log₁₀ 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 log₁₀ 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 Format:Math. Puterile formează un subgrup multiplicativ G = {…, b ⁻³, b ⁻², b ⁻¹, 1, b ¹, b ², b ³, …} al numerelor reale nenule. Pentru orice element Format:Math din G, se poate calcula Format:Math.

Aritmetica modulară

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

Puterea Format:Math a unuia dintre numerele din acest grup poate fi calculată prin ridicarea la puterea Format:Math și apoi găsirea restului împărțirii acestuia la Format:Math. Când numerele implicate sunt mari, este mai eficient să se reducă modulo Format:Math de mai multe ori pe parcursul calculului. Indiferent de algoritmul specific utilizat, această operație se numește Format:Ill-wd. De exemplu, fie (Z₁₇)^× . Pentru a calcula 3⁴ în acest grup, se calculează 3⁴ = 81, apoi se împarte 81 la 17, obținând restul 13. Astfel 3⁴ = 13 în grupul (Z₁₇)^×.

Logaritmul discret este doar operația inversă. De exemplu, considerăm ecuația 3^k ≡ 13 (mod 17) pentru Format:Math. Din exemplul de mai sus, o soluție este k = 4, dar nu este singura soluție. Deoarece 3¹⁶ ≡ 1 (mod 17) — după cum rezultă din mica teoremă a lui Fermat — rezultă, de asemenea, că dacă n este un număr întreg, atunci 3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1 ⁿ ≡ 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 3^m ≡ 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 Format:Math este elementul neutru 1 al grupului G, logaritmul discret Format:Math este nedefinit pentru Format:Math diferit de 1, și orice număr întreg Format:Math este un logaritm discret pentru Format:Math.

Proprietăți

Puterile se supun identității algebrice obișnuite Format:Math . Cu alte cuvinte, funcția

$f:𝐙\to G$

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

Dacă H este infinit, atunci Format:Math este, de asemenea, unic, iar logaritmul discret echivalează cu un Format:Ill-wd

${\log }_b:H\to 𝐙.$

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

${\log }_b:H\to {𝐙}_n,$

unde cu Z_n se notează grupul aditiv de numere întregi modulo Format:Math.

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

${\log }_{c}a={\log }_{c}b\cdot {\log }_{b}a.$

Algoritmi

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

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

Cu Diffie–Hellman se folosește un grup ciclic modulo un număr prim Format:Math, ceea ce permite un calcul eficient al logaritmului discret cu Pohlig–Hellman dacă ordinul grupului (fiind Format:Math) este suficient de Format:Ill-wd, 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 Format:Ill-wd 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 (Z_p)^× ) 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 Format:Ill-wd.

În același timp, problema inversă a exponențierii discrete nu este dificilă (poate fi calculată eficient folosind Format:Ill-wd, de exemplu). Această asimetrie este analogă cu cea dintre factorizarea numerelor întregi și înmulțirea lor. Ambele asimetrii (și alte posibile Format:Ill-wd) au fost exploatate în construcția sistemelor criptografice.

Opțiunile populare pentru grupul G în criptografia cu logaritmi discreți (DLC) sunt grupurile ciclice (Z_p)^× (de ex. Format:Ill-wd, Format:Ill-wd ș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 Format:Ill-wd 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 Format:Ill-wd 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 Format:Ill-wd.

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 Format:Ill-wd 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ă.

Bibliografie

• Format:Cite book
• Format:Cite web

Lectură suplimentară

• Format:Ill-wd ; Format:Ill-wd. Chapter 5, Prime Numbers: A computational perspective, ed. a 2-a, Springer.
• Format:Citation978-1-58488-508-5