înregistrare Logare
Puncte:6
LinusK avatar Crypto

De ce este grea problema logaritmului discret?

drapel de
LinusK

De ce se presupune că problema logaritmului discret este grea?

Altcineva a pus aceeași întrebare dar răspunsurile explică doar că exponențiația este în $O(\log(n))$ în timp ce se află cei mai rapidi algoritmi cunoscuți pentru a calcula logaritmi discreti $O(n)$. (Pasesc aici detalii precum timpul de execuție al calculului indexului.)

În altă parte am citit: „Presumăm că logaritmii discreti sunt grei pentru că timp de peste 40 de ani oamenii foarte deștepți nu au reușit să găsească un algoritm rapid”.

Acum, mă întreb dacă există argumente mai bune. Puteți explica de ce sunt dificili logaritmii discreti?

1417
0 + 0
kelalaka avatar
drapel in
kelalaka
[Logaritmul discret: dat fiind un p, ce înseamnă să găsești logaritmul discret al lui x la baza y?](https://crypto.stackexchange.com/q/76230/18298)
2
Răspunde
WizardOfMenlo avatar
drapel ph
WizardOfMenlo
Doar o notă rapidă, de fapt, puteți calcula jurnalul discret (într-un grup general) în operațiuni de grup $O(\sqrt{n})$ (folosind, de exemplu, Pollard Rho). Vezi, de exemplu, „O introducere în criptografia matematică” secțiunea 5.5
0
Răspunde
Puncte:15
poncho avatar Crypto
drapel my
poncho

Acum, mă întreb dacă există argumente mai bune.

Până la urmă, nu, nu chiar.

Nu avem nicio dovadă că calcularea jurnalelor discrete este dificilă. De altfel, nu avem nicio dovadă că există vreo problemă în interior $NP$ (adică orice problemă în care, dacă răspunsul este „da”, există o dovadă care poate fi verificată rapid) este grea.

Avem câteva dovezi parțiale, de exemplu, că în modelul „cutie neagră”, un jurnal discret pe un grup de ordin principal este greu. Pe de altă parte, ipotezele care fac este cunoscută a fi falsă pentru câmpuri finite și, prin urmare, este mai puțin util decât s-ar spera.

0 + 0
LinusK avatar
drapel de
LinusK
Nu puteți susține, de exemplu, că în timpul exponențiării fiecare dintre pătraturile $\log(n)$ șterge un pic de informație deoarece $x \cdot x == -x \cdot -x$?
0
Răspunde
poncho avatar
drapel my
poncho
@LinusK: nu chiar; dacă $g$ are ordinul $q$, atunci $g^x$ pentru $x \in \{0, ..., q-1\}$ este injectiv - adică nu pierde *nicio* informație . Și astfel, în timp ce un subpas comun de implementare (pătratarea) poate pierde informații, în general nu există nicio pierdere de informații.
4
Răspunde
LinusK avatar
drapel de
LinusK
Dar dacă $\mathbb{F}_p$ cu $p=2q+1$ și $g$ are ordinul $q$, atunci $g^x$ pentru $\{0,...,p-1\}$ nu este injectiv. Și dacă $g^{x_1} == g^{x_2}$ pentru un $x_1 \neq x_2$, atunci atât bitul cel mai mic de $x_1$ cât și $x_2$ (biții hardcore) trebuie să fie diferiți. De aceea am crezut că trebuie să fie ceva pierderi de informații.
0
Răspunde
poncho avatar
drapel my
poncho
@LinusK: totuși, în acest caz, $x_1 \equiv x_2 \pmod q$; prin urmare, există în esență o singură soluție (știind că îți oferă imediat toate celelalte)
3
Răspunde
drapel sh
Paŭlo Ebermann
Ce este un „grup dur”?
0
Răspunde
poncho avatar
drapel my
poncho
@PaÅloEbermann: Îmi pare rău, am schimbat modul în care am vrut să exprim asta în timp ce l-am scris și a rămas un „greu” suplimentar. Are modificarea mai mult sens?
0
Răspunde
drapel sa
K.G.
De asemenea, modelul de grup generic nu surprinde calculul cuantic, ceea ce pare să îl facă, de asemenea, mai puțin util decât se dorește.
0
Răspunde
poncho avatar
drapel my
poncho
@K.G.: destul de adevărat - chiar dacă (cred) algoritmul lui Shor poate funcționa într-o implementare de grup cutie neagră încurcată, acesta este un model de calcul diferit...
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.