Puncte:6

De ce nu putem folosi funcția Zeta pentru a căuta factori primi în RSA?

drapel cn

Poate am înțeles greșit, dar dacă funcția Zeta este eficientă de calculat și inversat și dacă presupunerea lui Riemann este adevărată (ceea ce pare), nu putem folosi funcția Zeta pentru a găsi eficient factorii primi ai numerelor mari și pentru a găsi privați? cheile cheilor publice RSA?

kelalaka avatar
drapel in
Bun venit pe Cryptography.se. Ce vrei să spui prin _eficient de calculat și inversat_?
stimulate avatar
drapel cn
@kelalaka eficient de calculat: practic calculabil în timp mai puțin decât exponențial, respectiv primul pe care îl căutăm; invers: eficient pentru a găsi intrarea în zeta pentru un număr prim dat.
Puncte:11
drapel ru

În primul rând, nu cred asta $\zeta(e)$ este atât de eficient de calculat. Interesul nostru de a calcula $\zeta(e)$ pentru scopuri teoretice ale numerelor prime se concentrează de obicei pe linia critică $\mathrm{Re}s=1/2$ si Formula Riemann-Siegel cere $O(t^{1/2})$ termeni de calculat $\zeta(1/2+it)$. Există accelerații pentru calcularea valorilor multiple, dar nu în mod dramatic.

La fel, nu sunt sigur ce vrei să spui prin invers. Funcția nu este bijectivă (știm multe locuri unde este zero de exemplu).

Acestea fiind spuse, au existat câteva idei despre utilizarea teoriei numerelor analitice pentru metodele de factorizare. Metoda de factorizare a grupurilor de clasă a lui Shanks poate fi accelerată dacă se poate aproxima $L(1,\chi_N)$ (aici $L$-funcția este pentru câmpul numeric $\mathbb Q(\sqrt N)$ și este strâns legată de $\zeta(e)$. Presupunând ipoteza Riemann generalizată, Shanks a reușit să reducă timpul de rulare al algoritmului său pentru a factora $N$ din $O(N^{1/4+\epsilon})$ la $O(N^{1/5+\epsilon})$. Este puțin probabil ca o astfel de complexitate să factorizeze numere mai mari de câteva sute de biți și cu care nu poate concura sita de câmp cu număr general.

Au existat idei de folosit $\zeta(e)$ în sine (a se vedea lucrarea recentă "Factorizarea cu indicii" de Sica de exemplu), dar aceștia se luptă să se apropie de complexitatea metodelor lui Shanks din anii 1970 (lucrarea Sica are complexitate $O(N^{1/3+\epsilon})$.)

Puncte:4
drapel us

Nu putem folosi funcția Zeta pentru a găsi eficient factorii primi ai numerelor mari și pentru a găsi cheile private ale cheilor publice RSA?

Pe scurt: The $\zeta$ funcţie nu dă acces la numere prime individuale (Nu cunosc nicio formulă care să existe), așa că, chiar dacă avem o metodă de calcul super-rapidă, nu poate fi folosită pentru găsi numere prime.


  • Ce $\zeta$ funcția oferă acces la, este de exemplu număr de numere prime între $1$ și $x$, adică funcția de numărare a primelor $\pi(x)$.

    Există într-adevăr o relație între funcția de numărare a primelor $\pi(x)$, și toate zerourile $\rho$ a lui Riemann $\zeta$ funcţie:

    $$\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac 12}\ ln(1-x^{{-2}}).$$

    Aici gandeste-te $\psi_0(x)$ ca ceva foarte apropiat de $\pi(x)$ în idee, dar doar numără numerele prime cu o altă pondere decât $1$ pentru fiecare prim, în schimb greutatea este $\log p$. Acest lucru omite detalii, dar dă ideea. Vedea Aici pentru mai multe precizii.

  • Produsul Euler pentru $\zeta$ funcția implică toate numerele prime, dar nu oferă o modalitate eficientă de a genera/găsi numere prime:

    $$\zeta(s) = \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{ \frac {1}{1-p^{-s}}}$$

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.