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

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.

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.