Tìm Tham Số Đường Cong Elliptic, a và b, Cho Hai Điểm Trên Đường Cong

Cho hai điểm trên đường cong $P=(x_1,y_1), Q=(x_2,y_2)$ chúng ta có thể xác định các tham số của dạng Weierstrass ngắn $y^2 = x^2 + ax +b$. Chèn tọa độ các điểm vào phương trình đường cong để được hai phương trình như bạn đã làm;

\begin{align} y_1^2 &= x_1^3 + ax_1 + b &\pmod{n} \ y_2^2 &= x_2^3 + ax_2 + b &\pmod{n}\ \hline & & \text{trừ}\ 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)&= a (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{align}

Để có thể tìm thấy $a$ vấn đề duy nhất là sự tồn tại của nghịch đảo nhân mô-đun của $(x_1 - x_2)$ đến $\bmod n$.

• Nếu $\gcd((x_1 - x_2),n) = 1$ thì nghịch đảo nhân mô-đun tồn tại và có thể dễ dàng tìm thấy với Thuật toán Euclide mở rộng (Ext-GCD)
• Nếu $\gcd((x_1 - x_2),n) \neq 1$ thì không có nghịch đảo (xem Điều gì xảy ra nếu bên dưới).
• Lưu ý rằng, trong trường hợp $x_1 - x_2 = 0$ sau đó chúng tôi có $\gcd(0,n) = n.$ Nói cách khác, không có nghịch đảo.

Một lần $a$ được tìm thấy thành công, việc tìm kiếm $b$ là dễ dàng hơn. Thay cái đã biết vào phương trình rồi giải cho cái chưa biết duy nhất $b$.

SageMath cho nghịch đảo mô-đun;

Zn = Số nguyên(12)
a = Zn(5)
b = a^-1
một

nếu đặt $a = 4$ sau đó bạn sẽ nhận được lỗi: ZeroDivisionError: nghịch đảo của Mod(4, 12) không tồn tại.

Chuyện gì xảy ra nếu không có nghịch đảo của $(x_1 - x_2)$ đến $\bmod{n}$. Chúng ta có thể tìm thấy giải pháp dưới đây?

$$(y_1^2 - y_2^2) -(x_1^3 - x_2^3)= a (x_1 - x_2) \pmod{n} \label{a}\tag{1}$$

Có, chúng ta vẫn có thể tìm giải pháp cho $\ref{a}$ nhưng chúng sẽ không phải là duy nhất.

bổ đề: Nếu $d$ là ước chung lớn nhất của a và m thì đồng dạng tuyến tính $ax \equiv b \pmod m$ có nghiệm khi và chỉ khi $d$ phân chia $b$. Nếu $d$ phân chia $b$, thì có chính xác $d$ các giải pháp

Để tìm thấy chúng, từ $a/d \cdot x \equiv b/d \pmod{m/d}$. Rõ ràng là $\gcd(a/d,m/d)=1$. Sau đó chúng ta có thể đảo ngược $a/d$ và giải quyết cho $x$. sau đó $\{x, x+\dfrac{m}{d},x+\dfrac{2m}{d}, \ldots, x+\dfrac{(d-1)m}{d} \}$ là $d$ giải phương trình $\ref{a}$.

Đối với mỗi giải pháp, nó dự kiến ​​​​sẽ có một khác nhau $b$, do đó để xác định duy nhất thông tin bổ sung sẽ là cần thiết.