Câmp finit Intersecția liniilor curbei eliptice

Vreau să găsesc punctele curbei care intersectează o linie arbitrară, nu doar o linie tangentă sau o linie prin puncte de curbă. Un exemplu:

p = 1303
b = 7

intrare: puncte arbitrare: (1, 1),(2, 2)
ieșire: puncte curbei: (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)

Linia ar trebui să se înfășoare în jurul câmpului

Iată soluția reală a formei exacte wolfram alpha pentru interogare;
rezolvați x , (mx+b)^2=x^3+7

Întâmpinați imediat probleme cu $\sqrt[3]2$ care nu are soluții mod 1303 $\nu â x \in \mathbb{F}_p : x^3 \equiv 2$
p = 1303
patrate x^((p+2)/9) , 326 pentru p = 1303 cuberoot x^((p+1)/4) , 145 pentru p = 1303 Ar putea încerca înlocuirea $\sqrt[3]2$ cu doi la puterea unei treimi? 190 Mă îndoiesc că va funcționa, așa că îl amân până în weekend Cuberoot de 3 este 88

EDITAȚI | ×: Se pare că nu contează dacă rădăcinile au sens, „cuberoot” din 2 ( = 1217) cub este 1111

Am adăugat o altă variabilă pentru panta pentru că m-am gândit că aveți nevoie de un raport. Nu l-am testat prea mult, dar returnează 629 pentru (1,1,0), care este o soluție corectă.

În mod ideal, intrarea ar trebui să fie de două puncte, nu de trei scalari.

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 secta(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) nu funcționează
  întoarcere x % P

sectează tipărire(1,1,0)

Folosirea unei singure diviziuni în loc de 3 nu pare să funcționeze.

Verificarea locului în care o linie intersectează curba este un concept similar cu adăugarea de puncte

Calculul nu ar trebui să fie prea complicat doar pentru că linia nu este definită de punctele curbei?

Primul pas este formarea ecuației drepte cu panta; $y = mx+c$, iar în cazul dvs $m=1$ și $c=0$. Acum echivalează acest lucru cu ecuația curbei $y^2 = x^3 + 7$;

$$x^2 = x^3 + 7$$ iar aceasta se formeaza

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

Trebuie să găsim rădăcinile în câmp $\operatorname{GF}(1303)$. SageMath este prietenul tău aici

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

h = f - g^2

h.roots()

și ieșiri

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

Și aici imaginile curbei, linia roșie linia pe care o alegeți și punctele pe care linia roșie le intersectează cu curba sunt punctele pe care linia roșie și liniile negre le intersectează.

.