înregistrare Logare
Puncte:1
avatar Crypto

Cum să alegeți legatura de netezime potrivită în timp ce utilizați metoda de calcul al indexului

drapel et
user93353

În timp ce implementați sita cuadratică, manualele oferă o formulă aproximativă pentru ce legat de netezime ar trebui să utilizați în baza de factori.

Pentru a factoriza un număr N folosind sita cuadratică, putem folosi următoarele:

$L = e^{\sqrt {\ln(N)ln(ln(N))}}$, $B = L^{\frac {1}{\sqrt 2}}$

Pentru metoda Index Calculus pentru rezolvarea problemei Discrete Log in $\mathbb F_p$, există o formulă similară? Multe dintre textele pe care le-am verificat, spuneți doar să alegeți un B potrivit pentru netezime. Dar nu dați nicio indicație despre cum alegeți un B potrivit.

117
1 + 0
Puncte:1
avatar Crypto
drapel pe
Samuel Neves

Coppersmith, Odlyzko și Schroeppel stabilit inițial $B = L[1/2, 1/2]$ atât pentru sitele liniare cât și pentru cele gaussiene. Pomerance a stabilit $B = L[1/2, 1/\sqrt{2}]$ pentru o variantă riguroasă de calcul a indicelui folosind metoda curbei eliptice ca metodă de testare a netezirii.

Aceste limite sunt doar asimptotice; limita într-o implementare va fi de obicei ajustată pentru a ține cont de performanța reală non-asimptotică a subrutinelor implicate.

0 + 7
drapel et
user93353
Am încercat această formulă cu câteva exemple rezolvate în unele cărți și rezultatul pare destul de diferit de ceea ce au folosit exemplele. Pentru ex.în cartea de criptografie matematică a lui Silverman, el rezolvă $37^x \equiv 211 \pmod 18443$. Dacă folosesc formula $B = L^{\frac {1}{\sqrt 2}}$, obțin 28,5. Cu toate acestea, pentru a rezolva problema, Silverman folosește B=5, care este destul de departe de B calculat. Silverman are și o problemă de exercițiu $17^x \equiv 19 \pmod 19079$, unde B calculat ar fi 28,5, dar eu sunt capabil pentru a o rezolva din nou folosind B=5.
0
Răspunde
drapel et
user93353
Ce vrei să spui prin ` cu avorturi timpurii, ca tester de netezime.`?
0
Răspunde
drapel et
user93353
De ce există 2 formule, adică de ce $B = L[1/2, 1/\sqrt{2}]$ - care este $L^{1/2}$
0
Răspunde
drapel pe
Samuel Neves
Dacă te uiți la cartea lui Silverman, sfârșitul Secțiunii 3.8 de la pagina 169 ar fi răspuns la întrebarea ta. Nu acordați prea multă atenție parametrilor din exemple, aceștia sunt optimizați mai degrabă pentru claritate decât performanță (adică, ar arăta mai rău ca un exemplu lucrat să aibă prea multe numere prime, sunt necesare mult mai multe relații etc.)
0
Răspunde
drapel pe
Samuel Neves
$L[1/2, 1/\sqrt{2}]$ este [notația L] mai generală (https://en.wikipedia.org/wiki/notația L). Înseamnă același lucru cu $L^{1/\sqrt{2}}$.
0
Răspunde
drapel et
user93353
Vă mulțumesc - puteți, de asemenea, să-mi spuneți ce înțelegeți prin „cu întreruperi anticipate, ca tester de netezime.”
0
Răspunde
drapel pe
Samuel Neves
Nu contează, am confundat asta cu o altă lucrare Pomerance. Aici este doar ECM. Dar asta nu contează prea mult; va funcționa și divizia de încercare, cu un timp de rulare ceva mai prost.
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.