在 GF(2^n) 中應用蒙哥馬利乘法的地方
我正在為幾個多項式優化 Reed Solomon 解碼庫 $ \operatorname{GF}(2^k) $ , $ k\in{8,10,12} $ .
從 Çetin K. Koç 和 Tolga Acar 的蒙哥馬利乘法中閱讀蒙哥馬利乘法 $ \operatorname{GF}(2^k) $ （在Designs, Codes and Cryptography, 1998中），我想知道該方法是否以及如何在進位自由乘法後幫助減少多項式。
- $ t(x) = a(x)b(x) $ 是來自無進位乘法的全長 (2k-1) 多項式
- $ u(x) = t(x)n’(x) \bmod r(x) $ 返回下半部分 $ \operatorname{GF} $ 乘法
- $ (u(x)n(x) + t(x)) / r(x) $ 對應於一個的上半部分 $ \operatorname{GF} $ 乘法和一個XOR
而不是計算 $ a(x)b(x) \bmod n(x) $ ， 我現在有了 $ a(x)b(x)r^{-1}(x) \bmod n(x) $ ，並且只有一個地方我可以想像使用它。在模冪求逆中，而不是計算 $ a(x)^{254} $ , 我可以計算 $ (a(x)r^{-1}(x))^{254} $ 並乘以一個常數 $ r^{254}(x) $ .
但它可以用於例如多項式評估（例如用於校正子計算）或用於模減少之後 $ \operatorname{GF} $ 乘法？
使用蒙哥馬利乘法的通常動機是它通過改變元素的表示來顯著降低模約簡的成本。在蒙哥馬利環中，多項式 $ A(x) $ 而是由 $ a(x)=A(x)r(x)\pmod{n(x)} $ 在哪裡 $ r(x) $ 是同階的固定元素 $ n(x) $ ，但對於哪個除法非常有效（例如 $ x^k $ ）。如果同樣我們有 $ B(x) $ 代表為 $ b(x)=B(x)r(x) $ 然後 $ a(x)b(x)r^{-1}(x)\equiv A(x)B(x)r(x)\pmod{n(x)} $ 這是我們會選擇的表示 $ A(x)B(x) $ 因此，您的算法是在此表示中實現多項式模乘的方法，而無需進行模約簡。加法和減法不需要新的算法。如果您有一個涉及許多模乘的算法，則值得將其轉換為蒙哥馬利環表示，使用蒙哥馬利算術，然後再轉換回來。
轉換 $ a(x) $ 回到 $ A(x) $ 我們需要乘以 $ r^{-1}(x) $ ，因此預先計算和保存可能很有用 $ r^{-1}(x)\pmod{n(x)} $ . 我不知道有什麼方法可以避免最終轉換中的模組化減少。
使用蒙哥馬利表示進行評估是可能的，但需要一些額外的工作：評估 $ A(x)\pmod{n(x)} $ 鑑於其代表性 $ a(x) $ 我們必須評估 $ a(x)\pmod{n(x)} $ 和 $ r^{-1}(x)\pmod{n(x)} $ 並將兩個答案相乘。但是，如果同一輸入需要多次評估 $ m $ ， 價值 $ r^{-1}(m) $ 可以重複使用，成本也不大。
在哪裡應用蒙哥馬利乘法 $ GF(2^n) $ ?
這個答案真的取決於你如何建構二進制擴展欄位 $ GF(2^n) $ . 如果不可約多項式是三項式或五項式，那麼歸約已經是有效的了！
三項式模乘法
讓 $ GF(2^n) $ 用三項式構造 $ P(x)=x^m+x^n+1 $ 在哪裡 $ \alpha $ 是這個多項式的根 $ 1<n<m/2 $ .
現在你想計算 $ C’(x) = C(x) \bmod P(x) $ 在哪裡
$$ C(x) = A(x)\cdot B(x) = \left( \sum_{i=0}^{m-1} a_i x^i \right)
\cdot \left( \sum_{i=0}^{m-1} b_i x^i \right) $$為了降低乘法成本，請使用 Karatsuba-Ofman 乘數。這可能需要一些調整，因為它具有遞歸性質，並且跳到最後可能不是最佳選擇。
現在，一旦你有一個$$ C(x) = \sum_{i=0}^{2m-2} c_i x^i $$你需要減少。我們可以使用 $ P(\alpha)=0 $ ， 和寫
$$ \begin{align} \alpha^m &= 1 + \alpha^n\ \alpha^{m+1} &= \alpha + \alpha^{n+1}\ \vdots & \quad \vdots\ \alpha^{2m-3} &= \alpha^{m-3} + \alpha^{m+n-3}\ \alpha^{2m-2} &= \alpha^{m-2} + \alpha^{m+n-2}\ \end{align} $$
通過使用這個我們可以說
$$ \begin{align} c’0 &= c_0 + c_m\ c’1 &= c_1 + c{m+1}\ \vdots ;;& \quad \vdots\ c’{n-1} &= c_{n-1} + c_{m+n-1} + c_{m+n-1}\ c’{n} &= c{n} + c_{m+n} + c_{m+n}\ c’{n+1} &= c{n+1} + c_{m+n+1} +c_{m+n+1}\ \vdots ;;& \quad \vdots\ c’{m-2} &= c{m-2} + c_{2m-2} + c_{2m-n-2}\ c’{m-1} &= c{m-1} + c_{2m-n-1}\ c’{m} &= c{m-2} + c_{2m-n}\ \vdots ;;& \quad \vdots\ c’{m+n-3} &= c{m+n-3} + c_{2m-3}\ c’{m+n-2} &= c{m+n-2} + c_{2m-2}\ \end{align} $$
如果看一下上面的內容，應該會注意到這些；
- 減少不完全，因為仍有 $ m-n $ 減少。
- 這些操作只是 x-or 和映射。
- 映射實際上是一個循環
乘法的成本只是 $ m^2 $ 大約最多 $ 2m $ 額外的 x 或減少！
當我們回到蒙哥馬利模乘是有成本的 $ 2m^2 $ 乘法和 $ 2m^2-3m-1 $ x 或運算。
具有任意不可約多項式的模乘法
當二進制擴展域有任意不可約多項式時，上表不再有效。然後你可以轉回蒙哥馬利。
請注意，蒙哥馬利模乘法也可以使用 Karatsuba-Ofman 來降低我們在這裡沒有考慮的乘法成本！
一些注意事項：
- 看看蒙哥馬利減少是如何工作的？蒙哥馬利的細節（整數情況，與多項式幾乎相同）
- 如果您需要一個模乘法，那麼您不需要將它們都轉換為它們的蒙哥馬利殘差表示。您可以通過以下方式實現；$$ MonPro(a(x),MontPro(b(x),1)) $$您還可以在模組化平方乘法中使用蒙哥馬利。
- 通常我們在設計時選擇不可約多項式。已經有一個 低權重二元不可約多項式表，由 HP 和方法在 GF(2) 上找到最少項的不可約多項式
- 用冪和模數反演不是一種有效的方法。已經有 Itoh-Tsujii 算法使用 $ t \ll m $ 乘法和 $ m-1 $ 平方。該算法已經擊敗了 Extended-GCD。