înregistrare Logare
Puncte:1
mangart avatar Crypto

Găsirea unui element de $\mathbb{Z}_p$ dacă ordinea acelui element este cunoscută

drapel cn
mangart

Am două numere prime $p$ (1024 biți) și $q$ (160 de biți) astfel încât $q$ desparte $p-1$. Acum vreau să găsesc un element $b$ în $\mathbb{Z}_p$ cu ordinul de $q$. Asta inseamna ca $b^q \equiv 1 \mod p$.

Am încercat să aleg $b$ la întâmplare și apoi verificați dacă congruența este valabilă, dar se pare că aceasta nu este o abordare bună, deoarece nu oferă un răspuns într-un timp rezonabil. Deci există vreo modalitate de a găsi $b$ eficient?

32
0 + 0
drapel us
Mikero
Cred că aceasta este o întrebare diferită, deoarece găsirea unui generator prin încercare și eroare va fi mult mai ușoară decât găsirea unui element cu o ordine diferită. Cred că probabilitatea de a lovi un element cu ordin non-trivial este $1 - \varphi(n)/n$ care este în general neglijabil aproape de zero (probabilitatea de a lovi un generator este $\varphi(n)/n$). Acest lucru sugerează necesitatea unei abordări mai eficiente decât încercarea și eroarea, care funcționează pentru găsirea unui generator.
0
Răspunde
kelalaka avatar
drapel in
kelalaka
**Din răspunsul lui Poncho:** O modalitate ușoară de a selecta un generator aleatoriu este de a selecta o valoare aleatorie $h$ între 2 și $p-1$ și de a calcula $h^{(p-1)/q} \bmod p$; dacă acea valoare nu este 1 (și cu mare probabilitate, nu va fi), atunci $h^{(p-1)/q} \bmod p$ este generatorul tău aleatoriu.
2
Răspunde
mangart avatar
drapel cn
mangart
@kelalaka Din câte știu, un generator este un element care poate genera toate elementele grupului și astfel ordinea acelui element ar fi $p-1$, dar încerc să găsesc un element $b$ care are ordinul $q$ care este mult mai mic decât $p-1$ și, de asemenea, $b$ prin această definiție nu este un generator al grupului.
0
Răspunde
kelalaka avatar
drapel in
kelalaka
Asta include răspunsul. Citește cu atenție.
1
Răspunde
mangart avatar
drapel cn
mangart
@kelalaka Oh, văd, răspunsul este de fapt în articolul Wikipedia legat în acel răspuns, despre grupul Schnorr. Deci asta chiar răspunde la întrebarea mea. Vă mulțumesc foarte mult și îmi pare rău că nu ați citit întrebarea sugerată mai amănunțit prima dată.
0
Răspunde
poncho avatar
drapel my
poncho
Dacă $q$ este prim, răspunsul meu este cel corect. Dacă nu este, dar factorizarea lui este cunoscută, atunci răspunsul meu (care funcționează niște simple post-testuri). Dacă factorizarea este necunoscută, atunci nu cred că există o modalitate care să funcționeze tot timpul (dar puteți obține una care funcționează cu probabilitate $> 0,99 $
1
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.