如何優化有限域乘法？

我目前正在嘗試優化有限域乘法 $ \operatorname{GF}(2)[x]/(p) $ ， 在哪裡 $ p = x^8 ⊕ x^7 ⊕ x^6 ⊕ x ⊕1 ∈ \operatorname{GF}(2)[x] $ .

問題是我必須乘以 $ 16,32,133,148,192,194 \ \ and \ \ 251 $ . 實際上，我所做的是聲明包含每個結果的 7 個數組（每個乘法一個；長度為 256）。例如，當我想乘 $ i = 145 $ 到 32 歲，我只是分配 $ array_{16}[i] $ 到結果。

有沒有其他方法來做乘法，例如為了減少我的算法使用的記憶體？

優化程式碼的更好方法是使用乘以 2 的概念（xtime）。

xtime(x) 是乘以 2，它是左移模不可約多項式 ( $ x^8\oplus x^7\oplus x^6\oplus x\oplus1 $ = 0x1C3)

xtime 在 c 程式碼中用不可約多項式 (0x1c3) 實現，如下所示

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3))

• = 加法模 2（程式碼中的異或）

您的值的二進製表示如下：

16 : 00010000

32 : 00100000

133: 10000101

148: 10010100

192: 11000000

194: 11000010

251: 11111011

16*x (mul16) 如下 16 是 $ 2^4 $ （4 次左移）-> mul16(x)=xtime(xtime(xtime(xtime(x))))。它可以從 mul8 重寫為以下xtime(mul8(x))。mul8 被定義為嵌套的三倍時間

32*x (mul32) 如下 32 是 $ 2^5 $ -> mul32(x)=xtime(xtime(xtime(xtime(xtime (x)))))= xtime(mul16(x))。

133x = (128+4+1)x = 128x+ 4*x + x；= ( $ 2^7 + 2^2 +1 $ )x = (mul128(x)^xtime(xtime(x))^x) = (mul128(x)^mul4(x))^x)

192= (128+64)x = mul128(x)^mul64(x) 194= (192+2)x = mul192(x)^xtime(x)

我會讓你做 148 和 251 的乘法，你可以使用下面的程式碼來幫助你：

#include <stdio.h>
#include <stdint.h>

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3)) //P: x8⊕x7⊕x6⊕x⊕1
#define mul4(x)    (xtime(xtime(x)))
#define mul8(x)    (xtime(mul4(x)))
#define mul16(x)   (xtime(mul8(x)))

#define mul32(x)      (xtime(mul16(x)))
#define mul64(x)      (xtime(mul32(x)))
#define mul128(x)     (xtime(mul64(x)))&0xFF
#define mul133(x)  (mul128(x)^xtime(xtime(x))^x)&0xFF
#define mul192(x)  mul128(x)^mul64(x)&0xFF
#define mul194(x)  mul192(x)^xtime(x)&0xFF



uint8_t gmul(uint8_t a, uint8_t b) {
   uint8_t p = 0; /* the product of the multiplication */
   while (a && b) {
           if (b & 1) /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
               p ^= a; /* since we're in GF(2^m), addition is an XOR */

           if (a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
               a = (a << 1) ^ 0x1c3; /* XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
           else
               a <<= 1; /* equivalent to a*2 */
           b >>= 1; /* equivalent to b // 2 */
   }
   return p;
}

int main(){
   // printf("%x\n",mul16(0x06)&0xFF);
   // printf("%x\n",mul32(0x06)&0xFF);


   // printf("%x\n",mul32(0x22)&0xFF);
   // printf("%x\n",gmul(0x22,32)&0xFF);

   printf("---------\n");
   printf("%x\n",mul128(0xf5)&0xFF);
   printf("%x\n",gmul(0xf5,128)&0xFF);

       printf("---------\n");
   printf("%x\n",mul64(0xf5)&0xFF);
   printf("%x\n",gmul(64,0xf5)&0xFF);

       printf("---------\n");
   printf("%x\n",mul192(0x35)&0xFF);
   printf("%x\n",gmul(192,0x35)&0xFF);

       printf("---------\n");
   printf("%x\n",mul133(0x35)&0xFF);
   printf("%x\n",gmul(133,0x35)&0xFF);

           printf("---------\n");
   printf("%x\n",mul194(0xe5)&0xFF);
   printf("%x\n",gmul(194,0xe5)&0xFF);


   return 0;
}

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