Puncte:0

Cum se demonstrează că un punct de curbă eliptică este mai mic sau mai mare decât jumătate din ordinul curbei?

drapel cn

Este posibil să spunem dacă un punct de pe o curbă eliptică este mai mic de jumătate din ordinul curbei?

Dacă am un punct $ = [a]$ pe o curbă cu ordinul prim q, există o modalitate eficientă de a ști asta $a < q/2$?

Înțeleg că probele de interval ar funcționa pentru asta, dar există o modalitate mai rapidă? Mai exact, lucrez cu secp256k1, dar orice sfat este foarte apreciat.

kelalaka avatar
drapel in
Cauți acest lucru [Demonstrarea faptului că două puncte de pe curba eliptică se află în rază](https://crypto.stackexchange.com/q/66058/18298) În special [Bullet Proofs](https://eprint.iacr.org/ 2017/1066.pdf)
Puncte:2
drapel ru

Dacă ar exista o soluție de timp polinomială, aceasta ar oferi o soluție de timp polinomială pentru problema logaritmului discret al curbei eliptice. Credem cu tărie că nu este cazul.

Pentru a vedea reducerea la logaritmul discret al curbei eliptice, să presupunem că am un punct $P_0=[x_0]G$ unde ordinea de $G$ este $q$ si vreau sa stiu $x_0$. calculez $2^{-1}\pmod q$, calculati $[2^{-1}]P_0$ și rulează algoritmul meu magic. Dacă algoritmul spune că există un $a$ cu $0<a<q/2$, atunci știu asta $x_0$ chiar și altfel, știu că este ciudat. Scris $b_0$ pentru putinul mic de $x$, Eu scriu $x_1=(x_0-b_0)/2$ și calculează $P_1=[2^{-1}](P_0-[b]G)=[x_1]G$. Acum pot repeta procesul pentru a recupera bitul scăzut $b_1$ de $x_1$ și așa mai departe, terminând când $P_n=G$. Acest lucru va dura cel mult $\log_2 q$ trepte.

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.