การตัดกันของเส้นโค้งวงรีแบบจำกัดสนาม

ฉันต้องการหาจุดเส้นโค้งที่ตัดกับเส้นโดยพลการ ไม่ใช่แค่เส้นสัมผัสหรือเส้นผ่านจุดโค้ง ตัวอย่าง:

พี = 1303
ข = 7

อินพุต : จุดโดยพลการ : (1, 1),(2, 2)
เอาต์พุต : จุดโค้ง : (319,319),(356,356),(629,629)

(319,319) 319^3+7 â¡ 319^2 â¡ 127 (สมัย p)
(356,356) 356^3+7 â¡ 356^2 â¡ 345 (สมัย p) 
(629,629) 629^3+7 â¡ 629^2 â¡ 832 (mod p)

เส้นควรพันรอบสนาม

นี่คือวุลแฟรมอัลฟ่าโซลูชันจริงสำหรับแบบสอบถาม
แก้ค่า x , (mx+b)^2=x^3+7

ทันทีที่มีปัญหากับ $\sqrt[3]2$ ซึ่งไม่มีวิธีแก้ปัญหา mod 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
def sqrtp(x):
    กลับธาร(x, (P + 1) // 4, P)
def cbrtp(x):
    กลับธาร(x, (P + 2) / 9, P)
def modinv(x):
    กลับธาร(x, (P - 2), P)
cbrt2 = cbrtp(2)

ส่วน 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) ไม่ทำงาน
  ผลตอบแทน x % P

พิมพ์ภาค (1,1,0)

การใช้เพียงหนึ่งส่วนแทนที่จะเป็น 3 ดูเหมือนจะไม่ทำงาน

การตรวจสอบว่าเส้นใดตัดกับเส้นโค้งเป็นแนวคิดที่คล้ายคลึงกับการบวกจุด

การคำนวณไม่ควรซับซ้อนมากเกินไปเพียงเพราะเส้นไม่ได้กำหนดโดยจุดโค้ง?

ขั้นตอนแรกคือการสร้างสมการเส้นตรงด้วยความชัน $y = mx+c$และในกรณีของคุณ $m=1$ และ $ค=0$. ตอนนี้ให้สมการนี้กับสมการเส้นโค้ง $y^2 = x^3 + 7$;

$$x^2 = x^3 + 7$$ และแบบฟอร์มนี้

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

เราต้องค้นหารากในฟิลด์ $\operatorname{GF}(1303)$. SageMath คือเพื่อนของคุณที่นี่

R.<x> = GF(1303)[]
พิกเซล = 1
พาย = 1
คิวเอ็กซ์ = 2
คิว = 2
ม = R((qy-py)/(qx-px))
พิมพ์ ("ความชัน = ",m)
c = py - m*px
พิมพ์ ("c = ", ค)
ก = ม*x + ค
f = x^3 + 7

ชั่วโมง = ฉ - g^2

h.root()

และเอาต์พุต

ความชัน = 1
ค = 0
[(629, 1), (356, 1), (319, 1)]

และนี่คือภาพของเส้นโค้ง เส้นสีแดงของเส้นที่คุณเลือก และจุดที่เส้นสีแดงตัดกับเส้นโค้งคือจุดที่เส้นสีแดงและเส้นสีดำตัดกัน

.