Vizualizare sursă pentru „Logaritm discret”

În [[matematică]], pentru [[Număr real|numerele reale date]] {{Math|''a''}} și {{Math|''b''}}, [[Logaritm|logaritmul]] {{Math|log<sub>''b''</sub> a}} este un număr {{Math|''x''}} astfel încât {{Math|1=''b''<sup>''x''</sup> = ''a''}}. Analog, în orice [[Grup (matematică)|grup]] ''G'', se poate defini pentru orice număr întreg {{Math|''k''}}  puterea ''b''<sup>''k''</sup>, iar '''logaritmul discret''' log<sub>''b''</sub>&#x2009;''a'' este un număr întreg ''k'' astfel încât {{Nowrap|1=''b''<sup>''k''</sup> = ''a''}}. În [[teoria numerelor]], termenul cel mai frecvent utilizat este cel de '''indice''': putem scrie ''x'' = ind<sub>''r''</sub> ''a'' (mod&nbsp;''m)'' (se citește „indicele lui {{Math|''a''}} în baza ''r'' modulo&nbsp;''m''”) pentru ''r''<sup>''x''</sup> ≡ ''a'' (mod&nbsp;''m'' ) dacă ''r'' este o rădăcină primitivă a lui ''m'' și [[Cel mai mare divizor comun|cmmdc]] (''a'', ''m'')&nbsp;=&nbsp;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 [[Criptografie asimetrică|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 {{Math|''G''}} orice grup. Notăm [[Grup (matematică)|operația de grup]] a acestuia cu semnele de înmulțire și [[Element neutru|elementul său neutru]] cu 1. Fie {{Math|''b''}} orice element al lui {{Math|''G''}}. Pentru orice număr întreg pozitiv {{Math|''k''}}, expresia {{Math|''b''<sup>''k''</sup>}} reprezintă produsul lui {{Math|''b''}} cu el însuși de {{Math|''k''}} ori:

: <math>b^k = \underbrace{b \cdot b \cdots b}_{k \; \text{factori}}.</math>

În mod similar, fie {{Math|''b''<sup>&minus;''k''</sup>}} produsul lui {{Math|''b''<sup>&minus;1</sup>}} cu sine însuși de {{Math|''k''}} ori. Pentru {{Math|1=''k''=0}}, puterea {{Math|''k''}} este [[Element neutru|elementul neutru]] 0: {{Math|1=''b''<sup>0</sup>=1}}.

Fie {{Math|''a''}} un element al lui {{Math|''G''}}''.'' Un întreg {{Math|''k''}}, care rezolvă ecuația {{Math|1=''b''<sup>''k''</sup> = ''a''}} se numește '''logaritmul discret''' (sau pur și simplu '''logaritmul,''' în acest context) din {{Math|''a''}} în bază {{Math|''b''}}''.'' Se scrie {{Math|1=''k'' = log<sub>''b''</sub> ''a''}} .

== Exemple ==

=== Puterile lui 10 ===
Puterile lui 10 formează o submulțime infinită ''G'' = {…, 0,001, 0,01, 0,1, 1, 10, 100, 1000, …} a [[Număr rațional|numerelor raționale]]. Această mulțime ''G'' este un {{Ill-wd|Q245462|3=grup ciclic}} în raport cu înmulțirea, iar 10 este generatorul. Pentru orice element {{Math|''a''}} al grupului, se poate calcula {{Math|log<sub>10</sub> ''a''}}. De exemplu, log<sub>10</sub>&#x2009;10000 = 4 și log<sub>10</sub>&#x2009;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<sub>10</sub>&#x2009;53 = 1,724276... înseamnă că 10 <sup>1,724276...</sup> = 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ție exponențială|funcția exponențială]].

=== Puterile unui număr real fix ===
Un exemplu similar este valabil pentru orice număr real diferit de zero {{Math|''b''}}. Puterile formează un subgrup multiplicativ ''G'' = {…, ''b'' <sup>−3</sup>, ''b'' <sup>−2</sup>, ''b'' <sup>−1</sup>, 1, ''b'' <sup>1</sup>, ''b'' <sup>2</sup>, ''b'' <sup>3</sup>, …} al numerelor reale nenule. Pentru orice element {{Math|''a''}} din ''G'', se poate calcula {{Math|log<sub>''b''</sub> ''a''}}.

=== Aritmetica modulară ===
Una dintre cele mai simple contexte pentru logaritmii discreți este grupul {{Ill-wd|Q1169249|3=('''Z'''<sub>''p''</sub>)<sup>×</sup>}}. Acesta este grupul înmulțirii {{Ill-wd|Q319400|3=modulo}} {{Math|''p''}}, cu {{Math|''p''}} număr prim. Elementele sale sunt {{Ill-wd|Q319400|3=clase de congruență}} modulo {{Math|''p''}}, iar produsul de grup a două elemente poate fi obținut prin înmulțirea obișnuită a elementelor întregi, urmată de reducerea modulo&nbsp;{{Math|''p''}}.

