问题标签 [finite-field]

我正在为 Haskell 寻找有限域线性代数库。

像Haskell的 FFLAS-FFPACK这样的东西会很棒:-)。

当然，我检查了hmatrix，似乎对任意矩阵元素类型有一些支持，但我找不到任何与 hmatrix 一起使用的有限域库。当然我会很感激一个高性能的解决方案:-)

特别是我希望能够将_p ^n×1和_p ^1×m矩阵（向量）乘以_{p n} ^×m矩阵。

我正在为 C 寻找一个有限域/伽罗瓦域精确线性代数库（C++ 是不可接受的，因为我需要能够编写一个 Haskell 绑定，而这对于 C++ 来说显然很困难）。

我找到了像FFLAS-FFPACK和Givaro这样的库，但这些是 C++ 模板库:-(

特别是我希望能够将_p ^n×1和_p ^1×m矩阵（向量）乘以_{p n} ^×m矩阵。

那么，有人知道合适的 C 或“extern C”库吗？

PS：这是我关于同一问题的Haskell 问题。

我希望能够计算

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

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

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

一般的

我正在寻找一个能够对大型有限域进行精确计算的库，例如 GF(2 ¹²⁸ )/ _{2 ¹²⁸}和 GF(2 ²⁵⁶ )/ _{2 ²⁵⁶}。我在下面列出了我需要的功能以及很酷的功能。显然，图书馆应该尽可能快:-)。啊，因为我不是 C++ 大师（可能大多数库都是 C++），所以示例代码说生成一个随机元素/一个常数并将其乘以它的乘法逆

必备功能

• 添加字段元素
• 字段元素的乘法
• 求域元素的乘法逆元

很高兴有功能

• 矢量/矩阵支持
• 随机元素支持

我已经看过的库可能不起作用

• FFLAS/FFPACK，似乎不适用于如此大的有限域
• Givaro似乎不适用于如此大的有限域

我已经看过可以工作的库（但我无法使用）

• NTL，我无法反转元素，但它应该真的可以工作，因为SAGE在定义 GF(2^256) 时似乎使用了这个库，并且可以使用反转元素x^(-1)
• PARI/GP，我无法在文档中找到我需要的所有内容，但 SAGE 文档有点说它应该可以工作

其他注意事项

• 我正在编写一个 Haskell 程序，稍后将与该库进行接口，因此更简单的 Haskell 接口会更好:-)

我在 C# 中实现 AES，并且在某些时候（MixColumns 函数）我必须在 GF(2^8) 有限域上乘以两个字节。

所以，我有三个选择：

• 使用 dotNet 具有的默认功能（它有类似的东西吗？）
• 编写一个自定义函数来做到这一点
• 使用查找表

对于自定义函数，我找到了一段 C 代码，我试图为 C# 重写，但它不起作用（我得到错误的结果）。(*)

这是原始的 C 代码（源代码）：

这就是我重写的内容：

我还在这里找到了一些查找表，这似乎是一种简单而好的方法，但我真的不知道如何使用它们，尽管我有预感。(**)

底线：我应该选择哪个选项，以及如何使它起作用，鉴于我上面写的就是我到目前为止所得到的，而且我真的不想深入了解数学知识。

更新：

*)同时我意识到我的 C# 重写代码产生了正确的答案，这只是我的错，因为我在验证它们时搞砸了。

**)这些表可以用作 Byte[256] 数组，比方说，当用作表数组的索引时，它的答案x*3是从 HEX 转换为 DECIMAL。table_3[x]x

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

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

给定一个 m*n 二进制矩阵 A，m*p 二进制矩阵 B，其中 n > m 计算 X 使得 AX=B 的有效算法是什么？

例如：

请注意，当我说二进制矩阵时，我指的是在字段 Z_2 上定义的矩阵，也就是说，所有算术都是模 2。

如果有任何兴趣，这是我在为随机纠错码生成合适的矩阵时面临的问题。

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

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

我需要在 16 位 CPU 上求解有限素数域中的多项式。我见过人们使用这些字段GF((2^16)+1), GF((2^16)-15)，并且GF((2^32)-5). 我猜这些选择源于有几个优化的事实。但是，除了使用“mod”之外，我不知道任何进一步的优化。如果有人向我指出一个好的资源，给我代码片段，或者解释为什么人们使用那些奇怪的素数而不是 say ，我将非常感激GF((2^16)-1)。

编辑：GF（（2 ^ 16）+ 1）中的%-free模：

编辑： GF(2^16-15) 中的 %-free 模数：

更新：我在 MSP430 上测量了一次性能：高版本比低版本快 4 倍。较低的版本与使用 % :/ 一样快。有什么进一步的建议可以加快较低版本的速度吗？

干杯康拉德

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.