了解蒙哥馬利對橢圓曲線的參數化
我在理解蒙哥馬利曲線 ECM 中仿射座標到投影座標的轉換時遇到了一些麻煩。如果有人可以通過擴展推導來解釋它，將非常感激。
來自：加速分解的波拉德和橢圓曲線方法頁面：261。 $$ \begin{equation}\tag{10.3.1.1}By^2 = x^3 + Ax^2 + x\end{equation} $$
讓 $ P_1 = (x_1, y_1) $ 和 $ P_2 = (x_2, y_2) $ 是曲線中的兩個點，其中 $ x_1 \neq x_2 $ 和 $ x_1x_2 \neq 0 $ . 然後 $ P_1 + P_2 = (x_3, y_3) $ 滿足
$$ x_3 = B[(y_1 - y_2)/(x_1 - x_2)]^2 - A - x_1 - x_2, $$ $$ \begin{align}x_3(x_1 - x_2)^2 & = B(y_1 - y_2)^2 - (A + x_1 + x_2)(x_1 - x_2)^2 \ & = -2By_1y_2 + x_1x_2(x_1 + x_2 + 2A) + x_1 + x_2 \ & = B(x_2y_1 - x_1y_2)^2/x_1x_2. \end{align} $$
相似地， $ P_1 - P_2 = (x_4, y_4) $ 滿足$$ x_4(x_1 - x_2)^2 = B(x_2y_1 + x_1y_2)^2/x_1x_2. $$將這些方程相乘並使用 (10.3.1.1) 得到$$ x_3x_4(x_1 - x_2)^2 = (x_1x_2 - 1)^2 $$除以 $ (x_1 - x_2)^2 $ . 這個等式仍然有效，如果 $ x_1x_2 = 0 $ . 如果 $ P_1 = P2 $ ，類似的推導產生
$$ 4x_1x_3(x_1^2 + Ax_1 + 1) = (x_1^2 - 1)^2 $$ 這些方程式僅參考 $ x_i $ ，而不是 $ y_i $ . 幸運的是，ECM 不需要我們計算 $ y_i $ .
（我不明白這一點以下的所有內容。有人可以幫我擴展這些推導嗎？似乎過於簡單化了）
讓 $ P $ 是曲線上的任意點，讓 x 座標 $ nP $ 是有理數 $ X_n/Z_n $ . 從比例 $ (X_{m-n}:Z_{m-n}),(X_m:Z_m) and (X_n:Z_n) $ , 可以計算比率 $ (X_{m-n}:Z_{m-n}) $ 通過加法公式。
$$ X_{m+n} \leftarrow Z_{m-n}(X_mX_n - Z_mZ_n)^2\ Z_{m+n} \leftarrow X_{m-n}(X_mZ_n - Z_mX_n)^2 $$
如果 $ mP \neq nP $ ，並通過重複公式$$ \begin{align} X_{2n} & \leftarrow (X_n^2 - Z_n^2)^2, \ Z_{2n} & \leftarrow 4X_nZ_n(X_n^2 + AX_nZ_n + Z_n^2) \end{align} $$
如果我們儲存比率，成本會下降 $ (X_m:Z_m:X_m+Z_m:X_m-Z_m) $ 並將公式重寫為（加法公式的右側已乘以4）
$$ \begin{align} X_{m+n} & \leftarrow Z_{m-n}[(X_m - Z_m)(X_n + Z_n) + (X_m + Z_m)(X_n - Z_n)]^2 \ Z_{m+n} & \leftarrow X_{m-n}[(X_m - Z_m)(X_n + Z_n) - (X_m + Z_m)(X_n - Z_n)]^2 \ \end{align} $$ 和
$$ \begin{align} 4X_nZ_n & = (X_n + Z_n)^2 - (X_n - Z_n) \ X_{2n} & \leftarrow (X_n + Z_n)^2(X_n - Z_n)^2 \ Z_{2n} & \leftarrow (4X_nZ_n)((X_n - Z_n)^2 + ((A + 2)/4)(4X_nZ_n)) \end{align} $$
寫 $ (x_i, y_i) = (X_i : Y_i : Z_i) $ ， 以便 $ x_i = X_i/Z_i $ 和 $ y_i = X_i/Z_i $ ， 在哪裡 $ Z_i \ne 0 $ 是任意的。（如果您不熟悉投影座標或喜歡視覺效果，請參閱真實橢圓曲線上的投影座標圖示。）
讓我們以加倍公式為例，其中 $ (x_3, y_3) = (x_1, y_1) + (x_1, y_1) = [2](x_1, y_1) $ :
$$ \begin{equation*} 4 x_1 x_3 ({x_1}^2 + A x_1 + 1) = ({x_1}^2 - 1)^2 \tag{p. 261, second display} \end{equation*} $$
以便
$$ \begin{equation*} x_3 = \frac{({x_1}^2 - 1)^2}{4 x_1 ({x_1}^2 + A x_1 + 1)}, \end{equation*} $$
在投影座標中是
$$ \begin{align*} \frac{X_3}{Z_3} &= \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2} {4 \frac{X_1}{Z_1} \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \ &= \frac{{Z_1}^4}{{Z_1}^4} \cdot \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2} {4 \frac{X_1}{Z_1} \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \ &= \frac{\bigl({Z_1}^2\bigr)^2 \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2} {4 X_1 Z_1 {Z_1}^2 \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \ &= \frac{\bigl({X_1}^2 - {Z_1}^2\bigr)^2} {4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr)}. \end{align*} $$
由此，我們可以讀出分子和分母：
$$ \begin{equation*} X_3 = \bigl({X_1}^2 - {Z_1}^2\bigr)^2 \qquad\text{and}\qquad Z_3 = 4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr). \end{equation*} $$
顯然，我們也可以將它們都乘以相同的任意非零因子，但這裡沒有必要。
對於不加倍的加法公式，您正在嘗試編寫 $ [m + n]P = [m]P + [n]P $ 按照 $ X $ 和 $ Z $ 座標 $ [m]P $ , $ [n]P $ ， 和 $ [m - n]P = [m]P - [n]P $ . 也就是說，你有 $ x_1 = x([m]P) $ , $ x_2 = x([n]P) $ ， 和 $ x_4 = x([m - n]P) $ ，而你試圖找到 $ x_3 = x([m + n]P) $ . 使用 p 上的頂部方程。261,$$ x_3 x_4 (x_1 - x_2)^2 = (x_1 x_2 - 1)^2, $$並再次寫出 $ x_i = X_i/Z_i $ .
最後一部分是整理以減少不同中間量的數量，例如使用以下觀察：
$$ \begin{multline*} {X_1}^2 + A X_1 Z_1 + {Z_1}^2 = {X_1}^2 - 2 X_1 Z_1 + {Z_1}^2 + 2 X_1 Z_1 + (A/4) 4 X_1 Z_1 \ = (X_1 - Z_1)^2 + \frac{A + 2}{4} 4 X_1 Z_1 \end{multline*} $$
寫出整個加倍公式 $ X_1 \pm Z_1 $ 總成本為 4A + 2S + 3M。