Làm cách nào để chứng minh rằng một điểm trên đường cong elip nhỏ hơn hoặc lớn hơn một nửa bậc của đường cong?

Có thể biết liệu một điểm trên đường cong elip có nhỏ hơn một nửa thứ tự của đường cong hay không?

Nếu tôi có một điểm $ = [a]$ trên một đường cong với bậc nguyên tố q, có cách nào hiệu quả để biết rằng $a < q/2$?

Tôi hiểu rằng bằng chứng phạm vi sẽ hoạt động cho việc này, nhưng có cách nào nhanh hơn không? Cụ thể, tôi đang làm việc với secp256k1, nhưng mọi lời khuyên đều được đánh giá cao.

Nếu có một giải pháp thời gian đa thức thì điều này sẽ cung cấp một giải pháp thời gian đa thức cho bài toán logarit rời rạc trên đường cong elip. Chúng tôi tin tưởng mạnh mẽ rằng đây không phải là trường hợp.

Để thấy sự rút gọn của logarit rời rạc của đường cong elip, giả sử rằng tôi có một điểm $P_0=[x_0]G$ thứ tự ở đâu $G$ Là $q$ và tôi muốn biết $x_0$. tôi tính toán $2^{-1}\pmod q$, tính toán $[2^{-1}]P_0$ và chạy thuật toán kỳ diệu của tôi. Nếu thuật toán nói rằng tồn tại một $a$ với $0<a<q/2$, sau đó tôi biết rằng $x_0$ thậm chí là khôn ngoan khác tôi biết đó là lẻ. Viết $b_0$ cho một chút thấp của $x$, Tôi viết $x_1=(x_0-b_0)/2$ và tính toán $P_1=[2^{-1}](P_0-[b]G)=[x_1]G$. Bây giờ tôi có thể lặp lại quy trình để khôi phục bit thấp $b_1$ của $x_1$ và cứ thế, chấm dứt khi $P_n=G$. Điều này sẽ mất nhiều nhất $\log_2 q$ các bước.