無進位乘法與乘法高飛_(2ķ)GF(2ķ)GF(2^k)

我使用 CLMUL 指令集實現了無進位乘法。這與簡單的模乘法同樣快。但是計算一些多項式的結果仍然很慢。我這樣做：

for (unsigned int i = 32; i-- > 0; )
{
   if (c & (1L << (i + 32)))
   {
       c ^= 1L << (i + 32);
       c ^= (uint64_t)p << i;
   }
}

其中 c 是 64 位無進位乘積， p 是一些不可約多項式 32 位。我不確定該程式碼是否正確。我們可以更快地做到這一點嗎？

如果我是對的，我們在計算乘積後仍然必須執行這個相當昂貴的過程，那麼我開始懷疑僅進行 mod 進行無進位乘法是否合理 $ 2^k $ . 是否進行無進位乘法模式 $ 2^k $ 本身也具有與無進位乘法模多項式類似的優點？

它可能是恆定的時間，但它是均勻分佈的嗎？一般來說，無進位乘法是乘法的合理替代方案 $ GF(2^k) $ ?

首先，您的程式碼對於乘法幾乎是正確的 $ GF(2^{32}) $ 前提是 $ p $ 表示單項式的位係數 $ x^{31},x^{30},\ldots,x^2,x,1 $ 在 32 次不可約多項式中。有一個圍欄問題 $ i $ 應該從 31 下降到 0。

現在，無進位乘法模型 $ 2^k $ 不對應於欄位中的乘法，而是對應於環 $ \mathbb Z[x]/x^k\mathbb Z[x] $ . 這不是進行密碼學的好數學對象。例如，輸出的低位只是輸入的低位的函式。通過比較乘法 $ GF(2^k) $ 所有輸出位都是所有輸入位的函式。場乘法的另一個特性是它對於非零輸入是可逆的，但是在我們的環中，對於沒有設置低位的輸入，該函式是不可逆的。

如果我們考慮所有輸入對，那麼輸出不是均勻分佈的。例如，只有 25% 的輸入會產生低位設置的輸出。如果我們固定其中一個輸入並確保設置其低位，則輸出是均勻分佈的，但輸出的低位將僅取決於輸入的低位。簡而言之，這不是一個好的選擇。

就您之前的問題而言，有一些可能的加速。如果您預先計算程式碼 $ c $ 取值 1<<32, 1<<33,…, 1<<63 並將這些值儲存為 $ x[0],\ldots,x[31] $ 然後程式碼可以替換為

for (int i = 31; i-- >= 0; )
{
   if (c & (1L << (i + 32)))
       c ^= x[i];
}
c %= 1<<32;

如果您還想要更快的速度，您可能需要查看表示欄位的替代方法，例如最佳正態基數或Zech 對數

引用自：https://crypto.stackexchange.com/questions/100105