înregistrare Logare
Puncte:1
avatar Crypto

De ce este folosit factorial în algoritmul $p - 1$ al lui Pollard?

drapel et
user93353

De ce anume folosim factorial pentru găsirea unui $L$ care este divizibil cu $p - 1$?

Algoritmul lui Pollard este despre numere B-powersmooth și nu numere B-smooth. Deci, unde anume intervine factorialul? Factorialele nu se fac prin puterea nimic - este doar o multiplicare de numere fără nicio exponențiere.

Mă refer la Pollard's $p - 1$ algoritmul descris în cartea Criptografie matematică a lui Silverman - unde verifică $a^{j!} - 1$ într-o buclă (cu j crescând) până găsesc dreptul $gcd(a^{j!} - 1)$ ceea ce duce la un factor.

Înțeleg partea în care Mica Teoremă a lui Fermat este folosită pentru a arăta că L este astfel încât $p-1$ desparte $a^L - 1$ & $q-1$ nu se împarte $a^L - 1$ - întrebarea mea nu are legătură cu asta. Întrebarea mea este de ce/cum se încearcă ${j!}$ (adică încercând factoriali) lucrează pentru a găsi un potrivit $L$?

137
1 + 0
Puncte:3
SSA avatar Crypto
drapel ng
SSA

Teorema Fermat Se află în spatele acestei a doua scheme de factorizare, cunoscută sub numele de metoda Polard p-1.

  • să presupunem că întregul compus impar n care trebuie factorizat are divizorul prim n, cu proprietatea că p-1 este un produs de numere prime relativ mici. Fie q atunci orice număr întreg astfel încât (p-1)|q. De exemplu, q ar putea fi fie k! sau cel mai mic multiplu comun al primului k întregi pozitivi, unde k este considerat suficient de mare. selectați 1<a<p-1
  • $${m\equiv a^q \equiv a^{(p-1)j}\equiv 1^j \equiv1(modp)}$$ implică p | (m-1), aceasta forțează ${gcd(m-1,n)>1}$
  • Dar este important de reținut că aici este , dacă ${gcd(m-1,n)=1}$, apoi ar trebui să reveniți și să selectați valoarea diferită a lui a.
  • Metoda ar putea eșua dacă q (k!) nu este considerat suficient de mare; adică dacă p-1 conține un factor prim mare sau un prim mic care apare la o putere mare, de aceea este mai bine să alegem k!, decât să ghicim orice număr mare nou de fiecare dată când obținem ${gcd(m-1,n)=1}$, prin urmare factorial este o alegere mai bună și poate crește probabilitatea de a afla dacă un factor este un factor prim mare.
0 + 10
drapel et
user93353
Am înțeles deja ceea ce ai explicat mai sus - despre utilizarea fermat pentru a demonstra că L este astfel încât $p-1$ împarte $a^L - 1$ și $q-1$ nu împarte $a^L - 1$ - întrebarea mea nu are legătură cu asta. Întrebarea mea este de ce/cum face ${k!}$ -adică. încercarea factorilor de lucru pentru a găsi un $L $ potrivit?
0
Răspunde
drapel et
user93353
De ce este factorial o alegere mai bună pentru a găsi $L$? Sau, ca să fiu sincer, nici nu înțeleg de ce este o alegere în primul rând?
0
Răspunde
SSA avatar
drapel ng
SSA
atunci când doriți să încercați numere diferite care pot sări la valori mari la fiecare pas, factorul ajută, în două cazuri, [1] dacă aveți un factor prim mare sau [2] un prim mic cu putere mare. deci in 10! , ai puterea de 2 este 8, pentru că 3 este 2 etc.de asemenea, am menționat că această metodă funcționează bine atunci când p-1 este un produs de prim relativ mic. Crezi că este vreo variantă mai bună?
0
Răspunde
drapel et
user93353
Nu mă gândesc deloc la nicio opțiune :-) Sunt un noob.
0
Răspunde
drapel et
user93353
`ai puterea de 2 este 8, pentru 3 este 2, etc` - ce vrei să spui pentru 3 este 2?.
0
Răspunde
drapel et
user93353
Deci 10! conține (2, 2^2, 2^3), (3, 3^2) și astfel orice factorial este format din puteri prime - și, prin urmare, aceasta este o modalitate bună de a găsi L - asta este ceea ce spui, nu?
0
Răspunde
SSA avatar
drapel ng
SSA
da, sunt numere prime impare mici, p-1 și q-1 sunt numere întregi netede. corectand in 10!, 3 are puterea de 4.
0
Răspunde
drapel pe
Samuel Neves
În cea mai mare parte, factorialul nu este folosit pentru $p-1$. Sau cel puțin nu ar trebui să fie. Vezi răspunsul meu [aici](https://crypto.stackexchange.com/a/72884/592).
0
Răspunde
drapel et
user93353
@SamuelNeves - majoritatea cărților la care m-am uitat par să folosească Factorial mai degrabă decât LCM. Nici măcar nu vorbesc despre LCM. Pentru ex.Criptografia matematică a lui Silverman, cartea lui Smart, Joy of Factoring. Metoda LCM este menționată doar într-o mică parte din cărți. Ai idee de ce este așa?
0
Răspunde
drapel et
user93353
@SamuelNeves - un alt lucru cu cartea lui Silverman este că pare să se uite la B-smooth (p-1) mai degrabă decât la B-powersmooth (p-1). Și pare să implice că, dacă p-1 este B-smooth, atunci trebuie să mergeți până la B!, în timp ce metodele LCM par să spună că dacă p-1 este B-powersmooth, atunci trebuie să mergeți până la LCM (1 la B) . Aceasta este, de asemenea, o chestiune de confuzie.
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.