[[Putere (matematică)|Puterea]] {{Math|''k''}} a unuia dintre numerele din acest grup poate fi calculată prin ridicarea la puterea {{Math|''k''}} și apoi găsirea restului împărțirii acestuia la {{Math|''p''}}. Când numerele implicate sunt mari, este mai eficient să se reducă modulo {{Math|''p''}} ''de'' mai multe ori pe parcursul calculului. Indiferent de algoritmul specific utilizat, această operație se numește {{Ill-wd|Q1228841|3=exponențiere modulară}}. De exemplu, fie ('''Z'''<sub>17</sub>)<sup>×</sup> . Pentru a calcula 3<sup>4</sup> în acest grup, se calculează 3<sup>4</sup> = 81, apoi se împarte 81 la 17, obținând restul 13. Astfel 3<sup>4</sup> = 13 în grupul ('''Z'''<sub>17</sub>)<sup>×</sup>.

Logaritmul discret este doar operația inversă. De exemplu, considerăm ecuația 3<sup>''k''</sup> ≡ 13 (mod 17) pentru {{Math|''k''}}. Din exemplul de mai sus, o soluție este ''k''&nbsp;=&nbsp;4, dar nu este singura soluție. Deoarece 3<sup>16</sup> ≡ 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<sup>4+16''n''</sup> ≡ 3<sup>4</sup> × (3<sup>16</sup>)<sup>''n''</sup> ≡ 13 × 1 <sup>''n''</sup> ≡ 13 (mod 17). Prin urmare, ecuația are un număr infinit de soluții de forma 4 + 16''n''. Mai mult, deoarece 16 este cel mai mic număr întreg pozitiv ''m'' care satisface relația 3<sup>''m''</sup> ≡ 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 {{Math|''b''}} este elementul neutru 1 al grupului ''G'', logaritmul discret {{Math|log<sub>''b''</sub> ''a''}} este [[expresie nedefinită|nedefinit]] pentru {{Math|''a''}} diferit de  1, și orice număr întreg {{Math|''k''}} este un logaritm discret pentru {{Math|1=''a'' = 1}}.

== Proprietăți ==
Puterile se supun identității algebrice obișnuite {{Math|1=''b''<sup>''k''+''l''</sup> = ''b''<sup>''k''</sup>''b''<sup>''l''</sup>}} . Cu alte cuvinte, funcția

: <math>f \colon \mathbf{Z} \to G</math>

definită prin {{Math|1=''f''(''k'') = ''b''<sup>''k''</sup>}} este un [[Morfism de grupuri|omomorfism de grup]] definit pe numerele întregi '''Z''' în raport cu operația de adunare, cu valori în [[Subgrup|subgrupul]] ''H'' al lui ''G'' {{Ill-wd|Q734209|3=generat}} de {{Math|''b''}}. Pentru orice {{Math|''a''}} din ''H'', există {{Math|log<sub>''b''</sub> ''a''}}. În schimb, {{Math|log<sub>''b''</sub> ''a''}} nu există pentru ''{{Math|''a''}}'' care nu sunt din ''H''.

Dacă ''H'' este infinit, atunci {{Math|log<sub>''b''</sub> ''a''}} este, de asemenea, unic, iar logaritmul discret echivalează cu un {{Ill-wd|Q742064|3=izomorfism de grup}}

: <math>\log_b \colon H \to \mathbf{Z}.</math>

Pe de altă parte, dacă ''H'' este finit de [[Ordin (teoria grupurilor)|ordinul]] ''{{Math|''n''}}'', atunci {{Math|log<sub>''b''</sub> ''a''}} este unic numai până la {{Ill-wd|Q319400|3=congruența modulo ''n''}}, iar logaritmul discret echivalează cu un izomorfism de grup

: <math>\log_b\colon H \to \mathbf{Z}_n,</math>

unde cu '''Z'''<sub>''n''</sub> se notează grupul aditiv de numere întregi modulo ''{{Math|''n''}}''.

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

: <math>\log_c a = \log_c b \cdot \log_b a.</math>

