กำหนดสองจุดบนเส้นโค้ง $P=(x_1,y_1), Q=(x_2,y_2)$ เราสามารถกำหนดพารามิเตอร์ของแบบฟอร์ม Weierstrass แบบสั้นได้ $y^2 = x^2 + ขวาน +b$. ใส่พิกัดของจุดลงในสมการเส้นโค้งเพื่อให้ได้สองสมการตามที่คุณทำ
\begin{จัด}
y_1^2 &= x_1^3 + ax_1 + b &\pmod{n} \
y_2^2 &= x_2^3 + ax_2 + b &\pmod{n}\ \hline & & \text{subtract}\
y_1^2 - y_2^2 &= x_1^3 - x_2^3 + a (x_1 - x_2) &\pmod{n}\
(y_1^2 - y_2^2) -(x_1^3 - x_2^3)&= ก (x_1 - x_2) &\pmod{n}\
[(y_1^2 - y_2^2) -(x_1^3 - x_2^3)] \cdot (x_1 - x_2)^{-1}&= a &\pmod{n}\
\end{แนว}
ที่จะสามารถหาได้ $a$ ปัญหาเดียวคือการมีอยู่ของ ผกผันการคูณแบบโมดูลาร์ ของ $(x_1 - x_2)$ ไปที่ $\bmod n$.
- ถ้า $\gcd((x_1 - x_2),n) = 1$ จากนั้นจึงมีการผกผันการคูณแบบโมดูลาร์และสามารถหาได้ง่ายด้วย อัลกอริทึมแบบยุคลิดแบบขยาย (Ext-GCD)
- ถ้า $\gcd((x_1 - x_2),n) \neq 1$ จากนั้นจะไม่มีการผกผัน (ดูจะเกิดอะไรขึ้นถ้าด้านล่าง)
- โปรดทราบว่าในกรณีนี้ $x_1 - x_2 = 0$ ถ้าอย่างนั้นเราก็มี $\gcd(0,n) = n.$ กล่าวอีกนัยหนึ่งไม่มีการผกผัน
ครั้งหนึ่ง $a$ พบสำเร็จพบ $ข$ ง่ายกว่า แทนค่าที่ทราบลงในสมการแล้วแก้เฉพาะค่าที่ไม่ทราบ $ข$.
SageMath สำหรับโมดูลาร์ผกผัน;
Zn = จำนวนเต็ม(12)
ก = สังกะสี(5)
ข = ก^-1
ก
ถ้าตั้งค่า $a = 4$ จากนั้นคุณจะได้รับข้อผิดพลาด: ZeroDivisionError: ไม่มีส่วนผกผันของ Mod (4, 12)
.
เกิดอะไรขึ้นถ้า ไม่มีการผกผันของ $(x_1 - x_2)$ ถึง $\bmod{n}$. เราสามารถหาวิธีแก้ปัญหาด้านล่างได้หรือไม่?
$$(y_1^2 - y_2^2) -(x_1^3 - x_2^3)= a (x_1 - x_2) \pmod{n} \label{a}\tag{1}$$
ใช่ เรายังคงสามารถหาวิธีแก้ไขได้ $\ref{a}$ แต่พวกเขาจะไม่ซ้ำกัน
บทแทรก: ถ้า $d$ เป็นตัวหารร่วมมากของ a และ m แล้วก็ความสอดคล้องเชิงเส้น $ax \equiv b \pmod m$ มีวิธีแก้ไขก็ต่อเมื่อ $d$ แบ่ง $ข$. ถ้า $d$ แบ่ง $ข$แล้วมีอยู่ว่า $d$ โซลูชั่น
เพื่อค้นหาพวกเขาจาก $a/d \cdot x \equiv b/d \pmod{m/d}$. เป็นที่ชัดเจนว่า $\gcd(a/d,m/d)=1$. จากนั้นเราสามารถกลับด้านได้ $a/d$ และแก้ปัญหาสำหรับ $x$. แล้ว $\{x, x+\dfrac{m}{d},x+\dfrac{2m}{d}, \ldots, x+\dfrac{(d-1)m}{d} \}$ คือ $d$ คำตอบสำหรับสมการ $\ref{a}$.
สำหรับแต่ละโซลูชั่นก็คาดว่าจะมีความแตกต่างกัน $ข$ดังนั้นสำหรับการกำหนดข้อมูลเพิ่มเติมจะต้องไม่ซ้ำกัน