Làm cách nào để xác định xem một điểm có lớn hơn n/2 hay không?

Làm cách nào chúng tôi có thể xác định xem khóa riêng được liên kết với một điểm, trên EC, nhỏ hơn hoặc lớn hơn 1/2 $n$, ở đâu $n$ là thứ tự?

Làm cách nào chúng tôi có thể xác định xem khóa riêng được liên kết với một điểm, trên EC, nhỏ hơn hay lớn hơn $1/2 n$, ở đâu $n$ là thứ tự?

Cách rõ ràng là tính toán nhật ký rời rạc của khóa riêng (có thể đạt được trong $O( \sqrt{n} )$ các bước và so sánh.

Ngoài ra, có thể chỉ ra rằng không có cách nào rẻ hơn đáng kể - với một Oracle, cho một điểm, tính toán nơi nhật ký rời rạc lớn hơn hoặc nhỏ hơn $1/2 n$, chúng ta có thể tính toán nhật ký rời rạc với $\log_2{n}$ truy vấn (cộng với một số hoạt động tương đối rẻ); do đó Oracle này không thể rẻ hơn $1 / \log_2{n}$ rẻ gấp nhiều lần so với cách tiếp cận ngây thơ ở trên.