== Algoritmi ==
{{Unsolved|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 {{Math|log<sub>''b''</sub> ''a''}} în [[Grup finit|grupuri finite]] ''G'' este de a ridica ''{{Math|''b''}}'' la puteri din ce în ce mai mari ''{{Math|''k''}}'' până când se găsește ''{{Math|''a''}}''. Acest algoritm este uneori numit ''înmulțire de încercare''. Este nevoie de [[Complexitate în timp|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 [[Complexitate în timp|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 [[Complexitate în timp|timp polinomial]] (în numărul de cifre din dimensiunea grupului).

Există un algoritm cuantic eficient datorat lui {{Ill-wd|Q370071|3=Peter Shor}}.<ref>{{Citat revistă|nume=Shor|prenume=Peter|an=1997|titlu=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer|journal=SIAM Journal on Computing|volum=26|număr=5|pagini=1484–1509|doi=10.1137/s0097539795293172}}</ref>

Algoritmi clasici eficienți există și în anumite cazuri speciale. De exemplu, în grupul numerelor întregi modulo ''{{Math|''p''}}'' în raport cu adunarea, puterea {{Math|''b''<sup>''k''</sup>}} devine un produs {{Math|''bk''}}, iar [[egalitate (matematică) |egalitatea]] înseamnă congruență modulo ''{{Math|''p''}}'' în numerele întregi. {{Ill-wd|Q1362750|3=Algoritmul lui Euclid extins}} găsește rapid ''{{Math|''p''}}.''

Cu [[schimbul de chei Diffie–Hellman|Diffie–Hellman]] se folosește un grup ciclic modulo un număr prim {{Math|''p''}}, ceea ce permite un calcul eficient al logaritmului discret cu Pohlig–Hellman dacă [[Ordin (teoria grupurilor)|ordinul grupului]] (fiind {{Math|''p''&minus;1}}) este suficient de {{Ill-wd|Q1529876|3=neted}}, adică nu are [[Descompunerea în factori primi|factori primi]] mari.

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

* ambele sunt cazuri speciale ale {{Ill-wd|Q5752087|3=problemei subgrupurilor ascunse}} pentru [[Grup abelian|grupuri abeliene]] finite,
* ambele probleme par a fi dificile (nu sunt cunoscuți [[Algoritm|algoritmi]] eficienți pentru  [[Calculator cuantic|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 [[Criptografie|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'''<sub>''p''</sub>)<sup>×</sup> ) 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 {{Ill-wd|Q7291990|3=autoreductibilitatea aleatorie}}.

În același timp, problema inversă a exponențierii discrete nu este dificilă (poate fi calculată eficient folosind {{Ill-wd|Q864127|3=exponențiarea prin ridicarea la pătrat}}, de exemplu). Această asimetrie este analogă cu cea dintre factorizarea numerelor întregi și [[Înmulțire (matematică)|înmulțirea]] lor. Ambele asimetrii (și alte posibile {{Ill-wd|Q720931|3=funcții unidirecționale}}) au fost exploatate în construcția sistemelor criptografice.

Opțiunile populare pentru grupul ''G'' în [[Criptografie|criptografia]] cu logaritmi discreți (DLC) sunt grupurile ciclice ('''Z'''<sub>''p''</sub>)<sup>×</sup> (de ex. {{Ill-wd|Q1162410|3=Criptarea ElGamal}}, {{Ill-wd|Q623447|3=schimbul de chei Diffie–Hellman}} și [[Digital Signature Algorithm]]) și subgrupurile ciclice ale [[Curbe eliptice|curbelor eliptice]] pe [[Corp finit|corpuri finite]].

Deși nu există un algoritm public cunoscut pentru rezolvarea problemei logaritmului discret în general, primii trei pași ai [[ciurul câmpurilor de numere generalizat|algoritmului ciurului algebric]] depind doar de grupul ''G'', nu de elementele specifice ale lui ''G'' al căror logaritm finit este dorit. Prin {{Ill-wd|Q7239568|3=precalcularea}} 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.<ref name="imperfectfs">{{Citat web|url=https://weakdh.org/imperfect-forward-secrecy.pdf|nume=Adrian|titlu=Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice|date=October 2015|first1=David|last2=Bhargavan|last3=Durumeric|last4=Gaudry|last5=Green|last6=Halderman|last7=Heninger|last8=Springall|last9=Thomé|first2=Karthikeyan|first3=Zakir|first4=Pierrick|first5=Matthew|first6=J. Alex|first7=Nadia|first8=Drew|first9=Emmanuel}}</ref>

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 {{Ill-wd|Q19984009|3=Logjam}} 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 {{Ill-wd|Q3733198|3=export grade}}.<ref name="imperfectfs"/>

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 {{Ill-wd|Q47913|3=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 [[Dezvăluirile lui Edward Snowden|documentele NSA scurse]] cum că NSA ar fi capabilă să spargă o mare parte din criptografia actuală.<ref name="imperfectfs"/>

== Note ==
<references/>

== Bibliografie ==
* {{cite book |last1=Rosen |first1=Kenneth H.|title=Elementary Number Theory and Its Application |year=2011|publisher=Pearson |isbn=978-0321500311 |page=368 |edition=6th}}
* {{cite web |last1=Weisstein |first1=Eric W.|title=Discrete Logarithm |url=http://mathworld.wolfram.com/DiscreteLogarithm.html |website=MathWorld |publisher=Wolfram Web|access-date=1 January 2019}}

== Lectură suplimentară ==
* {{Ill-wd|Q92693|3=Richard Crandall}} ; {{Ill-wd|Q761544|3=Carl Pomerance}}. Chapter 5, ''Prime Numbers: A computational perspective'', ed. a 2-a, Springer.
* {{Citation|last=Stinson|first=Douglas Robert|title=Cryptography: Theory and Practice|year=2006|edition=3rd|place=London|publisher=[[CRC Press]]|isbn=978-1-58488-508-5}}<bdi><cite class="citation cs2" data-ve-ignore="true" id="CITEREFStinson2006">[[Special:BookSources/978-1-58488-508-5|978-1-58488-508-5]]</cite></bdi>
{{Portal|Matematică}}

[[Categorie:Logaritmi]]
[[Categorie:Criptografie]]
[[Categorie:Teoria grupurilor]]
[[Categorie:Pages with unreviewed translations]]