ฉันรู้เกี่ยวกับการบีบอัดคีย์ที่คุณควรตรวจสอบว่าค่า y เป็นคู่หรือคี่เพื่อกำหนดว่าด้านใดของเส้นโค้งอยู่
เพื่อให้แม่นยำยิ่งขึ้น คุณต้องตัดสินใจว่า $y$ เป็นคู่หรือคี่เพื่อให้คุณสามารถให้คำแนะนำเพียงพอสำหรับการคลายการบีบอัดเพื่อให้รู้ว่าสิ่งใด $y$ มูลค่าในการสร้างใหม่
สำหรับค่าใด ๆ ของ $x$มี (อย่างมากที่สุด) สองค่าสำหรับ $y$ ที่เป็นไปตามสมการเส้นโค้ง (ซึ่งในกรณีของคุณ $y^2 = x^3 - x + 3$). และปรากฎว่า (สำหรับฟิลด์ลักษณะคี่ ซึ่งก็คือ) หนึ่งในสองโซลูชันสำหรับ $y$ จะเป็นคู่และหนึ่งจะเป็นคี่ - ดังนั้นเพียงแค่ระบุว่า $y$ เป็นคู่หรือคี่เป็นข้อมูลที่เพียงพอสำหรับตัวคลายการบีบอัดที่จะรู้ว่าหมายถึงตัวใด
สำหรับจุดส่วนใหญ่บนเส้นโค้งนั้น จุดบนจะเป็นเลขคู่ และจุดล่างจะเป็นเลขคี่
ไม่ว่าเส้นโค้งจะอยู่ที่ "ครึ่งบน" (ซึ่งฉันคิดว่าหมายถึง $y > p/2$) หรือ "ครึ่งล่าง" ไม่เกี่ยวข้อง เราใช้ lsbit ไม่ว่าจะมีขนาดเท่าใดก็ตาม $y$ เกิดขึ้น
ตอนนี้ เราสามารถกำหนดอัลกอริธึมการบีบอัดทางเลือกที่ขึ้นอยู่กับว่า $y > p/2$แทนที่จะเป็น lsbit ของ $y$. ท้ายที่สุดแล้ว ในฟิลด์สำคัญ หนึ่งในวิธีแก้ปัญหาจะมี $y > p/2$ และอื่น ๆ จะมี $y < p/2$. อย่างไรก็ตาม นั่นไม่ใช่สิ่งที่ผู้คนทำกันจริงๆ (สาเหตุหนึ่งที่เป็นไปได้คือเนื่องจากการทดสอบบิตเดียวง่ายกว่าการเปรียบเทียบค่าเต็ม)