Intro
最近做題目時，打開題目看到一個高次曲線，還有一個函數實作點的加法，雖然知道八成是橢圓曲線的變種，但完全不知道要怎麼處理，所以寫了這篇文章搜集橢圓曲線不同形式之間的轉換方法。
形式們
| Form name | Equation |
|---|---|
| 最常用的 | \(y^2 = x^3 + ax + b\) |
| Weierstrass | \(y^2 + axy + cy = x^3 + bx^2 + dx + e\) |
| projective | \(y^2z = x^3 + axz^2 + bz^3\) |
| Jacobian | \(y^2 = x^3 + axz^4 + bz^6\) |
| Montgomery | \(by^2 = x^3 + ax^2 + x\) |
| Edward | \(x^2 + y^2 = c^2(1 + dx^2y^2)\) |
| Twisted Edward | \(ax^2 + y^2 = 1 + dx^2y^2\) |
| Huff | \(ax(y^2 - 1) = by(x^2 - 1)\) |
我們的目標是把所有其他curve變成「最常用的」或是 Weiestrass，因為這兩種曲線可以直接塞進 sage 裡面跑。另外，Edward 系列也有 projective 版本，但大同小異。
Projective
對於一個 projective 的點 \((x, y, z)\)，他會對應到橢圓曲線的點 \((\frac{x}{z}, \frac{y}{z})\)，然後參數不變。
Jacobian
跟 projective 很像，一個點 \((x, y, z)\) 會對應到橢圓曲線的 \((\frac{x}{z^2}, \frac{y}{z^3})\)，然後參數不變。
Montgomery
把 Montgomery 的式子除上 \(b^3\)
\[\left(\frac{y}{b}\right)^2 = \left(\frac{x}{b}\right)^3 + \frac{a}{b}\left(\frac{x}{b}\right)^2 + \frac{1}{b^2}\left(\frac{x}{b}\right)\]
這樣就變成 Weiestrass form 了，所以 Montgomery 的點 \((x, y)\) 會對應到 \((\frac{x}{b}, \frac{y}{b})\)。
Edward
這是 Twisted Edward curve 的一個特例，我們可以把原式除上 \(c^2\) 然後改寫成
\[\left(\frac{x}{c}\right)^2 + \left(\frac{y}{c}\right)^2 = 1 + dc^4\left(\frac{x}{c}\right)^2\left(\frac{y}{c}\right)^2\]
這是 Twisted Edward 中 \(a = 1\) 的特例。
Twisted Edward
我們可以它轉換成 Weiestrass curve:
\[y^2 = x^3 + 2(a + d)x^2 + (a - d)^2x\]
且一個點 \((x, y)\) 會被轉換成 \(((a - d)\frac{1 + y}{1 - y}, (a - d)\frac{2(1 + y)}{x(1 - y)})\)。有興趣的人可以推推看
Huff
我們可以它轉換成 Weiestrass curve:
\[y^2 = x^3 + (a + b)x^2 + abx\]
且一個點 \((x, y)\) 會被轉換成 \((\frac{bx - ay}{y - x}, \frac{b - a}{y - x})\)。有興趣的人可以推推看
參考資料同 Twisted Edward
Script
有機會的話或許可以寫個 python 任意轉換這些東西。
Conclusion
雖然還是有題目連 curve 都不給，要用加法公式自己判斷，但有了這個表再去查也方便許多，祝大家再也不會看到完全不知道在幹嘛的曲線！