NTL库中Galois域GF(2^8)的元素表示及算术运算

Question

我是 NTL 库的新手，因为它的 GF2X、GF2E、GF2EX 等。现在，我想在伽罗华域 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.

例如，{53} • {CA} = {01} 在 Rijndael 的字段中，因为

(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，我运行 Visual Studio 2015 on Windows 7. 我已经下载了我需要的东西，但必须构建一个包含所有提供的源文件的库，这将需要一段时间才能弄清楚。但是，根据另一个答案，这应该可以帮助您入门。首先，初始化 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) 多项式系数之间的一些映射。

NTL库中Galois域GF(2^8)的元素表示及算术运算

How to represent the elements of the Galois filed GF(2^8) and perform arithmetic in NTL library

c++

number-theory

ntl

finite-field