可以找到曲線上兩點的 GCD 嗎？
在數學上是否有可能找到素數曲線上兩個點的 GCD，其中一個點不是您在擴展歐幾里得算法中所做的順序？
TLDR：如果我們專門化一個生成點 $ G $ 對於素數階橢圓曲線群，我們可以一致地定義該生成器的兩點的 GCD。但是我們不能有效地找到任意點和一組密碼學興趣，其中離散對數問題很難。
在找到東西之前，我們必須知道它是什麼。因此雨披的子問題：
“素數曲線上兩點的 GCD”是什麼意思？
GCD 代表最大公約數。因此我們需要定義三個概念
什麼是“主要曲線”。在此，曲線代表橢圓曲線。素數是兩者之一的屬性
- 基礎有限域的順序（通常注意到素數順序 $ p $ ，然後該欄位只是整數模 $ p $ );
- 曲線的階數，即曲線的有限點組中有多少元素，包括中性點；
- 或曲線子組的階數（然後經常注意到 $ n $ ，就像我們將要做的那樣）。
素數橢圓曲線點的“除數”的概念，我們假設它是橢圓曲線的一個點，具有一些要定義的屬性。
橢圓曲線點中“最大”的概念。
我們可以一致地定義這些事情！我們假設“素數曲線”是素數階的某個子群 $ n $ 橢圓曲線（可能是整個曲線，可以使用素數場；例如secp256k1，secp256r1），以及 $ G $ 曲線的給定點/組的一個元素，而不是中性點。現在的集合 $ n $ 整數 $ [0,n) $ 與曲線同構，通過平凡同構 $ i\mapsto i,G $ 像往常一樣定義： $ 0,G $ 是團體的中立者， $ i,G $ 是 $ ((i-1),G)+G $ 對於任何 $ i\in[1,n) $ 和 $ + $ 群的法則。
我們可以在集合上定義“除數”和“最大” $ [0,n) $ . 我們可以定義該集合的兩個元素的 GCD（連同有點武斷的 $ \gcd(0,0)=0 $ ）。然後我們可以使用這個同構來定義一個帶有生成點的素數橢圓曲線群的兩個點的最大公約數 $ G $ .
換句話說，我定義了點的 GCD $ P $ 和 $ Q $ 作為匹配私鑰的點（對於生成器 $ G $ ) 是私鑰匹配的 GCD $ P $ 和 $ Q $ ，與匹配的私鑰一個整數 $ [0,n) $ .
如果我們可以有效地解決所考慮的組中的離散對數問題，那麼我們可以有效地計算 GCD（我們解決兩個 DLP，計算整數的 GCD，然後返回曲線）。
更新：在某種程度上反過來也是正確的。如果我們可以有效地計算任意兩點的 GCD $ P $ 和 $ Q $ ，那麼我們可以使用該算法來有效地計算離散對數 $ i $ 任何的 $ P $ . 草圖：我們選擇第一個素數 $ r_j $ 直到 $ n<\prod r_j $ ，並且對於每個 $ j $ 我們發現 $ i\bmod r_j $ 通過要求 GCD $ (P+k,G,r_j,G) $ 這是要麼 $ G $ 或者 $ r_j,G $ , 在後一種情況下表明 $ i+k\equiv0\pmod{r_j} $ . 然後我們發現 $ i $ 由中國剩餘定理。優化可以將相當數量的查詢組合成一個。例如送出 $ (P+k,G,30,G) $ 並測試結果是否為 $ G $ , $ 2,G $ , $ 3,G $ , $ 5,G $ , $ 6,G $ , $ 10,G $ , $ 15,G $ 或者 $ 30,G $ . 通過使用 Baby-Step/Giant-Step 的變體計算預言機輸出的離散對數，可以進一步減少。
我不知道密碼學或其他方面的任何應用程序。
簡短的版本是你不能定義點的 GCD，因為這需要首先定義一個明確的比較它們的有序序列的概念，即一種測試方法 $ [k]P > [j]P , k>j $ 和 $ P \in E $ ， 在哪裡 $ E $ 是由您的橢圓曲線和相應的生成器定義的點集 $ P $ .
這種順序比較與距離的概念有關 $ [k]P $ 和 $ [j]P $ 在定義的空間內。關於具有 p 個元素的有限域中的距離 $ F_p $ 在哪裡 $ E $ 已定義，不幸的是，我們無法以任何方式比較距離 $ F_p $ .
正如 Silverman 所說，有一個很好的方法來定義元素之間的距離 $ Z_p $ 和 $ Q_p $ ，但沒有一個好的方法來定義元素之間的距離 $ F_p $ , 也不適用於橢圓曲線上座標在 $ F_p $ .
有一張天然地圖 $ E(Q_p) to E(F_p) $ 但不幸的是，實際上並沒有任何好的逆映射。Silverman 在下面的論文中討論了這個問題，在嘗試提升然後使用提升來解決 ECDLP 的背景下。
提升和橢圓曲線離散對數，密碼學選定領域 (SAC 2008)，電腦科學講義 5381，Springer–Verlag，柏林，2009 年，82-102。