จะพิสูจน์ได้อย่างไรว่าจุดโค้งวงรีนั้นเล็กกว่าหรือมากกว่าครึ่งหนึ่งของลำดับเส้นโค้ง?

เป็นไปได้ไหมที่จะบอกได้ว่าจุดบนเส้นโค้งวงรีมีค่าน้อยกว่าครึ่งหนึ่งของลำดับเส้นโค้ง?

ถ้าฉันมีประเด็น $ = [a]$ บนเส้นโค้งที่มีลำดับเฉพาะ q มีวิธีที่มีประสิทธิภาพในการรู้หรือไม่ $a < คิว/2$?

ฉันเข้าใจว่าการพิสูจน์ช่วงจะได้ผลสำหรับสิ่งนี้ แต่มีวิธีที่เร็วกว่านี้ไหม โดยเฉพาะอย่างยิ่ง ฉันกำลังทำงานกับ secp256k1 แต่คำแนะนำใด ๆ ก็ได้รับการชื่นชมอย่างมาก

หากมีวิธีแก้ปัญหาเวลาพหุนาม สิ่งนี้จะให้วิธีแก้ปัญหาเวลาพหุนามแก่ปัญหาลอการิทึมไม่ต่อเนื่องของเส้นโค้งวงรี เราเชื่ออย่างยิ่งว่าจะไม่เป็นเช่นนั้น

หากต้องการดูการลดลงของลอการิทึมไม่ต่อเนื่องของเส้นโค้งวงรี สมมติว่าฉันมีจุด $P_0=[x_0]G$ โดยที่คำสั่งของ $G$ เป็น $คิว$ และฉันต้องการทราบ $x_0$. ฉันคำนวณ $2^{-1}\pmod q$, คำนวณ $[2^{-1}]P_0$ และเรียกใช้อัลกอริทึมเวทมนตร์ของฉัน หากอัลกอริทึมบอกว่ามีอยู่ $a$ กับ $0<a<q/2$แล้วฉันก็รู้ว่า $x_0$ เป็นเรื่องฉลาดที่ฉันรู้ว่ามันแปลก การเขียน $b_0$ สำหรับบิตต่ำของ $x$, ฉันเขียน $x_1=(x_0-b_0)/2$ และคำนวณ $P_1=[2^{-1}](P_0-[b]G)=[x_1]G$. ตอนนี้ฉันสามารถทำซ้ำขั้นตอนเพื่อกู้คืนบิตต่ำ $b_1$ ของ $x_1$ และอื่น ๆ สิ้นสุดเมื่อ $P_n=G$. ซึ่งจะใช้เวลามากที่สุด $\log_2 คิว$ ขั้นตอน