配對中扭曲曲線的順序
我們正在使用 Barreto-Naehrig 曲線進行最佳 Ate 配對，我試圖確保我所做的觀察可以概括。
我們定義 $ E $ 作為 $ y^2 = x^3 + 3 $ 並使用擴展塔 $$ \begin{equation}\begin{split} \mathbb{F}{p^2} &= \mathbb{F}p[u] / (u^2 + 1) \ \mathbb{F}{p^6} &= \mathbb{F}{p^2}[v] / (v^3 - (u+3)) \ \mathbb{F}{p^{12}} &= \mathbb{F}{p^6}[w] / (w^2 - v) \end{split}\end{equation} $$
並定義扭曲曲線 $ E’ $ 作為 $ y^2 = x^3 + 3/(u+3) $ .
在 Sage 中玩耍，調整 BN 參數並使用不同素數的曲線 $ p $ 並訂購 $ r $ ，我發現順序 $ E’ $ 曾是 $ r * (2p - r) $ . 但我無法找到任何證實這總是正確的。有誰知道這是否普遍正確，或者我是否發現與我的（非常小的）曲線樣本重合？
**摘要：**不，這不適用於所有曲線。不過，它確實適用於所有 Barreto-Naehrig 曲線。但是，有一些微妙之處。
**首先，一些定義。**為了準確地定義問題，我必須回憶一些已知的結果。
讓 $ \mathbb{F}_q $ 既不是特徵的有限域 $ 2 $ 或者 $ 3 $ ; 那是， $ q = p^f $ 對於一些素數 $ p \geq 5 $ 和一些整數 $ f \geq 1 $ . 我們考慮曲線 $ E $ 超過 $ \mathbb{F}_q $ 帶有短 Weierstraß 方程 $ y^2 = x^3 + Ax + B $ 對於兩個常數 $ A $ 和 $ B $ 這樣 $ 4A^3 + 27B^2 \neq 0 $ （如果不滿足最後一個屬性，則存在一個沒有切線的奇異點，因此無法以有意義的方式將其添加到自身，並且曲線不是嚴格意義上的曲線）。
曲線同構對應於變數的仿射變化；這些是將線映射到線的平面變換，因此可以保存點加法。可以看出，具有短 Weierstraß 方程的兩條曲線之間變數的唯一可能變化是 $ (x,y) \mapsto (e^2 x, e^3 y) $ 對於任何 $ e \neq 0 $ 在 $ \mathbb{F}_q $ . 這種變數的變化將曲線方程轉換為： $ y^2 = x^3 + Ae^{-4}x + Be^{-6} $ . 因此，我們可以在很大程度上“規範化” $ A $ 或者 $ B $ 到一小組可能的值。
這 $ j $ - 曲線的不變數是場元素： $$ j = 1728 \frac{4A^3}{4A^3 + 27B^2} $$ 的每個元素 $ \mathbb{F}q $ 是一個可能的值 $ j $ -不變的。當兩條曲線相同時 $ j $ -invariant，那麼它們要麼是彼此同構的（在上面解釋的意義上），要麼它們被稱為彼此的*扭曲。*當兩條曲線扭曲時，這意味著它們在場擴展中是同構的；也就是說，有一個學位 $ k > 1 $ 這樣，提升到 $ \mathbb{F}{q^k} $ ，這兩個曲線方程成為同一曲線的兩個同構定義（這也適用於代數閉包 $ \mathbb{F}_q $ ）。扭曲稱為二次如果 $ k = 2 $ ,立方如果 $ k = 3 $ ， 等等。
在一般情況下，當 $ j $ -invariant 不同於 $ 0 $ 並從 $ 1728 $ ，曲線允許單次扭曲（直到同構）並且它是二次的。即，讓 $ d $ 是一個非二次餘數 $ \mathbb{F}_q $ （即沒有平方根的元素）；扭曲方程為： $ y^2 = x^3 + Ad^2x + Bd^3 $ . 可以看出，如果我們“發明”一個平方根 $ e $ 的 $ d $ ，那麼這產生了上面描述的同構。 $ e $ 不存在，通過構造，在 $ \mathbb{F}_q $ ; 因此，毗鄰 $ e $ 至 $ \mathbb{F}q $ 產量 $ \mathbb{F}{q^2} $ , 2 次擴展（在通常的多項式域擴展定義中，我們使用不可約多項式 $ X^2 - d $ , 並呼叫 $ e $ 它的根源之一是領域擴展）。
可以證明，如果曲線 $ E(\mathbb{F}_q) $ 有紅衣主教 $ q+1-t $ （和 $ t $ 是Frobenius 的跡，以 Hasse 定理為界： $ t^2 \leq 4q $ )，則轉折有基數 $ q+1+t $ ，即跟踪被簡單地否定。基本證明在於列舉元素 $ x $ 在 $ \mathbb{F}_q $ :
- 如果 $ x $ 是這樣的 $ x^3 + Ax + B $ 是平方 $ y \neq 0 $ ，那麼有兩點 $ (x,y) $ 和 $ (x,-y) $ 上 $ E $ . 但是之後， $ (dx)^3 + Ad^2(dx) + Bd^3 = d^3 y^2 $ ，並且由於 $ d $ 不是正方形 $ \mathbb{F}_q $ ，這最後一個值不是正方形，也沒有點 $ (dx,y’) $ 轉折 $ E’ $ .
- 相反，如果 $ x^3 + Ax + B $ 不是正方形 $ \mathbb{F}_q $ ，那麼沒有意義 $ (x,y) $ 上 $ E $ , 但會有兩點 $ (dx,y’) $ 上 $ E’ $ .
- 如果 $ x^3 + Ax + B = 0 $ ， 然後 $ (x,0) $ 是一個點 $ E $ ， 和 $ (dx,0) $ 是一個點 $ E’ $ .
因此，通過列舉 $ q $ 的可能值 $ x $ ，我們總是得到兩個點：要麼兩個在 $ E $ , 或兩個 $ E’ $ , 或其中之一 $ E $ 和 $ E’ $ . 這涵蓋了所有要點 $ E $ 和 $ E’ $ 除了無限遠點，它本身沒有座標，並且是兩條曲線的一部分。所以， $ #E + #E’ = 2q + 2 $ ，從中得到結果。
請注意，從 $ j $ -不變數，匹配曲線方程為： $$ y^2 = x^3 + \frac{3j}{1728 - j} x + \frac{2j}{1728 - j} $$
如果 $ j $ -invariant 為零，則這對應於方程曲線 $ y^2 = x^3 + B $ （IE $ A = 0 $ ）。這樣一個方程只有六條曲線，直到同構（即正好有六個同構類）；而且，它們都是彼此的曲折。其中一些是二次扭曲，一些是三次扭曲，還有一些是六次扭曲。
如果 $ q = 2 \bmod 3 $ （這可能只發生在特徵 $ p $ 本身等於 $ 2 $ 模組 $ 3 $ ， 和 $ q = p^f $ 對於奇數 $ f $ )，那麼每個元素 $ \mathbb{F}_q $ 有一個立方根；因此，對於每個 $ y \in \mathbb{F}_q $ , 有一個 $ x $ 這樣 $ x^3 = y^2 - B $ . 由此可知曲線階數為 $ q + 1 $ , 曲線是超奇異的, 曲線的嵌入度是 $ 2 $ ，並且您不希望將其用於配對。超奇異曲線有很多特殊的性質，這裡我就不詳述了。
我現在假設 $ q = 1 \bmod 3 $ . 自從 $ q $ 是奇數（它是特徵的冪，我們假設它不等於 $ 2 $ ，並且是素數，因此是奇數），因此 $ q = 1 \bmod 6 $ . 這意味著存在非平凡的第六統一根，並且存在元素 $ \xi $ 這樣 $ X^6 - \xi $ 是不可約的（ Barreto-Naehrig 文章中給出了一個簡短的證明，第 6 頁）。我們通過列舉方程獲得所有曲線類： $$ y^2 = x^3 + \frac{B}{\xi^i} $$ 對所有人 $ i $ 從 $ 0 $ 至 $ 5 $ .
和 $ \xi^0 $ , 我們有曲線 $ E $ 本身。和 $ \xi^3 $ ，我們得到一個二次扭曲 $ E $ . 和 $ \xi^2 $ 和 $ \xi^4 $ ，我們得到兩個三次扭曲 $ E $ . 和 $ \xi $ 和 $ \xi^5 $ ，我們得到兩個六性扭曲 $ E $ .
現在為團體訂單。當曲線有 $ j $ -不變數為零，則其群階只能取六個值（對應六個同構類）。考慮整數 $ 4q - t^2 $ : 如上所述，根據哈斯定理，這個整數是非負的。您可以通過刪除所有具有偶數指數的素數因子來使其無平方；即你可以寫： $$ 4q - t^2 = Dv^2 $$ 對於整數 $ D $ 和 $ v $ ， 在哪裡 $ D $ 是無平方的（即沒有素數 $ z $ 這樣 $ z^2 $ 劃分 $ D $ ）。通過整數分解的唯一性， $ D $ 是唯一定義的。對於曲線 $ j $ - 不變數為零，碰巧 $ D = 3 $ ， 總是; 這也適用於另一種方式：如果 $ D = 3 $ , 那麼曲線必須有 $ j $ -不變數零（這來自複數乘法理論，這確實相當複雜）。從價值 $ v $ ，我們可以得到曲線扭曲的階數 $ E $ . 我們記得 $ #E(\mathbb{F}_q) = q + 1 - t $ ; 然後：
- 二次扭曲 $ E $ 有秩序 $ q + 1 + t $ .
- 三次曲折 $ E $ 有秩序 $ q + 1 - (3v-t)/2 $ 或者 $ q + 1 - (-3v-t)/2 $ .
- 性轉折 $ E $ 有秩序 $ q + 1 - (-3v+t)/2 $ 或者 $ q + 1 - (3v+t)/2 $ .
有關展示和提示，請參閱Eta Pairing Revisited，第 4 節。
第三種情況是當 $ j $ -不變數等於 $ 1728 $ . 這對應於曲線方程 $ y^2 = x^3 + Ax $ ， IE $ B = 0 $ . 如果 $ q = 3 \bmod 4 $ ，那麼這就定義了一條超奇異曲線。如果 $ q = 1 \bmod 4 $ ，然後你得到四個同構類，它們都是相互扭曲的；這樣的曲線接受一個二次扭曲和兩個四次扭曲（擴展度 4）。我不會詳細說明那個，但請參閱 Hess-Smart-Vercauteren 文章了解詳細資訊。
另一個有用的結果是，給定一條曲線 $ E $ 在欄位上定義 $ \mathbb{F}_q $ , 有順序 $ #E(\mathbb{F}q) = q + 1 - t $ ， 的順序 $ E $ 過域擴展可以計算如下： $$ #E(\mathbb{F}{q^n} = q^n + 1 - (\alpha^n + \overline{\alpha}^n) $$ 對於所有整數 $ n \geq 1 $ ， 在哪裡 $ \alpha $ 和 $ \overline{\alpha} $ 是多項式的兩個（复）根 $ X^2 - tX + q $ . 有一個很好的遞歸關係：
- $ \alpha^0 + \overline{\alpha}^0 = 2 $
- $ \alpha^1 + \overline{\alpha}^1 = t $
- $ \alpha^{n+1} + \overline{\alpha}^{n+1} = t(\alpha^n + \overline{\alpha}^n) - q(\alpha^{n-1} + \overline{\alpha}^{n-1}) $
尤其是， $ \alpha^2 + \overline{\alpha}^2 = t^2 - 2q $
所有這些都說明了，讓我們看看你的具體問題。
你有一個素數 $ p = 1 \bmod 3 $ . 一條曲線定義在 $ E(\mathbb{F}_p) $ , 有方程 $ y^2 = x^3 + B $ ; 這是一條曲線 $ j $ -不變的零。它的順序表示 $ r $ . 這條曲線有跡 $ s $ , 就是這樣 $ r = p + 1 - s $ . 在 BN 曲線中， $ r $ 也是素數，但這在這裡無關緊要。
然後你將曲線提升到 $ \mathbb{F}_{p^2} $ . 我寫的 $ q = p^2 $ : 你對曲折感興趣 $ E $ 定義為 $ \mathbb{F}_q $ ，而不是曲折 $ E $ 定義為 $ \mathbb{F}_p $ . 對這些事情要準確很重要；這就是我使用的原因 $ q $ 並不是 $ p $ 在上述所有治療中。
根據上面的結果，您可以計算： $$ #E(\mathbb{F}_q) = q + 1 - (s^2 - 2p) $$ 即曲線上的軌跡 $ \mathbb{F}_q $ 是 $ t = s^2 - 2p $ .
因為這是一條曲線 $ j $ - 不變零，它允許 5 個曲折，其中兩個是六分法，有順序： $$ \begin{eqnarray*} o_1 &=& q + 1 - \frac{3v + t}{2} \ o_2 &=& q + 1 - \frac{-3v + t}{2} \ \end{eqnarray*} $$ 在哪裡 $ v $ 是這樣的 $ 4q - t^2 = 3v^2 $ .
**那麼問題是：**是否可以保證這兩個性彆扭曲中的一個具有完全的順序？ $ r(2p-r) = (p+1-s)(p-1+s) $ ?
**答案是不。**這是一個反例：
讓 $ p = 31 $ . 曲線 $ y^2 = x^3 + 3 $ 有訂單 $ r = 43 $ ，即它的跡是 $ s = -11 $ . 二次擴展是 $ q = 961 $ ; 超過 $ \mathbb{F}_q $ , 曲線 $ E $ 有痕跡 $ t = s^2 - 2p = 59 $ . 我們注意到 $ 4q - t^2 = 363 = 3(11^2) $ ， 因此 $ v = 11 $ . 那麼這兩個性彆扭曲的順序是 $ o_1 = 916 $ 和 $ o_2 = 949 $ . 然而， $ (p+1-s)(p-1+s) = 817 $ , 這兩者都不同 $ o_1 $ 和 $ o_2 $ .
**然而，對於 BN 曲線，這是可行的。**回想一下，BN 曲線由一個整數參數化 $ u $ ， 和：
- $ p = 36u^4 + 36u^3 + 24u^2 + 6u + 1 $
- $ s = 6u^2 + 1 $
整數 $ u $ 被選擇使得 $ p $ 是素數，曲線階數 $ r = p+1-s $ 也是素數。在這種情況下，人們可以注意到： $$ 4p - s^2 = 3(6u^2 + 4u + 1)^2 $$ 因此 $ s $ 是一些曲線的軌跡 $ \mathbb{F}_p $ 和 $ j $ -不變的零。然後我們可以將該曲線提升到 $ \mathbb{F}_q $ 和 $ q = p^2 $ ，並且那個將有兩個性彆扭曲。
這種選擇 $ p $ 和 $ s $ 暗示 $ r $ 劃分 $ p^{12}-1 $ ，這意味著嵌入度（定義配對的關鍵屬性）最多為 $ 12 $ ，因此曲線將是“配對友好的”。
使用這些參數，您可以獲得：
- $ q = p^2 $
- $ t = -36u^4 - 72u^3 - 36u^2 - 12u - 1 $
- $ 4q - t^2 = 3v^2 $ 和 $ v = (6u^2+4u+1)(6u^2+1) $
因此，兩個性彆扭曲順序是： $$ \begin{eqnarray*} o_1 &=& 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1044u^4 + 360u^3 + 84u^2 + 12u + 1 \ o_2 &=& 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1152u^4 + 432u^3 + 120u^2 + 24u + 4 \ \end{eqnarray*} $$
如果你計算表達式 $ (p+1-s)(p-1+s) $ ，你會發現你得到的多項式與 $ o_1 $ . 因此，對於任何 BN 曲線，保證有一個六線扭曲 $ E’ $ 的 $ E $ （超過 $ \mathbb{F}_q $ ) 會有訂單 $ (p+1-s)(p-1+s) = r(2p-r) $ .
**注意：**仍然有兩個性彆扭曲。當您選擇您的 $ \xi $ 這樣 $ X^6-\xi $ 是不可約的 $ \mathbb{F}_q $ ，你可能不走運並得到錯誤的。另一個扭曲可以通過使用獲得 $ \xi^5 $ 代替（或者你可以再試一次 $ \xi $ ，因為您想要一個使計算最容易進行的操作）。