Cryptanalysis
GF(2^m) 中多項式的模約簡
我無法理解在 Galois 域上減少過程的硬體中的算法實現 $ F_{2^{163}} $ 在下面的過程中，看起來我們正在計算 $ zc(z) $
2m-2 downto m前半部分的值 $ c(z) $
- 但我不明白什麼是 $ r(z) $ 以及它是如何獲得的？
- $ r(z) $ 不應該固定為 $ Z^m $ 如果它是多項式，它的值是多少，W 是多少？
- 以及過程是怎樣的 $ z^k * r(z) $ 從硬體上看，每個 k 和一個和門只左移 1 $ r(z) $ ?
我不知道這是否可以幫助你，但你知道在二進制算術中，你有： $ f(z)=z^m+r(z) $ ; 然後 $ z^m =f(z)+r(z) $ . 注意：這裡的加法表示按位異或，您可以通過適當的門在硬體中輕鬆表示。然後讓我們繼續檢查您向我們展示的歸約算法： $ c(z)=c_{2.m-2}.z^{2.m-2}+c_{2.m-1}.z^{2.m-1}+\cdots+c_{m}.z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0 $ 我們因式分解 $ z^m $ ; 那麼，我們得到： $ c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0 $ 並更換 $ z^m=f(z)+r(z) $ 並執行歸約 mod f(z)：剩下的是： $ c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).r(z)+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0 $ 可以使用預先計算的表來計算！
另一種解釋 $ r(z) $ 從 $ z^m =1.f(z)+r(z) $ 表明 $ r(z) $ 是除法的餘數 $ z^m $ 經過 $ f(z) $ 而商是常數多項式 1。