Можно ли вычислить обратное умножение точки на эллиптической кривой?

Название должно сбивать с толку. Представьте, что у нас есть эта кривая:

$у^2 = х^3 + 9х + 17$ над $\mathbb F_{23}$

И мы знаем

[4]Р = (19, 20)

[8]Р = (12, 17)

Если у нас есть только значение $[8]П$, можно ли вычислить $2^{-1}Х$ и $2^{-1}Y$ из $[8]П$ получить $[4]П$?

Поскольку 2 делит порядок группы (который равен 32), есть два прообраза. Их можно найти как корни многочлена умножения на 2 минус цель $х$ (который можно вычислить из полиномы деления).

Пример в шалфее:

мудрец: E = EllipticCurve(GF(23), [9, 17])                                                                                                                                                                                                      
шалфей: E.multiplication_by_m(2)                                                                                                                                                                                                                
((х^4 + 5*х^2 + 2*х - 11)/(4*х^3 - 10*х - 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 * х ^ 4 - 9 * х ^ 3 + 9 * х ^ 2 + 11 * х + 4))

Это две рациональные карты для вычисления $х$ и $у$ точки $[2](х,у)$. Мы хотим $х$ быть равным 19, поэтому:

мудрец: (E.multiplication_by_m(2)[0] - 19)
  .числитель()
  .univariate_polynomial()
  .roots(кратность=ложь)
[20, 10]

Мы можем убедиться, что $[2](20, *) = (19, *)$. Обратите внимание, что знак $у$ должен быть выбран в соответствии с выходным знаком.

мудрец: P = E.lift_x(20)                                                                                                                                                                                                                        
шалфей: 2*п                                                                                                                                                                                                                                     
(19 : 3 : 1)
шалфей: 2*(-P)                                                                                                                                                                                                                                  
(19 : 20 : 1)

Можно повторить дважды, чтобы получить 4-корень, или напрямую использовать карту умножения на 4 (что немного менее эффективно).