math - 伽罗瓦域中的加法和乘法

Question

我正在尝试在极其有限的嵌入式平台上生成二维码。一切尽在 the specification除了生成纠错码字之外，看起来相当简单。我研究了一堆现有的实现，它们都试图实现一堆直接超出我头脑的多项式数学，特别是关于伽罗瓦域。我能看到的最直接的方法，无论是在数学复杂性还是在内存要求方面，都是规范本身中列出的电路概念:

根据他们的描述，我相当有信心可以实现这一点，除了标记为 GF(256) 加法和 GF(256) 乘法的部分之外。

他们提供以下帮助:

The polynomial arithmetic for QR Code shall be calculated using bit-wise modulo 2 arithmetic and byte-wise modulo 100011101 arithmetic. This is a Galois field of 2^8 with 100011101 representing the field's prime modulus polynomial x^8+x^4+x^3+x^2+1.

这对我来说几乎都是希腊语。

所以我的问题是:在这种伽罗瓦域算术中执行加法和乘法的最简单方法是什么？假设两个输入数字都是 8 位宽，并且我的输出也需要是 8 位宽。一些实现会预先计算，或在两个查找表中进行硬编码以帮助解决此问题，但我不确定这些是如何计算的，或者在这种情况下如何使用它们。我宁愿不为这两个表占用 512 字节内存，但这实际上取决于替代方案。我真的只需要帮助了解如何在该电路中进行单个乘法和加法运算。

Answer 1

实际上只需要一张表。这适用于 GP(256) 乘法。请注意，所有算术都是无进位的，这意味着没有进位传播。

不带进位的加法和减法相当于异或。

因此，在 GF(256) 中，a + b 和 a - b 都相当于 a xor b。

GF(256) 乘法也是无进位乘法，并且可以使用无进位乘法以与无进位加法/减法类似的方式完成。这可以通过硬件支持(例如 Intel's CLMUL instruction set)有效地完成。 .

然而，困难的部分是减少模100011101。在正常的整数除法中，您可以使用一系列比较/减法步骤来完成此操作。在 GF(256) 中，您可以使用一系列比较/异或步骤以几乎相同的方式完成此操作。

事实上，如果预先计算所有 256 x 256 乘法并将它们放入 65536 项查找表中，速度仍然更快，这已经够糟糕的了。

以下 pdf 的第 3 页对 GF256 算法有很好的引用:

http://www.eecs.harvard.edu/~michaelm/CS222/eccnotes.pdf