Finite field Elliptic Curve line intersection

Question

I want to find the curve points that intersects an arbirtary line, not just tangent line or a line through curve points. An example:

p = 1303
b = 7

input : arbitrary points : (1, 1),(2, 2)
output : curve points : (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)

The line should wrap around the field

Here is the wolfram alpha exact form real solution for query ;
solve x , (mx+b)^2=x^3+7

Immediately getting issues with $\sqrt[3]2$ which has no solutions mod 1303 $\not ∃ x \in \mathbb{F}_p : x^3 \equiv 2$
p = 1303
squarerrot x^((p+2)/9) , 326 for p = 1303 cuberoot x^((p+1)/4) , 145 for p = 1303 Could try substituting $\sqrt[3]2$ with two to the power of one third? 190 I doubt it will work so I'm putting it putting it off until the weekend Cuberoot of 3 is 88

EDIT: Turns out it doesn't matter if the roots make sense , the "cuberoot" of 2 ( = 1217) cubed is 1111

Added another variable for the slope because I figured you need a ratio. I have not tested it much but it returns 629 for (1,1,0) which is a correct solution.

The input should ideally be two points not three scalars though.

P = 1303
def sqrtp(x):
    return pow(x, (P + 1) // 4, P)
def cbrtp(x):
    return pow(x, (P + 2) / 9, P)
def modinv(x):
    return pow(x, (P - 2), P)
cbrt2 = cbrtp(2)

def sect(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) doesn't work
  return x % P

print sect(1,1,0)

Using just one division instead of 3 doesn't seem to work.

Checking where a line intersects the curve is a similar concept to point addition

The calculation shouldn't be overly more complicated just because the line is not defined by curve points?

Answer 1

The first step is forming the line equation with the slope; $y = mx+c$, and in your case $m=1$ and $c=0$. Now equate this with the curve equation $y^2 = x^3 + 7$;

$$x^2 = x^3 + 7$$ and this forms

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

We need to find the roots in the field $\operatorname{GF}(1303)$. SageMath is your friend here

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

h = f - g^2

h.roots()

and outputs

slope =  1
c =  0
[(629, 1), (356, 1), (319, 1)]

And here the images of the curve, red line the line you choose, and the points that the red line intersects with the curve are the points that the red line and black lines intersect.

.