Пересечение линии эллиптической кривой конечного поля

Я хочу найти точки кривой, которые пересекают произвольную линию, не просто касательная или линия, проходящая через точки кривой. Пример:

р = 1303
б = 7

ввод: произвольные точки: (1, 1), (2, 2)
вывод: точки кривой: (319 319), (356 356), (629 629)

(319,319) 319^3+7 ≡ 319^2 ≡ 127 (mod p)
(356 356) 356 ^ 3 + 7 - 356 ^ 2 - 345 (mod p) 
(629 629) 629 ^ 3 + 7 - 629 ^ 2 - 832 (mod p)

Линия должна обтекать поле

Вот точное решение альфа-формы wolfram для запроса;
решить x , (mx+b)^2=x^3+7

Сразу возникают проблемы с $\sqrt[3]2$ у которого нет решений мод 1303 $\not â x \in \mathbb{F}_p : x^3 \equiv 2$
р = 1303
Squarerrot x^((p+2)/9) , 326 для p = 1303 кубический корень x^((p+1)/4) , 145 для p = 1303 Можно попробовать заменить $\sqrt[3]2$ с двумя в степени одной трети? 190 Сомневаюсь, что получится, поэтому откладываю до выходных. Кубический корень из 3 равен 88

РЕДАКТИРОВАТЬ: Оказывается, неважно, есть ли смысл в корнях, «кубический корень» из 2 (= 1217) в кубе равен 1111

Добавил еще одну переменную для наклона, потому что я решил, что вам нужен коэффициент. Я не тестировал его много, но он возвращает 629 для (1,1,0), что является правильным решением.

Однако входные данные в идеале должны быть двумя точками, а не тремя скалярами.

Р = 1303
защита sqrtp(x):
    вернуть pow(x, (P + 1) // 4, P)
защита cbrtp(x):
    вернуть pow(x, (P + 2)/9, P)
дефмодинв(х):
    вернуть pow(x, (P - 2), P)
cbrt2 = cbrtp(2)

Защитная секция (m, n, b):
  L = 27*(b**2 - 7)*n**2 + 18*b*m**3*n + 2*m**6
  U = (-6*b*m*n - m**4) % P
  T = cbrtp (sqrtp (L ** 2 + 4 * U ** 3) + L) % P
  x = T * modinv((3 * cbrt2 * n)) - ( cbrt2 * U) * modinv(3*n*T) + m**2 * modinv(3*n)
  # x = (2*m**2*T + cbrt2*(cbrt2*T**2 - 2*U)) * modinv(6*n*T) не работает
  возврат х % Р

раздел печати (1,1,0)

Использование только одного деления вместо 3, похоже, не работает.

Проверка того, где линия пересекает кривую, аналогична концепции добавления точек.

Расчет не должен быть слишком сложным только потому, что линия не определяется точками кривой?

Первым шагом является формирование уравнения линии с наклоном; $у = мх+с$, а в вашем случае $м=1$ и $с=0$. Теперь приравняйте это к уравнению кривой $у^2 = х^3 + 7$;

$$х^2 = х^3 + 7$$ и это формы

$$f(x) = x^3 -x^2 + 7 $$

Нам нужно найти корни в поле $\operatorname{GF}(1303)$. SageMath твой друг здесь

R.<x> = GF(1303)[]
пкс = 1
ру = 1
дх = 2
qу = 2
m = R ((qy-py)/(qx-px))
печать ("уклон = ", м)
с = ру - м*px
печать("с = ", с)
г = м * х + с
е = х ^ 3 + 7

ч = е - г ^ 2

h.roots ()

и результаты

наклон = 1
с = 0
[(629, 1), (356, 1), (319, 1)]

А здесь изображения кривой, красная линия — выбранная вами линия, а точки, в которых красная линия пересекает кривую, — это точки, в которых пересекаются красная линия и черные линии.

.