一條直線在有限域上碰到橢圓曲線上的兩個點，是否必須通過連續來達到另一個點？
Arstechnica的文章標題為“橢圓曲線密碼學的（相對容易理解的）入門書”聲稱這一點；
事實上，你仍然可以在這條曲線和圓點上一起玩台球遊戲。曲線上的直線方程仍然具有相同的屬性。此外，可以有效地計算點運算。您可以將兩點之間的線視覺化為一條在邊界處環繞直到到達一個點的線。就像，在我們的 bizarro 台球遊戲中，當一個球擊中棋盤邊緣（最大值）然後被神奇地傳送到桌子的另一側並繼續前進直到到達一個點，有點像遊戲
並提供動畫（頁面上看到的是GIF，這裡不能連結）。
我做了一個類似的測試，達到了同樣的效果；
簡單的曲線是 $ E\colon y^2=x^3+4x+20 $ 超過 $ \mathbb{F}_{29} $ 和 $ P=(1,5), Q=(5,7) $ 和 $ R = P+Q = (16,2) $ 繪製在圖上。
我已經按照相同的步驟，畫一條線穿過 $ P $ 和 $ Q $ ，並在擊中邊緣時從相反的邊緣繼續！
綠線是可能元素的邊框+1，藍線用於（視覺）檢查延續。
現在經驗足夠了；
如果關於 Arstechnica 的說法在理論上是正確的，那麼理論是什麼？
問題要求證明（真實）事實，為了執行點加法 $ R\gets P+Q $ 以圖形方式在場上的橢圓曲線上 $ \mathbb F_p $ 方程的 $ y^2\equiv x^3+a,x+b\pmod p\tag{1}\label{fgr1} $ 和 $ p $ 適當小（這裡 $ p=29 $ , $ a=4 $ , $ b=20 $ ） 和 $ 4,a^3+27,b^2\not\equiv0\pmod p\tag{2}\label{fgr2} $ 我們可以（除了特殊情況¹ $ P $ 和 $ Q $ 相等或在同一垂直線上）執行幾何構造 $ R $ 按圖
- 在（黑色）方形網格上繪製 $ p $ 除中性線²以外的曲線點（藍點）。
- 畫一條紅線，從 $ P $ 平行於並在的方向 $ \overrightarrow{PQ} $ .
- 一旦線碰到曲線的一個點，而不是 $ Q $ ， 叫它 $ R’ $ ; 然後在垂直（紫色）線上穿過 $ R’ $ ，找到曲線的另一個點並將其稱為結果 $ R $ 的 $ P+Q $ .
- 如果紅線撞到一邊，從那裡畫一條水平或垂直（綠色）線到另一邊；然後從那個交叉點繼續畫紅線，平行於 $ \overrightarrow{PQ} $ ，並迭代到上面的項目符號。
繪製紅線後位移 $ d $ 沿著 $ x $ 軸從 $ P $ , 並考慮到兩邊的環繞，畫紅線的筆有座標 $ \begin{align}x&=(x_P+d)&\bmod p\tag{3}\label{fgr3}\ y&=\left(y_P+d,\frac{y_Q-y_P}{x_Q-x_P}\right)&\bmod p\tag{4}\label{fgr4} \end{align} $ 與計算 $ \mathbb R $ . 理由：左邊是什麼 $ \bmod $ 運算符³在 $ \eqref{fgr3} $ 和 $ \eqref{fgr4} $ 是筆移動的位置 $ d $ 沿著 $ x $ 軸，如果我們沒有在黑邊上環繞。這 $ \bmod $ 運算符擷取環繞的效果。
紅線上座標均為整數的點（包括但不限於曲線上的任意一點）因此有對應的 $ d $ 一個整數，並驗證 $ (y-y_P)(x_Q-x_P)\equiv(x-x_P)(y_Q-y_P)\pmod p\tag{5}\label{fgr5} $ 和任何 $ (x,y) $ 如果我們無限期地繪製它，匹配這個方程將在紅線上； $ P $ 何時到達 $ d=p,(x_Q-x_P) $ （或更早）。
由此可見，我們的圖形搜尋過程 $ R’ $ 到達曲線的一個點（並因此終止），並產生一個點 $ R’ $ 哪個座標 $ (x,y) $ 涉及驗證的整數 $ \eqref{fgr1} $ 和 $ \eqref{fgr5} $ . 但是我們還沒有證明 $ R $ 從…獲取 $ R’ $ 是預期點（我們沒有排除 $ R’=P $ 或曲線的其他一些不需要的點）。
一個直覺的論點是，當我們移除 $ \bmod p $ 從方程，並在該領域工作 $ \mathbb R $ 代替 $ \mathbb F_p $ , $ \eqref{fgr5} $ 成為通過的線的方程 $ P $ 和 $ Q $ 在歐幾里得平面（座標在 $ \mathbb R $ ）。我們繪製紅線並在曲線上找到與該線相交的第三個點的圖形程序因此僅僅是場中的平移⁴ $ \mathbb F_p $ 現場同方程曲線上點加法的圖形構造 $ \mathbb R $ ，因此必須“起作用”，即在曲線點集和中性點上產生一個交換群定律。
或者，我們可以分析證明這個圖形過程終止並產生相同的結果 $ R $ 作為方程曲線上加點的常用公式 $ \eqref{fgr1} $ 和 $ \eqref{fgr2} $ ，也就是當 $ x_P\ne x_Q $ $$ \begin{align} \lambda&\gets(x_Q-x_P)^{-1}(y_Q-y_P)&\bmod p\tag{6}\label{fgr6}\ x_R&\gets\lambda^2-x_P-x_Q&\bmod p\tag{7}\label{fgr7}\ y_R&\gets\lambda(x_P-x_R)-y_R&\bmod p\tag{8}\label{fgr8} \end{align} $$ 注：在此，所有數量都是元素 $ \mathbb F_p $ , 或等價範圍內的整數 $ [0,p) $ . 尤其是， $ (x_Q-x_P)^{-1} $ 是模逆。
證明草圖，其中大部分⁴與該領域中同一方程的點加法公式的可能展示平行 $ \mathbb R $ :
- 我們分析表明 $ \eqref{fgr1} $ 和 $ \eqref{fgr5} $ 由驗證 $ (x,y)\gets(x_R,(-y_R)\bmod p) $ 計算每 $ \eqref{fgr6} $ , $ \eqref{fgr7} $ , $ \eqref{fgr8} $ .
- 條件 $ \eqref{fgr2} $ 允許證明 $ x\ne X_P $ 和 $ x\ne X_Q $ .
- 因此具有這些座標的點 $ (x,y) $ 是在無限期繪製的紅線上，並且兩者都沒有 $ P $ 也不 $ Q $ .
- 當我們消除 $ y $ 從方程 $ \eqref{fgr1} $ 和 $ \eqref{fgr5} $ ，我們得到一個三次方程 $ x $ 在該領域 $ \mathbb F_p $ . 因此，它最多有 3 個不同的解決方案。其中兩個是 $ x_P $ 和 $ x_Q $ ，第三個就是上面的 $ x $ ， 兩者都不 $ x_P $ 也不 $ x_Q $ .
- 由於我們的圖形程序從 $ P $ 並跳過 $ Q $ ，它必須達到一個點 $ x $ 在到達之前 $ P $ 再次。
- 因此 $ R’ $ 我們的搜尋程序有 $ x=x_R $ 的 $ \eqref{fgr7} $
- 同一垂直線上的曲線點共享相同的 $ x $ ，因此相同 $ y^2\bmod p $ 根據曲線方程。由此可見 $ R $ 以圖形方式構造具有座標 $ (x_R,y_R) $ 的 $ \eqref{fgr7} $ , $ \eqref{fgr8} $ , QED
¹ 這種特殊情況細分為
- $ P\ne Q $ ， 在這種情況下 $ P+Q $ 是中性的²。
- $ P=Q $ . 一個圖形結構選擇兩個不同的點 $ S $ 和 $ S’ $ 在同一條垂直線上，兩者都不同於 $ P $ , 併計算 $ (P+S)+(P+S’) $ . 什麼時候 $ S $ 可以在同一水平線上選擇 $ P $ ，這簡化了為 $ P+S $ . 我不知道用於現場曲線的“切線”技術的直接圖形模擬 $ \mathbb R $ .
² 中性線是曲線的一個額外點，不在圖上，經常註明 $ \infty $ 或者 $ 0 $ , 這樣對於任何點 $ S $ , $ S+\infty=S=\infty+S $ .
³ 的 $ \bmod $ 運算符具有來自的規範擴展 $ \mathbb Z $ 至 $ \mathbb R $ : 我們可以定義 $ u\bmod m $ 和 $ u\in\mathbb R $ 和 $ m\in\mathbb R_+^* $ 作為 $ v\in \mathbb R_+ $ 和 $ v<m $ 和 $ (u-v)/m\in\mathbb Z $ .
⁴ 唯一的操作差異是橢圓曲線在現場 $ \mathbb R $ 我們必須在兩個方向上畫紅線，當這是可選的，因為我們在一個有限的集合中，這條線最終環繞回到 $ P $ .
