(ฉันเดาว่าไม่ แต่ทำไมเป็นกรณีนี้ มีวิธีใดบ้างที่จะทำให้เป็นไปได้)
จากสามเหลี่ยมด้านเท่าที่กำหนด T1 (โดยมีจุดยอด 3 จุด A,B,C อยู่ในสนามที่จำกัด $\mathbb F_N^D $) สามเหลี่ยมด้านเท่า T2 อีกอันสามารถสร้างได้โดยการสะท้อนหนึ่งใน 3 จุดยอดที่ขอบระหว่างจุดยอดอีกสองจุด สิ่งนี้จะถูกทำซ้ำหลายครั้ง
กำหนดเพียงสองสามเหลี่ยมสุ่ม T1 และ T2 (และ $\mathbb F_N^D $) ฝ่ายตรงข้ามสามารถคำนวณทางที่สั้นที่สุดจาก T1 ถึง T2 ได้หรือไม่?
(สมมติว่ามีทางและโมดูโล $N$ และขนาด $D$ ถูกเลือกสูงพอที่การทดสอบสามเหลี่ยมทั้งหมดจะใช้เวลานาน)
หรือเขาสามารถทำได้ (มาก) เร็วกว่าการใช้ทีละขั้นตอน?
(เช่นตัวอย่างที่ EC a generator $g$ ไม่จำเป็นต้องสมัคร $m$ ครั้งถ้าเราต้องการคำนวณ $g^m$. ฉันกำลังมองหาเทคนิคมากกว่าหนึ่งมิติซึ่งไม่สามารถลดขนาดให้เป็นปัญหามิติเดียวได้ และจำเป็นต้องคำนวณทีละขั้นตอน 'ความยาว' ของ 'วิธีที่สั้นที่สุด' จะเป็นจำนวนของการคำนวณ (สามเหลี่ยม) ที่จำเป็น)
ในการสะท้อนจุด A ที่ขอบ BC เรากำลังมองหาจุด $S$ และตัวแปร $r$ กับ
$$S = B + r (C-B)$$
อนุญาต $v$ ทิศทางของขอบ BC:
$$v = \vec{v} = C-B$$
นี้ $S$ จะช่วยให้เราสามารถคำนวณทิศทางจาก $A$ ถึง $BC$ และด้วยการคำนวณจุดที่มิเรอร์นี้ $A_M$
$$A_M = A + 2(S-A)$$
เพื่อทำสิ่งนี้ $S-A$ ต้องตั้งฉากกับ $v$. ดังนั้นผลคูณสเกลาร์ต้องเป็น 0:
$$(S-A)' v = 0$$
$$(B+rv-A)' v = 0$$
$$(BA)' v = -rv'v$$
$$r = \frac{(B-A)'v}{-(v'v)}$$
(เหมือนกับในปริภูมิแบบยุคลิด ยกเว้นเขตจำกัด $r$ ต้องคำนวณด้วยอินเวอร์ส $(-(v'v))^{-1}$ เกิน $N$)
แก้ไข: fgrieu ชี้ให้เห็นว่ายังมีวิธีที่ง่ายกว่ามากในการคำนวณการสะท้อนของสามเหลี่ยมด้านเท่า:
$$A_M = A' = B+C-A$$
(จบการแก้ไข)
ฉันทำการทดสอบสำหรับ 2 มิติและจำนวนเฉพาะ $N$.
เขตข้อมูล จำกัด $\mathbb F_N^2 $ สามารถสร้างสามเหลี่ยมด้านเท่าได้ก็ต่อเมื่อ $N$ มีรากสำหรับ $3$.
สามารถสร้างรูปสามเหลี่ยมด้านเท่าที่มีความยาวขอบที่กำหนดได้ $2 น^2$ รูปสามเหลี่ยมอื่น ๆ (แต่ละอันมีความยาวขอบเท่ากัน)
ความยาวขอบแต่ละชุดมีสองชุดดังกล่าว เบ็ดเสร็จ $2(N-1) (2N^2)$ ที่ไม่ปะติดปะต่อกัน
(ฉันเพิ่งคำนวณความยาวขอบกำลังสองระหว่างสองจุดเหมือนในปริภูมิยุคลิด)
ในปริภูมิแบบยุคลิดสะท้อนสามเหลี่ยมรอบจุด ($C$) จะมีลักษณะดังนี้:
กระจกบานแรก $A$ ที่ $CB$. แล้วส่องกระจก $B$ ที่ $CA_M$ และอื่น ๆ หากเป็นรูปสามเหลี่ยมด้านเท่าก็จะจับคู่อีกครั้งหลังจากทำเช่นนี้ 6 ครั้ง
ในสนามที่จำกัด $\mathbb F_{11}^2 $ มันสามารถมีลักษณะดังนี้:
ทำได้ 6 ครั้ง (ประมาณ 1 คะแนน)
ทำเพียงทิศทางเดียวก็จะเข้ากันในภายหลัง $2N$
อัลกอริทึมการเข้ารหัสที่คล้ายกับสิ่งนี้มีอยู่จริงหรือไม่?
เหตุใดจึงไม่ปลอดภัย หรือมันคืออะไร? มิติเพิ่มเติมจะช่วย?
ความคิดใดที่จะทำให้ปลอดภัยยิ่งขึ้น?