Trường hữu hạn Giao điểm của đường cong Elliptic

Tôi muốn tìm các điểm đường cong cắt một đường tùy ý, không chỉ là đường tiếp tuyến hoặc đường đi qua các điểm của đường cong. Một ví dụ:

p = 1303
b = 7

đầu vào : điểm tùy ý : (1, 1),(2, 2)
đầu ra : điểm đường cong : (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)

Dòng nên quấn quanh lĩnh vực này

Đây là giải pháp thực sự dạng chính xác của wolfram alpha cho truy vấn;
giải x , (mx+b)^2=x^3+7

Ngay lập tức nhận được vấn đề với $\sqrt[3]2$ mà không có giải pháp mod 1303 $\not â x \in \mathbb{F}_p : x^3 \equiv 2$
p = 1303
squarerrot x^((p+2)/9) , 326 cho p = 1303 cuberoot x^((p+1)/4) , 145 cho p = 1303 Có thể thử thay thế $\sqrt[3]2$ với hai lũy thừa một phần ba? 190 Tôi nghi ngờ nó sẽ hoạt động nên tôi đang hoãn nó lại cho đến cuối tuần Căn bậc ba của 3 là 88

CHỈNH SỬA: Hóa ra nguồn gốc có ý nghĩa hay không cũng chẳng sao, "cuberoot" của 2 (= 1217) lập phương là 1111

Đã thêm một biến khác cho độ dốc vì tôi cho rằng bạn cần một tỷ lệ. Tôi chưa kiểm tra nhiều nhưng nó trả về 629 cho (1,1,0), đây là một giải pháp đúng.

Tuy nhiên, đầu vào lý tưởng phải là hai điểm chứ không phải ba vô hướng.

P = 1303
xác định sqrtp(x):
    trả về pow(x, (P + 1) // 4, P)
xác định cbrtp (x):
    trả về pow(x, (P + 2)/9, P)
def modinv(x):
    trả về pow(x, (P - 2), P)
cbrt2 = cbrtp(2)

giáo phái def(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) không hoạt động
  trả lại x %P

in phái(1,1,0)

Chỉ sử dụng một phép chia thay vì 3 dường như không hiệu quả.

Kiểm tra vị trí đường thẳng cắt đường cong là một khái niệm tương tự như phép cộng điểm

Việc tính toán không nên quá phức tạp chỉ vì đường không được xác định bởi các điểm đường cong?

Bước đầu hình thành phương trình đường thẳng có hệ số góc; $y = mx+c$, và trong trường hợp của bạn $m=1$ và $c=0$. Bây giờ cân bằng điều này với phương trình đường cong $y^2 = x^3 + 7$;

$$x^2 = x^3 + 7$$ và hình thức này

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

Chúng ta cần tìm gốc rễ trong lĩnh vực này $\operatorname{GF}(1303)$. SageMath là bạn của bạn ở đây

R.<x> = GF(1303)[]
px = 1
py = 1
qx = 2
qy = 2
m = R((qy-py)/(qx-px))
in("độ dốc = ",m)
c = py - m*px
in("c = ", c)
g = m*x + c
f = x^3 + 7

h = f - g^2

h.root()

và đầu ra

độ dốc = 1
c = 0
[(629, 1), (356, 1), (319, 1)]

Và đây là hình ảnh của đường cong, đường màu đỏ là đường bạn chọn và các điểm mà đường màu đỏ giao với đường cong là các điểm mà đường màu đỏ và đường màu đen giao nhau.

.