Schoof演算法

Schoof 演算法'是一種計算有限體上橢圓曲線上點數的有效演算法。該演算法應用於橢圓曲線密碼學，其中了解點的數量對於判斷橢圓曲線上點群中離散對數問題的難度至關重要。

該演算法由 René Schoof 於 1985 年發表，是一項理論上的突破，因為它是第一個用於計算橢圓曲線上點數的決定性多項式時間演算法。在 Schoof 演算法出現之前，計算橢圓曲線上點數的方法，如樸素演算法和大小步演算法，大多繁瑣且具有指數級的執行時間。

本文解釋 Schoof 的方法，重點在於闡述該演算法結構背後的數學思想。

簡介

設 E 為定義在有限體 \mathbb{F}_{q} 上的橢圓曲線，其中 q=p^n ， p 為質數， n 為整數 \geq 1 。在特徵 \neq 2, 3 的體上，橢圓曲線可由一個（短）Weierstrass 方程式給出：

y^2 = x^3 + Ax + B

其中 A,B\in \mathbb{F}_{q} 。定義在 \mathbb{F}_{q} 上的點集由滿足曲線方程式的解 (a,b)\in\mathbb{F}_{q}^2 和一個無窮遠點 O 組成。將橢圓曲線上的群律限制在此集合上，可以看出此集合 E(\mathbb{F}_{q}) 構成一個阿貝爾群，其中 O 作為單位元素。為了計算橢圓曲線上的點數，我們計算 E(\mathbb{F}_{q}) 的基數。 Schoof 計算基數 \# E(\mathbb{F}_{q}) 的方法利用了 Hasse 橢圓曲線定理、中國剩餘定理以及除法多項式。

Hasse 定理

Hasse 定理指出，如果 E/\mathbb{F}_{q} 是有限體 \mathbb{F}_{q} 上的橢圓曲線，則 \# E(\mathbb{F}_q) 滿足

\mid q + 1 - \# E(\mathbb{F}_{q}) \mid \leq 2\sqrt{q}.

這個由 Hasse 在 1934 年提出的強大結果，將 \# E(\mathbb{F}_{q}) 的範圍縮小到一個有限（儘管很大）的可能性集合中，從而簡化了我們的問題。定義 t 為 q + 1 - \# E(\mathbb{F}_{q}) ，利用這個結果，我們現在只需計算 t 模 N 的值（其中 N > 4\sqrt{q} ），就足以確定 t ，進而確定 \# E(\mathbb{F}_{q}) 。雖然對於一般的 N ，沒有直接有效計算 t \pmod N 的方法，但對於小的質數 l ，計算 t \pmod l 卻是相當有效率的。我們選擇 S=\{l_1,l_2,...,l_r\} 作為一個由不同質數組成的集合，使得 \prod l_i = N > 4\sqrt{q} 。給定所有 l_i\in S 的 t \pmod {l_i} 值，中國剩餘定理允許我們計算出 t \pmod N 。

為了計算質數 l \neq p 下的 t \pmod l ，我們利用弗羅貝尼烏斯自同態 \phi 的理論和除法多項式。注意，只考慮質數 l \neq p 並無損失，因為我們總是可以選擇一個更大的質數來取代它，以確保乘積足夠大。無論如何，Schoof 演算法最常用於處理 q=p 的情況，因為對於小特徵的體，有更有效率的所謂 p 進演算法。

弗羅貝尼烏斯自同態

給定定義在 \mathbb{F}_{q} 上的橢圓曲線 E ，我們考慮 E 在 \mathbb{F}_{q} 的代數閉包 \bar{\mathbb{F}}_{q} 上的點；也就是說，我們允許點的座標在 \bar{\mathbb{F}}_{q} 中。 \bar{\mathbb{F}}_{q} 在 \mathbb{F}_q 上的弗羅貝尼烏斯自同態可擴展到橢圓曲線上，定義為 \phi : (x, y) \mapsto (x^{q}, y^{q}) 。

