A random note for some basic things about elliptic curve.
Intro
橢圓曲線
\[y^2 + a_1 xy + a_3 y = x^3 + a_2x^2 + a_4x + a_6\]
的二維曲線，這裡我們只考慮 \(\mathbb{Z}_p\) 下的橢圓曲線，也就是
\[y^2 + a_1 xy + a_3 y = x^3 + a_2x^2 + a_4x + a_6 \pmod{p}\]
其中 \(p\) 為一質數，在大部分的情況下 (\(p \ne 2, 3\))，橢圓曲線都可以化簡成以下形式：
\[y^2 = x^3 + Ax + B \pmod{p}\]
以下我們都使用簡化後的形式。
曲線形狀
橢圓曲線有兩個重要的參數：判別式和 \(j\)-invariant。前者決定橢圓曲線的形狀，後者決定兩條曲線是否等價。
\[\Delta = -16(4A^3+27B^2)\] \[j = \frac{6912A^3}{4A^3 + 27B^2}\]
如果判別式是正的，橢圓曲線會是一個圈圈加一條曲線，負的則會是一條曲線，為零的時候會形成singular curve
Singular Curve
Singular Curve 的形式為 \(y^2 = x^3 - Ax^2\) (注意到這裡我們保留 \(x^2\) 項)，曲線有參數式 \((t^2 + A, t(t^2 + A))\)。若曲線上的 \(P, Q, R\) 都在一條直線 \(y = ax + b\) 上，則這三點的參數 \(t_P, t_Q, t_R\) 滿足方程式
\[t(t^2 + A) = a(t^2 + A) + b\] \[t^3 - at^2 + At - (aA + b) = 0\]
由根與係數的關係，我們有
\[t_Pt_Q + t_Pt_R + t_Qt_R = A\]
然後改寫成
\[\prod_{cyc} \frac{t_P + \sqrt{A}}{t_P - \sqrt{A}} = 1\]
由於 \(t = \frac{y}{x}\)，考慮映射：
\[(x, y) \mapsto \frac{y-\sqrt{A}x}{y + \sqrt{A}x}\]
我們可以把三點共線轉化成三個數字相乘是 \(1\)，也就相當於把橢圓曲線上的 DLP 轉化成一般的 DLP。值得一提的是當 \(A\) 是二次剩餘時是 \(\mathbb{Z}_{q}\) 的DLP，否則是某種高斯整數的 DLP，order 是 \(p + 1\)。