如何表示Galois域GF(2^8)的元素并在NTL库中执行算术

Question

我是NTL库的GF2X、GF2E、GF2EX等的新手。现在，我想对Galois域GF(2^8)执行乘法。问题如下：

Rijndael (standardised as AES) uses the characteristic 2 finite field with 256 elements, 
which can also be called the Galois field GF(2^8). 
It employs the following reducing polynomial for multiplication:
x^8 + x^4 + x^3 + x^1 + 1.

例如，Rijndael字段中的｛53｝•｛CA｝=｛01｝，因为

(x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x)
= (x^13 + x^12 + x^9 + x^7) + (x^11 + x^10 + x^7 + x^5) + (x^8 + x^7 + x^4 + x^2) + (x^7 + x^6 + x^3 + x)
= x^13 + x^12 + x^9 + x^11 + x^10 + x^5 + x^8 + x^4 + x^2 + x^6 + x^3 + x
= x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x
and
x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x modulo x^8 + x^4 + x^3 + x^1 + 1
=   (11111101111110 mod 100011011)
=   {3F7E mod 11B} = {01}
=   1 (decimal)

我的问题是如何在NTL中表示归约多项式x^8 + x^4 + x^3 + x^1 + 1以及多项式x^6 + x^4 + x + 1和x^7 + x^6 + x^3 + x。然后对这些多项式进行乘法运算，得到结果{01}。

这是我使用这个图书馆的一个很好的例子。

Answer 1

再说一次，我不知道NTL，我在Windows 7上运行Visual Studio 2015。我已经下载了我需要的东西，但必须用提供的所有源文件构建一个库，这需要一段时间才能弄清楚。然而，根据另一个答案，这应该会让你开始。首先，初始化GF(256(的归约多项式：

GF2X P;                      // apparently the length doesn't need to be set
SetCoeff(P, 0, 1);
SetCoeff(P, 1, 1);
SetCoeff(P, 3, 1);
SetCoeff(P, 4, 1);
SetCoeff(P, 8, 1);
GF2E::init(P);

接下来，将变量指定为多项式：

GF2X A;
SetCoeff(A, 0, 1);
SetCoeff(A, 1, 1);
SetCoeff(A, 4, 1);
SetCoeff(A, 6, 1);
GF2X B;
SetCoeff(B, 1, 1);
SetCoeff(B, 3, 1);
SetCoeff(B, 6, 1);
SetCoeff(B, 7, 1);
GF2X C;

看起来乘法有一个覆盖，所以假设乘法覆盖基于GF(2^8(扩展字段GF2E:：init(p(，这将起作用。

C = A * B:

---

正如问题后所评论的，NTL更倾向于大字段。对于GF(256(，使用字节和查找表会更快。对于高达GF(2^64(，具有无进位乘法的xmm寄存器内部函数(PCLMULQDQ(可以用于在没有表的情况下快速实现有限域数学(需要一些常数，多项式及其乘法逆(。对于大于GF(2^64(的字段，需要扩展精度的数学方法。对于字段GF(p^n(，其中p！=2和n>1，无符号整数可以与查找表一起使用。构建这些表将涉及整数和GF(p(多项式系数之间的一些映射。