這個映射在 E(\mathbb{F}_{q}) 上是恆等映射，並且可以擴展到無窮遠點 O ，使其成為一個從 E(\bar{\mathbb{F}}_{q}) 到自身的群同態。

弗羅貝尼烏斯自同態滿足一個二次多項式，該多項式透過以下定理與 E(\mathbb{F}_{q}) 的基數相關聯：

定理：由 \phi 給出的弗羅貝尼烏斯自同態滿足特徵方程式

\phi ^2 - t\phi + q = 0, 其中 t = q + 1 - \# E(\mathbb{F}_q)

因此，對於所有 P=(x, y) \in E ，我們有 (x^{q^{2}}, y^{q^{2}} ) + q(x, y) = t(x^{q}, y^{q}) ，其中 + 表示橢圓曲線上的加法，而 q(x,y) 和 t(x^{q},y^{q}) 分別表示 (x,y) 與 q 的純量乘法以及 (x^{q},y^{q}) 與 t 的純量乘法。

人們可以嘗試在 E 的座標環 \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B) 中，將這些點 (x^{q^{2}}, y^{q^{2}}) 、 (x^{q}, y^{q}) 和 q(x, y) 作為函數進行符號計算，然後搜索滿足方程式的 t 值。然而，多項式的次數會變得非常大，這種方法並不實用。

Schoof 的想法是將此計算限制在不同小質數 l 階的點上進行。固定一個奇質數 l ，我們現在轉向解決確定 t_{l} （定義為 t \pmod l ）的問題，對於一個給定的質數 l \neq 2, p 。如果一個點 (x, y) 位於 l -撓子群 E[l]=\{P\in E(\bar{\mathbb{F}_{q}}) \mid lP=O \} 中，則 qP = \bar{q}P ，其中 \bar{q} 是滿足 q \equiv \bar{q} \pmod l 和 \mid \bar{q} \mid< l/2 的唯一整數。注意 \phi(O) = O 且對於任何整數 r ，我們有 r\phi (P) = \phi (rP) 。因此 \phi (P) 的階將與 P 相同。因此對於屬於 E[l] 的 (x, y) ，如果 t \equiv \bar{t} \pmod l ，我們也有 t(x^{q}, y^{q})= \bar{t}(x^{q}, y^{q}) 。因此，我們已將問題簡化為求解以下方程式：

(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) \equiv \bar{t}(x^{q}, y^{q}),

其中 \bar{t} 和 \bar{q} 的整數值在 [-(l-1)/2,(l-1)/2] 範圍內。

質數模計算

第 l 個除法多項式的根恰好是 l 階點的 x 座標。因此，將 (x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) 的計算限制在 l -撓點上，意味著在 E 的座標環中並模第 l 個除法多項式來計算這些表達式。也就是說，我們在 \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l}) 中進行運算。這特別意味著，透過 (X(x,y),Y(x,y)):=(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) 定義的 X 和 Y ，其 y 的次數最多為 1， x 的次數最多為 (l^2-3)/2 。

純量乘法 \bar{q}(x, y) 可以透過倍加法或使用第 \bar{q} 個除法多項式來完成。後者的方法給出：

\bar{q} (x,y) = (x_{\bar{q}},y_{\bar{q}}) = \left( x - \frac {\psi_{\bar{q}-1} \psi_{\bar{q}+1}}{\psi^{2}_{\bar{q}}}, \frac{\psi_{2\bar{q}}}{2\psi^{4}_{\bar{q}}} \right)

其中 \psi_{n} 是第 n 個除法多項式。注意 y_{\bar{q}}/y 僅為 x 的函數，將其記為 \theta(x) 。

我們必須將問題分為兩種情況： (x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y) 的情況，以及 (x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y) 的情況。注意，這些等式是在模 \psi_l 下進行檢查的。

情況 1: (x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)

