问题标签 [finite-field]

假设我有一个超过 GF(2) 的矩阵，即一个二进制矩阵。现在如何在 2 的有限域上计算给定矩阵的左零空间？

MATLAB 是否为此提供了内置函数？

我一直在研究有限域。假设我有一个素数p=7。所以我得到了一份清单q=[0,1,2,3,4,5,6]。现在我想要集合 q 的元素的所有可能排列7 个位置。例如 [1,1,1,4,6,3,1] 是可能的排列之一。python中是否有任何内置命令可以做到这一点？实际上，我正在与 P 所在的更大领域合作127 (p=127).

我正在使用 gf256 库进行 galois 场数学运算，并将它放在一个 numpy 矩阵中。尽管使用它调用np.linalg.inv()时，它会引发错误。

以上是总结，下面是详细内容：

毕竟，gfarr看起来像这样

并np.linalg.inv(gfarr)抛出此错误

矩阵绝对是可逆的，GF256 类支持所有常用运算符。是否可以使用 numpy 进行这项工作？

OpenSSL 在执行 RSA 时执行模块化归约，但为了最大限度地提高有限域上椭圆曲线的效率，它还需要对那些进行模块化归约。

我很好奇OpenSSL 源代码中的哪个文件OpenSSL 执行这些模块化缩减。我特别感兴趣的是它在哪里处理二进制有限域，但是知道它在哪里处理素数有限域可能会让我深入了解它在哪里处理二进制有限域。

我想使用 NTT 实现多项式的乘法。我遵循数论变换（整数 DFT），它似乎有效。

现在我想在任意素数的有限域Z_p[x]上实现多项式的乘法。p

p与以前的无界情况相比，它是否改变了系数现在以 为界的任何内容？

特别是，原始 NTT 需要找到N大于的工作模数作为工作模数，(magnitude of largest element of input vector)^2 * (length of input vector) + 1以便结果永远不会溢出。如果结果无论如何都会受到那个p素数的限制，那么模数可以有多小？请注意，p - 1不必是 form (some positive integer) * (length of input vector)。

编辑：我从上面的链接中复制粘贴了源代码来说明问题：

印刷：

但是，在我更改minmod = maxval**2 * len(vec0) + 1为 的地方minmod = maxval + 1，它停止工作：

为了按预期工作，最小的minmod（在上面的链接中）是什么？N

我正在使用pyfinte在它使用的 F(2^8) 字段上计算 AES 的乘法，但是当我执行以下操作时：

实际结果是 0xdc 但它应该是 0xda 这是我手动解决的方法：

0xbf*0x03 = 0xbf * 0x02 + 0xbf * 0x01 = 0b10111111 * 0x02 + 0xbf = 0b01111110 + 0x1B + 0xbf = 0b11011010 = 0xda

这是我手独奏的更好格式：

那么哪里错了？是我手动解决的吗？还是在pyfinite？如何解决这个问题？

我正在实现 GF(8) 乘法。原始多项式是 x^3 + x + 1。我知道基础知识：如果乘法溢出，我可以用我的原始多项式对它进行异或运算，并将其带入有限域的范围内。

但是，当溢出发生多于一位时，就会出现问题。例如： 正确结果：二进制结果 12(1001) 中的 alpha^3(011) * alpha^2(100)。乘积溢出，因此与原始多项式进行 XOR 会给出正确的值，即 alpha^5(111)。 不正确的结果：二进制结果中的 alpha^5(111) * alpha^3(011) 21(10101)。这里结果溢出了两位，并且使用原始多项式进行 XOR 不会给出正确的结果。

我错过了什么？

所以目前我正在尝试仅使用多项式来实现有限域。因此，我不想使用 AND 之类的操作对二进制数进行操作。相反，我想用多项式来完成整个事情。

我已经走了很远，有乘法（这里不需要包括），加法等工作。问题是当我对我的素数多项式取模时，我必须将多项式转换为整数来比较它们的大小。我想避免这样做，有没有办法解决这个问题并以不同的方式进行模数？

结果与代码在其当前状态下工作的结果相同，但我需要它以其他方式工作，然后才能继续。

我有一个稀疏的二进制矩阵，我想在二进制字段上分析其属性。该应用程序用于分析一些稀疏的二进制纠错码。矩阵本身太大而无法作为完全密集矩阵处理，大小约为 10,000 x 30,000 或更大，即使只有一小部分条目将被填充。我希望能够在利用矩阵的稀疏性的同时进行二进制线性代数。

我需要做的两件主要事情是：

- 找到其行空间与另一个稀疏矩阵的行空间相交的基

- 找到它的等级

我已经看到有一些包可以找到子空间交集（例如这个 MuPAD 函数）并找到矩阵在不同字段上的等级（例如gfrank），但是对于我正在使用的矩阵来说，它们花费的时间非常长。

有这样的东西吗？或者任何可以用来做到这一点的技巧？如果这在另一种编程语言中也是可能的，那也会有帮助。

对于我当前的项目，我需要能够使用来自 GF(2) 的条目来计算 64*64 矩阵的等级。我想知道是否有人有一个好的解决方案。

为此，我一直在使用pyfinite，但由于它是纯 python 实现，因此速度相当慢。我也尝试过对我一直在使用的代码进行 cythonise，但由于依赖 pyfinite 而遇到了问题。

我的下一个想法是在 cython 中编写我自己的课程，但这对于我的需要来说似乎有点矫枉过正。

我需要以下功能

感谢您的任何想法。