Có thể tính nghịch đảo phép nhân của một điểm trên đường cong elip không?

Tiêu đề phải gây nhầm lẫn. Hãy tưởng tượng chúng ta có đường cong này:

$y^2 = x^3 + 9x + 17$ trên $\mathbb F_{23}$

Và chúng tôi biết

[4]P = (19 , 20)

[8]P = (12 , 17)

Nếu chúng ta chỉ có giá trị của $[8]P$, Có thể tính toán $2^{-1}X$ và $2^{-1}Y$ của $[8]P$ để có được $[4]P$?

Vì 2 phân chia thứ tự nhóm (là 32), nên có hai tiền ảnh. Chúng có thể được tìm thấy dưới dạng nghiệm của đa thức nhân 2 trừ đi mục tiêu $x$ (có thể được tính từ đa thức chia).

Ví dụ trong Sage:

hiền triết: E = EllipticCurve(GF(23), [9, 17])                                                                                                                                                                                                      
nhà hiền triết: 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))

Đây là hai bản đồ hợp lý để tính toán $x$ và $y$ của điểm $[2](x,y)$. Chúng tôi muốn $x$ bằng 19 nên:

hiền nhân: (E.multiplication_by_m(2)[0] - 19)
  .tử số()
  .univariate_polynomial()
  .roots(multiplities=False)
[20, 10]

Chúng tôi có thể xác minh rằng $[2](20, *) = (19, *)$. Lưu ý rằng dấu hiệu của $y$ phải được chọn để khớp với dấu hiệu đầu ra.

hiền triết: P = E.lift_x(20)                                                                                                                                                                                                                        
hiền triết: 2*P                                                                                                                                                                                                                                     
(19 : 3 : 1)
hiền triết: 2*(-P)                                                                                                                                                                                                                                  
(19 : 20 : 1)

Có thể lặp lại hai lần để có 4 căn hoặc sử dụng trực tiếp bản đồ nhân 4 (kém hiệu quả hơn một chút).