透過使用群 E(\mathbb{F}_{q}) 的加法公式，我們得到：

X(x,y) = \left( \frac{y^{q^{2}} - y_{\bar{q}}}{x^{q^{2}} - x_{\bar{q}}} \right) ^{2} - x^{q^{2}} - x_{\bar{q}}.

注意，如果不等式的假設是錯誤的，這個計算將會失敗。

我們現在可以使用 x 座標將 \bar{t} 的選擇範圍縮小到兩種可能性，即正值和負值的情況。之後使用 y 座標來確定兩種情況中哪一種成立。

我們首先證明 X 僅為 x 的函數。考慮 (y^{q^{2}} - y_{\bar{q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar{q}}/y)^{2} 。因為 q^{2}-1 是偶數，透過將 y^{2} 替換為 x^3+Ax+B ，我們將表達式重寫為

(x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x))^2

並且得到

X(x)\equiv (x^3+Ax+B)\left(\frac{(x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x)}{x^{q^2}-x_{\bar{q}}}\right)^2\bmod \psi_l(x).

現在，如果對於某個 \bar{t}\in [0,(l-1)/2] ，有 X \equiv x^{q} _ {\bar{t}}\bmod \psi_l(x) ，則 \bar{t} 滿足

\phi ^{2}(P) \mp \bar{t} \phi(P) + \bar{q}P = O

對於所有 l -撓點 P 。

如前所述，使用 Y 和 y_{\bar{t}}^{q} ，我們現在能夠確定 \bar{t} 的兩個值（ \bar{t} 或 -\bar{t} ）中哪一個是正確的。這就給出了 t\equiv \bar{t}\pmod l 的值。Schoof 演算法將每個考慮的質數 l 的 \bar{t}\pmod l 值儲存在變數 t_l 中。

情況 2: (x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)

我們從假設 (x^{q^{2}}, y^{q^{2}}) = \bar{q}(x, y) 開始。因為 l 是奇質數，所以 \bar{q}(x, y)=-\bar{q}(x, y) 不可能成立，因此 \bar{t}\neq 0 。特徵方程式得出 \bar{t} \phi(P) = 2\bar{q} P 。因此 \bar{t}^{2}\bar{q} \equiv (2q)^{2} \pmod l 。這意味著 \bar{q} 是模 l 的二次剩餘。設 q \equiv w^{2} \pmod l 。在 \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l}) 中計算 w\phi(x,y) ，並檢查是否 \bar{q}(x, y)=w\phi(x,y) 。如果是，則 t_{l} 為 \pm 2w \pmod l ，具體取決於 y 座標。

如果 \bar{q} 不是模 l 的二次剩餘，或者方程式對於 w 和 -w 都不成立，那麼我們關於 (x^{q^{2}}, y^{q^{2}}) = +\bar{q}(x, y) 的假設是錯誤的，因此 (x^{q^{2}}, y^{q^{2}}) = - \bar{q}(x, y) 。特徵方程式給出 t_l=0 。

額外情況 l = 2

回想一下，我們最初的考慮排除了 l = 2 的情況。由於我們假設 q 是奇數， q + 1 - t \equiv t \pmod 2 ，特別是， t_{2} \equiv 0 \pmod 2 若且唯若 E(\mathbb{F}_{q}) 有一個 2 階元素。根據群中的加法定義，任何 2 階元素的形式必須是 (x_{0}, 0) 。因此， t_{2} \equiv 0 \pmod 2 若且唯若多項式 x^{3} + Ax + B 在 \mathbb{F}_{q} 中有根，若且唯若 \gcd(x^{q}-x, x^{3} + Ax + B)\neq 1 。

