1
$\begingroup$

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

enter image description here

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.

enter image description here

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?

$\endgroup$
6
  • $\begingroup$ Welcome to Cryptography.SE. Your first center is not clear and the curve is not defined, too. Are you asking a line passing through 3 points? this is easy, take $P$ and $Q$ calculate $R = P+Q$ then $P,Q,-R$ on the same line. An image from this answer (or here )might help you to visualize. $\endgroup$
    – kelalaka
    Jun 15 '21 at 20:09
  • $\begingroup$ I only find algorithms that assume inputs are points satifying the curve equation $\endgroup$ Jun 15 '21 at 20:34
  • $\begingroup$ Could you write your problem more explicitly? What do mean points that intersect an arbitrary line? A point can lie on a line or not. $\endgroup$
    – kelalaka
    Jun 15 '21 at 20:40
  • $\begingroup$ The input is two points, on or off the elliptic curve that forms a line. The output should be points that are both on the elliptic curve, and on the line formed by the two arbitrary points. $\endgroup$ Jun 15 '21 at 20:48
  • $\begingroup$ In this case, form the line equation and intersect with the curve. $y = mx +c$ and take square and equate to the right part of the curve equation and solve! $\endgroup$
    – kelalaka
    Jun 15 '21 at 20:54
2
$\begingroup$

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.

enter image description here.

$\endgroup$
1
  • $\begingroup$ I hope this was not an HW! $\endgroup$
    – kelalaka
    Jun 16 '21 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.