solution

Cho đường cong elliptic dạng Weierstrass trên trường hữu hạn $\mathbb{Z}_p$ ($p$ là số nguyên tố lẻ):

$E: y^2 \equiv x^3 + ax + b \pmod p, \qquad 4a^3 + 27b^2 \not\equiv 0 \pmod p.$

Tập các điểm $(x, y)$ thỏa mãn phương trình trên, cùng với một điểm đặc biệt gọi là điểm vô cực $O$ (phần tử trung hòa), tạo thành một nhóm với phép cộng điểm được định nghĩa theo quy tắc hình học/đại số chuẩn:

• $O + P = P + O = P$ với mọi điểm $P$.
• Nếu $P = (x_1, y_1)$ và $Q = (x_2, y_2)$ với $x_1 = x_2$ và $y_1 + y_2 \equiv 0$, thì $P + Q = O$ (hai điểm đối nhau).
• Nếu $P \ne Q$ (và không đối nhau): $\lambda = \dfrac{y_2 - y_1}{x_2 - x_1} \bmod p$.
• Nếu $P = Q$ và $y_1 \ne 0$: $\lambda = \dfrac{3x_1^2 + a}{2y_1} \bmod p$ (nếu $y_1 = 0$ thì $2P = O$).
• Khi đó $x_3 = \lambda^2 - x_1 - x_2 \bmod p$, $y_3 = \lambda(x_1 - x_3) - y_1 \bmod p$.

Cho điểm $P = (x_P, y_P)$ trên đường cong và số nguyên $k \ge 0$, hãy tính điểm $kP = \underbrace{P + P + \dots + P}_{k}$ (quy ước $0 \cdot P = O$), sử dụng thuật toán nhân đôi-và-cộng (double-and-add).

Ví dụ: với $p=23, a=1, b=1$, điểm $P=(3,10)$ nằm trên đường cong (vì $10^2 \equiv 3^3+3+1 \equiv 8 \pmod{23}$). Ta có $2P = (7, 12)$.