演算法

    輸入：
        1. 橢圓曲線  E = y^{2}-x^{3}-Ax-B 。
        2. 有限體  F_q  的一個整數  q ，其中  q=p^{b}, b \ge 1 。
    輸出：
         E  在  F_q  上的點數。
    選擇一個不包含  p  的奇質數集合  S 
    
    . 
    下面迴圈中的所有計算均執行於

                    否則
                        
        否則如果  \bar{q}  是模  l  的二次剩餘，則

            否則
                
        否則
            
    使用中國剩餘定理，從方程式  t \equiv t_{l} \pmod l （其中  l \in S ）計算  t  模  N 。
    輸出  q+1-t 。

複雜度

大部分計算量在於對每個質數 l 計算 \phi(P) 和 \phi^{2}(P) ，也就是計算 x^q 、 y^q 、 x^{q^2} 和 y^{q^2} 。這涉及在環 R = \mathbb{F}_{q}[x, y]/ (y^2-x^3-Ax-B, \psi_l) 中進行冪運算，需要 O(\log q) 次乘法。由於 \psi_l 的次數是 \frac{l^2-1}{2} ，環中的每個元素都是一個次數為 O(l^2) 的多項式。根據質數定理，大小約為 O(\log q) 的質數大約有 O(\log q) 個，這表示 l 為 O(\log q) ，因此我們得到 O(l^2) = O(\log^2q) 。因此，環 R 中的每次乘法需要 O(\log^4 q) 次 \mathbb{F}_{q} 中的乘法，而後者又需要 O(\log^2 q) 次位元運算。總計，對每個質數 l ，位元運算的次數為 O(\log^7 q) 。考慮到需要對 O(\log q) 個質數中的每一個都執行此計算，Schoof 演算法的總複雜度結果為 O(\log^8 q) 。使用快速多項式和整數算術可將其降至 \tilde{O}(\log^5 q) 。

Schoof 演算法的改進

在 1990 年代，Noam Elkies 和 A. O. L. Atkin 相繼對 Schoof 的基本演算法進行了改進，他們將先前考慮的質數集 S = \{l_1, \ldots, l_s\} 限制為某種特定類型的質數。這些質數分別被稱為 Elkies 質數和 Atkin 質數。如果特徵方程式 \phi^2-t\phi+ q = 0 在 \mathbb{F}_l 上分裂，則質數 l 稱為 Elkies 質數；反之，不是 Elkies 質數的質數則稱為 Atkin 質數。Atkin 展示了如何將從 Atkin 質數獲得的資訊與從 Elkies 質數獲得的資訊相結合，從而產生一種高效的演算法，即後來的 Schoof–Elkies–Atkin 演算法。需要解決的第一個問題是確定一個給定的質數是 Elkies 質數還是 Atkin 質數。為此，我們使用模多項式，它源於對模形式的研究以及將複數上的橢圓曲線詮釋為格。一旦確定了是哪種情況，我們就可以使用一個次數比相應的除法多項式更低的多項式來進行運算，即 O(l) 而非 O(l^2) 。為了高效實現，使用了機率性求根演算法，這使其成為一個拉斯維加斯演算法，而非決定性演算法。在啟發式假設下，即上界為 O(\log q) 的質數中約有一半是 Elkies 質數，這產生了一個比 Schoof 演算法更有效率的演算法，其期望執行時間在使用樸素算術時為 O(\log^6 q) ，在使用快速算術時為 \tilde{O}(\log^4 q) 。雖然已知這個啟發式假設對大多數橢圓曲線成立，但並不知道它是否在所有情況下都成立，即使在廣義黎曼猜想（GRH）下也是如此。

實作

Mike Scott 用 C++ 實現了幾種演算法。這些實作是免費的（無條款、無條件），並使用了在 AGPLv3 授權下分發的 MIRACL 程式庫。

針對質數 p 的 E(\mathbb{F}_p) 的 Schoof 演算法實作。
針對 E(\mathbb{F}_{2^m}) 的 Schoof 演算法實作。

參見

橢圓曲線密碼學
橢圓曲線點計數
除法多項式
弗羅貝尼烏斯自同態

參考文獻