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

ชื่อเรื่องต้องทำให้สับสน ลองจินตนาการว่าเรามีเส้นโค้งนี้:

$y^2 = x^3 + 9x + 17$ เกิน $\mathbb F_{23}$

และเรารู้

[4]P = (19 , 20)

[8]P = (12 , 17)

ถ้าเรามีค่าแค่ $[8]฿เป็นไปได้ไหมที่จะคำนวณ $2^{-1}X$ และ $2^{-1}ใช่$ ของ $[8]฿ ที่จะได้รับ $[4]P$?

เนื่องจาก 2 แบ่งลำดับกลุ่ม (ซึ่งก็คือ 32) จึงมีภาพพรีอิมเมจสองภาพ สามารถหาได้จากรากของพหุนามคูณด้วย 2 ลบเป้าหมาย $x$ (ซึ่งสามารถคำนวณได้จาก พหุนามหาร).

ตัวอย่างใน Sage:

ปราชญ์: E = EllipticCurve(GF(23), [9, 17])                                                                                                                                                                                                      
ปราชญ์: E.multiplication_by_m(2)                                                                                                                                                                                                                
((x^4 + 5*x^2 + 2*x - 11)/(4*x^3 - 10*x - 1),
 (8*x^6*y - 8*x^4*y + 6*x^3*y + 3*x^2*y + 3*x*y + 6*y)/(-5*x^ 6 + 2*x^4 - 9*x^3 + 9*x^2 + 11*x + 4))

นี่คือแผนที่เหตุผลสองแผนที่สำหรับการคำนวณ $x$ และ $y$ ของจุด $[2](x,y)$. พวกเราต้องการ $x$ เท่ากับ 19 ดังนั้น:

ปราชญ์: (E.multiplication_by_m(2)[0] - 19)
  .เศษ()
  .univariate_polynomial()
  .root(การคูณ=เท็จ)
[20, 10]

เราสามารถตรวจสอบได้ว่า $[2](20, *) = (19, *)$. โปรดทราบว่าเครื่องหมายของ $y$ ต้องเลือกให้ตรงกับสัญญาณขาออก

ปราชญ์: P = E.lift_x(20)                                                                                                                                                                                                                        
ปราชญ์: 2 * P                                                                                                                                                                                                                                     
(19 : 3 : 1)
ปราชญ์: 2*(-P)                                                                                                                                                                                                                                  
(19 : 20 : 1)

สามารถทำซ้ำสองครั้งเพื่อให้ได้ 4 ราก หรือใช้แผนที่คูณด้วย 4 โดยตรง (ซึ่งมีประสิทธิภาพน้อยกว่าเล็กน้อย)