Puncte:0

Compresie cheie curbă eliptică

drapel in

Am o curbă eliptică y2 = x3 -x + 3 peste un câmp finit de 127. Încerc să comprim un punct folosind standardul X9.62. Știu că pentru compresia tastei ar trebui să verificați dacă valoarea y este pară sau impară pentru a determina pe ce parte a curbei se află.Pentru majoritatea punctelor de pe curbă, punctul superior este par, iar punctul inferior este impar. Cu toate acestea, pentru perechea (16, 20) și (16, 107) și alte câteva, punctul inferior este par, iar punctul superior este impar.

Înseamnă asta că nu puteți utiliza compresia tastelor pe această curbă specifică sau există o altă modalitate de a face acest lucru?

Puncte:2
drapel my

Știu că pentru compresia tastei ar trebui să verificați dacă valoarea y este pară sau impară pentru a determina pe ce parte a curbei se află.

Pentru a fi mai precis, determinați dacă $y$ este par sau impar, astfel încât să puteți da un indiciu suficient pentru ca decompresia să știți care $y$ valoare de reconstruit.

Pentru orice valoare de $x$, există (cel mult) două valori pentru $y$ care satisface ecuația curbei (care este, în cazul dvs., $y^2 = x^3 - x + 3$). Și, se dovedește că (pentru câmpurile caracteristice ciudate, care este aceasta) una dintre cele două soluții pentru $y$ va fi par, iar unul va fi impar - prin urmare, afirmând doar dacă $y$ este par sau impar este suficientă informație pentru ca decompresorul să știe care este vorba.

Pentru majoritatea punctelor de pe curbă, punctul superior este par, iar punctul inferior este impar

Dacă curba este în „jumătatea superioară” (ceea ce, presupun, înseamnă $y > p/2$) sau „jumătatea inferioară” este irelevantă; folosim lsbit, indiferent de magnitudine $y$ se întâmplă să fie.

Acum, s-ar putea defini un algoritm de compresie alternativ care se bazează pe dacă $y > p/2$, mai degrabă decât lsbit de $y$. La urma urmei, într-un domeniu prim, una dintre soluții va avea $y > p/2$ iar celălalt va avea $y < p/2$. Cu toate acestea, asta nu este ceea ce fac oamenii de fapt (un motiv posibil este că este mai ușor să testați un singur bit decât să faceți o comparație pe valoarea completă)

fgrieu avatar
drapel ng
Adăugare: pentru a determina dacă $x\pmod p$ este par sau impar, găsim întregul $a$ în ​​intervalul $[0,p)$ cu $a\equiv x\pmod p$, adică $a$ calculat ca $ a\obține x\bmod p$ și testează dacă $a$ este par sau impar. De exemplu, $129\pmod{127}$ este par, deoarece $2\equiv129\pmod{127}$ și $0\le2

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.