【密碼學競賽】橢圓曲線上的計算（多倍點問題）

我們現在所要解決的問題是實數域上的橢圓曲線問題，故方程式為： y 2 y^2 y2= x 3 x^3 x3+ a x ax ax+b

1、已知點G=（2，7）在橢圓曲線E11（1，6）上，計算2G的值。

(1)已知橢圓曲線方程E11為： y 2 y^2 y2= x 3 x^3 x3+ x x x+6（mod 11)

(2)求G與曲線相切時的斜率（即求導），得到直線方程

(3)将直線方程代入曲線方程，解一個三次方程

具體步驟及推導過程如下圖所示：

關于分數求模的具體做法可以參考這篇文章。

在推導的時候我弄錯了一件事，以緻于怎麼推導， y 3 y_3 y3​的符号都不對,那就是P+Q并不在PQ上，而是在-PQ上，即P+Q關于x軸的對稱點在PQ上。

直線PQ的斜率為k。

k = { y 2 − y 1 x 2 − x 1 , P ≠ Q 3 x 2 + a 2 y , P = Q k=\left\{ \begin{array}{l} \frac {y_2-y_1}{x_2-x_1},P \neq Q \\ \frac{3x^2+a}{2y},P = Q \end{array} \right. k={x2​−x1​y2​−y1​​,P̸​=Q2y3x2+a​,P=Q​

P+Q的坐标 ( x 3 , y 3 ) (x_3,y_3) (x3​,y3​)為

{ x 3 = k 2 − x 1 − x 2 y 3 = k ( x 1 − x 3 ) − y 1 \left\{ \begin{array}{l} {x_3}=k^2-x_1-x_2 \\ {y_3}=k(x_1-x_3)-y_1 \end{array} \right. {x3​=k2−x1​−x2​y3​=k(x1​−x3​)−y1​​