问题标签 [galois-field]

我正在尝试对字节执行非线性函数以实现 SAFER+。该算法需要计算以字节为底的 45 对数，我不明白该怎么做。

日志₄₅ (201) = 1.39316393

当我将它分配给一个字节时，该值被截断为 1，我无法恢复确切的结果。

我该怎么处理这个？

我正在尝试在极其有限的嵌入式平台上生成 QR 码。除了生成纠错码字之外，规范中的所有内容似乎都相当简单。我查看了一堆现有的实现，它们都试图实现一堆让我头疼的多项式数学，特别是关于伽罗瓦域。在数学复杂性和内存要求方面，我能看到的最直接的方式是规范本身中列出的电路概念：

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

他们提供以下帮助：

QR 码的多项式算法应使用按位模 2 算法和按字节模 100011101 算法计算。这是一个 2^8 的伽罗瓦域，其中 100011101 表示该域的素数模多项式 x^8+x^4+x^3+x^2+1。

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

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

我在此处的 GCM SP-800-38D 文档中为块乘法（算法 1）提供了 C 代码。第 11-12 页。

完成代码后，我想看看是否有任何方法可以测试代码。您可以在我提供的代码下方找到附件。请注意，我使用 24 位块代替了 128 位块，仅用于测试目的。如有必要，我将不胜感激。

我希望能够计算

其中 g 在有限域 GF(2^m) 中。这里 m 相当大，m = 256、384、512 等，因此查找表不是解决方案。我知道对于类似的想法有非常快速的算法，用于 Z/nZ 的 modpow（参见HAC的第 619-620 页）。

1. 什么是计算周期（即 g^x）的快速、非基于表格的方法？
2. 这绝对是一个一厢情愿的问题，但它来了：蒙哥马利乘法/求幂的想法可以“循环”到伽罗瓦域吗？由于同构属性，我想这样想，但我真的不知道。

备注：这是我在 math.stackoverflow.com 上的帖子我想这是提出这个问题的最佳社区。

Matlab 有一个内置函数，用于计算具有十进制数和有限域数的矩阵的秩。但是，如果我没记错的话，他们只计算最低排名（行排名和列排名最低）。我只想计算行秩，即找到矩阵的独立行数（在我的例子中是有限字段）。有没有功能或方法可以做到这一点？

你知道C++中伽罗瓦域算术的实现吗？至少应该涵盖像 GF(2 ¹⁶ ) 和 GF(2 ^{32 ) 这样的情况。}性能是一个问题，因此实施应该考虑优化其操作。

我更喜欢一个通用的计算库或一个专门用于此任务的小型库。缺少这些，我也欢迎一些可读的源代码。

我正在开发一个在 vba 中生成 QR 码的功能。我正在关注本教程。我现在正在这一步中生成纠错字。这需要 GF(256) 对数/反对数表，参见此处。我真的不想输入整个表格。有谁知道用于生成这些表的函数，所以我可以将它们存储在数组中？该教程有一个指向如何生成表的链接，但它被破坏了。

我应该在前面提到它，但是这将在 access 中运行，因此粘贴到 excel 中效果不佳。但是当我写这篇文章时，我意识到我可以使用访问表。虽然我更愿意在代码中完成这一切。

我试图了解 galois LFSR 代码是如何工作的。在维基百科页面上有一个带有示例的图。有一个 C 代码段。

我无法理解维基百科上给出的数字并与代码相关联。切换蒙版在做什么？任何人都可以解释该操作如何使用示例位序列及其移位版本。我不了解字段，也不了解代码。我在网上查了一下，但如果不进入领域术语，就找不到对该算法的任何好的解释。请帮忙。

我想在 galois 场（GF4）上使用 numpy 数组。所以，我将 GF4 类设置为数组元素。它适用于数组+整数计算，但不适用于数组+数组计算。

但它也适用于数组和数组*整数计算。

我应该如何更正以下代码？我想使用我的类 GF4。

I'm trying to read in a polynomial in GF(2) finite field, which is basically only 1 or 0 for the coefficients or constants and the only number that really differentiates 1 part of polynomial from the other is the exponent. But the exponent ends up only marking the 'place' or index of the location in the resulting list that is then only marked as a 1. Every other position in the resulting list is a 0.

Some code with an example:

So as you can see, this outputs:

But is should output a 1 in the head of the list (polynomial degrees go high-to-low from left-to-right and so should the list). The length is right, since that's the highest degree. I'm teaching myself Python right now, so I'm sure that the pro Python people are cringing at my code. To those who are pro, please feel free to suggest a more Pythonic solution, or anything else constructive as I'm trying to rid myself of all beginner habits as quickly as possible. I'll put this into a function (actually it goes into a function within a class) later, this is just to get the basic idea down.

EDIT:

From the answer below (I'm not taking credit for the idea just some of the code), I made this which seems Pythonic but not sure how to best integrate the code where I extract using regex and convert to int (in the c list):

I'm wondering how to streamline this code and make it more Pythonic.