計算Fp2Fp2mathbb F_{p^2}-定義的橢圓曲線的有理點FpFpmathbb F_p
如何計算定義的橢圓曲線上的點 $ \mathbb F_p $ ， 例如 $ y^2 \equiv x^3 + 1 \pmod p $ , 座標在 $ \mathbb F_{p^2} $ ? （點可能有復數格式 $ \mathbb F_{p^2} $ )
一般情況是欄位擴展。給定一個欄位 $ \mathbb{F}_q $ 的 $ q $ 元素（在您的情況下，該欄位是 $ \mathbb{Z}p $ , 整數模素數 $ p $ )，您想在欄位中定義和進行計算 $ \mathbb{F}{q^k} $ 的 $ q^k $ 某個整數的元素 $ k > 1 $ . 為此，首先考慮 $ \mathbb{F}_q[X] $ 這是多項式的環，其係數為 $ \mathbb{F}_q $ ：多項式是形式和：
$$ A = \sum_{i=0}^{\infty} a_i X^i $$ 對於某些值 $ a_i $ （“係數”）在該領域 $ \mathbb{F_q} $ , 這樣只有有限數量的 $ a_i $ 區別於 $ 0 $ . 多項式的次數是整數 $ n $ 這樣 $ a_n \neq 0 $ 但 $ a_i = 0 $ 對所有人 $ i > n $ . 多項式可以以自然方式相加和相乘。如果我們定義：
$$ \begin{eqnarray} A &=& \sum_{i=0}^{\infty} a_i X^i \ B &=& \sum_{i=0}^{\infty} b_i X^i \ \end{eqnarray} $$ 那麼總和 $ A $ 和 $ B $ 是： $$ A + B = \sum_{i=0}^{\infty} (a_i+b_i) X^i $$ 產品是： $$ AB = \sum_{i=0}^{\infty} \left(\sum_{j=0}^{i} a_j b_{i-j}\right) X^i $$ 多項式有明確定義的歐幾里得除法：給定多項式 $ A $ 和 $ B $ ， 和 $ B $ 非零（“零多項式”是係數都為零的多項式），則存在唯一多項式 $ Q $ 和 $ R $ 這樣 $ A = BQ + R $ , 和程度 $ R $ 嚴格小於度 $ B $ . （為了使這個定義起作用，我們正式定義零多項式有度 $ -1 $ .)
如果我們可以計算加法和乘法，並且我們有歐幾里得除法，那麼我們可以定義一個模運算：“ $ A $ 模組 $ B $ “是值 $ R $ 在等式中 $ A = BQ + R $ .
現在讓我們選擇一個多項式 $ M $ 學位 $ k $ 在 $ \mathbb{F}q[X] $ . 為了使事情更簡單，我們選擇一個酉多項式，即它的最高非零係數 $ m_k = 1 $ . 然後我們定義 $ \mathbb{F}{q^k} $ 成為的商 $ \mathbb{F}_q[X] $ 經過 $ M $ ：這是一組嚴格小於度數的多項式 $ k $ ，並且所有運算（加法和乘法）都取模 $ M $ . 換句話說，當多項式相加和相乘時，我們按照上面描述的那樣做，附加規則是 $ M $ 為零，即
$$ X^k = \sum_{i=0}^{k-1} -m_i X^i $$ 這定義了一個環。構造的美妙之處在於，如果多項式 $ M $ 是不可約的 $ \mathbb{F}q[X] $ （意味著不存在多項式 $ U $ 和 $ V $ 程度嚴格大於 $ 1 $ 並且嚴格低於 $ k $ 這樣 $ M = UV $ )，那麼那個環就是一個欄位。另一個額外的（和不明顯的）屬性是 $ M $ 實際上並不重要，因為所有領域 $ \mathbb{F}{q^k} $ 彼此同構，即它們描述了相同的內部結構。這就是為什麼我們可以談論“the”領域 $ \mathbb{F}_{q^k} $ .
場 $ \mathbb{F}_{q^k} $ 稱為域擴展 $ \mathbb{F}_q $ 學位 $ k $ . 我們正式映射元素 $ \mathbb{F}q $ 到多項式 $ 0 $ 在 $ \mathbb{F}{q^k} $ ，這讓我們可以說 $ \mathbb{F}q $ 是的一個子集 $ \mathbb{F}{q^k} $ .
在您的特定情況下，讓我們看看上面的內容。你的基礎領域 $ \mathbb{F}_q $ 是 $ \mathbb{Z}_p $ , 整數模素整數 $ p $ . 你想要學位的領域擴展 $ 2 $ ，所以你需要一個不可約多項式 $ M $ 學位 $ 2 $ . 為了使計算更容易，您更喜歡 $ M $ 盡可能“簡單”，即：
$$ M = X^2 + \alpha $$ 和 $ \alpha $ 選擇這樣乘以 $ \alpha $ 很容易。你還需要 $ M $ 是不可約的（因為你想要一個欄位），這意味著 $ -\alpha $ 不能承認任何平方根 $ \mathbb{Z}p $ . 這裡一個很常見的選擇是選擇 $ p $ 這樣 $ p = 3 \pmod 4 $ , 因為那樣我們可以設置 $ \alpha = 1 $ . 如果你這樣做，那麼 $ M = X^2 + 1 $ . 在應用上述規則時，這定義了 $ \mathbb{F}{p^2} $ 包含在多項式中 $ A = a_1X + a_0 $ 對於所有值 $ a_0 $ 和 $ a_1 $ 在 $ \mathbb{Z}_p $ ，並且加法和乘法是“自然地”完成的，額外的規則是 $ X^2 = -1 $ . 如果不是寫 $ X $ 你叫它 $ i $ , 那麼你得到與復數相同的結構 $ \mathbb{C} $ 從實數 $ \mathbb{R} $ ，以及@Cryptostatis 在他的回答中列出的簡單計算規則。值得注意的是，在實施時可能會進行額外的優化：
$$ \begin{eqnarray} (a_0+ia_1)(b_0+ib_1) &=& (a_0b_0 - a_1b_1) + i(a_0b_1 + a_1b0) \ &=& (a_0b_0 - a_1b_1) + i((a_0+a_1)(b_0+b_1) - a_0b_0 - a_1b_1) \end{eqnarray} $$ 也就是說，兩個值的乘積 $ \mathbb{Z}_{p^2} $ , 與模 $ M = X^2+1 $ , 可以只用三個乘法計算 $ \mathbb{Z}_p $ .
有關有限域的更多資訊以及域擴展構造的詳細資訊，非常經典的讀物是Neal Koblitz的數論和密碼學課程。
（根據您的問題，我想您想涉足 Weil 和 Tate 配對；因此，您需要能夠瀏覽一些毛茸茸的數學，而 Koblitz 的書幾乎是必讀的。當您掌握領域擴展，繼續閱讀Ben Lynn 的博士論文，我發現這篇論文對這個主題很有吸引力。）
我提供一個具體的例子。說 $ p=11. $ 你想找到橢圓曲線的點 $ y^2=x^3+1 $ 在有限域上 $ L=GF(p^2). $ 還設置 $ K=GF(p). $ 然後是二次擴展的定義多項式 $ L/K, $ 將是一個不可約的二次多項式 $ K. $ 拿來就夠了 $ f(z)=z^2+7z+2. $ 現在你必須採取每一個元素 $ L $ 作為 $ x- $ 座標和計算 y 座標。例如設置為 $ x- $ 協調 $ x=z. $ 然後我們得到方程 $ y^2=z^3+1. $ 但
$$ z^3+1=z(-7z-2)+1=-7z^2-2z+1=-7(-7z-2)-2z+1= $$ $$ 49z+14-2z+1=47z+15=3z+4. $$ 另一方面 $ (3z)^2=9z^2=9(-7z-2)=-63z-18=3z+4. $ 所以我們得到了點（在投影座標中） $ (z:3z:1),(z:-3z:1)=(z:8z:1). $ 如果你讓 $ x $ 在集合中執行 $ L $ 你會得到所有的分數 $ L $ （有 $ 144 $ 點）。 在 sagemath 中，您可以編寫以下程式碼。
sage:p=11;K.<x>=GF(p**2,'a'); print K.modulus() E1=EllipticCurve(K,[0,0,0,0,1]) E1.points()