有限域中算術的複雜性？
我想知道在有限域中加/減和乘/除數的複雜性是什麼 $ \mathbb{F}_q $ . 我需要它來理解我正在閱讀的一篇文章。
讓 $ n = \lceil \log q \rceil $ （和 ” $ \log $ " 是以 2 為底的對數，所以 $ n $ 是大小，以位為單位， $ q $ ).
如果 $ q $ 是一個素數（即 $ \mathbb{F}_q $ 是整數模域 $ q $ )，那麼經典實現將有成本 $ O(n) $ 對於加法和減法， $ O(n^2) $ 用於乘法和除法。乘法的成本可以通過使用Tom-Cook 乘法或快速傅里葉變換（使用快速算法進行最終的模化約簡，我目前不知道它的名字）來漸近降低，降到大約 $ O(n(\log n)^2) $ . 但是，對於密碼學中使用的大小的數字（例如，2048 位整數），這些方法往往不值得付出努力，而普通的蒙哥馬利乘法更快。至少通常的智慧是這樣。每個新的硬體架構都可能挑戰這樣的結果。對於模除法，最快的算法是擴展二進制 GCD算法，它是二次的。
必須注意的是，即使蒙哥馬利的乘法和擴展二進制 GCD 都是成本 $ O(n^2) $ , 實際上，對於相同大小的數字，前者往往比後者快幾十倍，因為蒙哥馬利的乘法可以依賴硬體本機乘法操作碼並按 32 或 64 塊處理位，而二進制 GCD 是逐位算法。
如果 $ q $ 是 2 的冪（ $ q = 2^n $ )，然後是欄位 $ \mathbb{F}_q $ 是通過多項式獲得的商場 $ \mathbb{F}_2[X] $ 模一個給定的不可約多項式 $ P $ . 由於同一基數的所有有限域都是同構的，因此可以選擇多項式 $ P $ 幾乎是空的，即三項式 ( $ P = 1 + X^a + X^n $ ) 或五項式 ( $ P = 1 + X^a + X^b + X^c + X^n $ ）。這允許線性減少模 $ P $ . 在實踐中，乘法將使用Karatsuba 算法完成，複雜度約為 $ O(n^{1.585}) $ .
此外，在二進製欄位中，平方（和提取平方根）可以非常有效地完成， $ O(n) $ 複雜。這就是 Frobenius 內同態，用於加速一種稱為 Koblitz 曲線的特殊橢圓曲線的計算。平方和平方根甚至可以進一步優化以使用普通基變得“自由”，但這會使乘法的效率大大降低，因此在一般情況下這不被認為是淨收益。
除了應用密碼學手冊（尤其是第 2 章和第 14 章）之外，一個很好的參考資料是橢圓曲線密碼學指南的第 2 章，它涵蓋了有限域算術——而且，瞧！該書的第 2 章是“免費樣本”一章，可以從網站上以 PDF 格式下載。
好吧，如果 $ q $ 是素數（而不是 $ p^n $ 和 $ n>1 $ )，然後可以通過做傳統的模運算來執行加減乘 $ q $ ， 那是：
$ a +_{\mathbb{F}_q}b \equiv (a+b) \bmod q $
$ a -_{\mathbb{F}_q}b \equiv (a-b) \bmod q $
$ a \times_{\mathbb{F}_q}b \equiv (a\times b) \bmod q $
這樣，加法和減法可以及時完成 $ O(log(q)) $ ，而乘法通常是及時完成的 $ O(log^2(q)) $ . 現在，有一些漸近更快的乘法/取模方法，但它們通常在 $ q $ 是我們在密碼學實踐中通常看到的；但是，如果您的 $ q $ 是巨大的，使用這些更快的方法是合理的。
棘手的是除法。這不是整數域上的除法，然後是模運算。相反，它涉及找到一個數字的乘法倒數；也就是說，給定 $ b $ ，我們找到欄位成員 $ b^{-1} $ 這樣 $ b \times b^{-1} = 1 $ . 然後， $ a / b = a \times b^{-1} $
乘法逆元通常使用擴展歐幾里得方法找到；一個直接的實現需要 $ O(log^3(q)) $ 時間。同樣，您可以進行一些優化；然而，除法仍然是四種操作中成本最高的（在某種程度上，我們通常安排計算以最小化除法的數量，即使以增加乘法的數量為代價）。