精确的大有限域线性代数库（例如GF（2 ^ 128）/ GF（2 ^ 256））

Question

通用

我正在寻找一种能够在大的有限域（如GF(2¹²⁸)/_2¹²⁸和GF(2²⁵⁶)/_2²⁵⁶）上进行精确计算的库。下面列出了我需要的功能以及希望有的功能。显然，该库应尽可能快。由于我不是C++专家（而且可能大多数库都是C++的），因此需要示例代码，例如生成随机元素/常量并将其与它的乘法逆元相乘。

必备功能

• 有限域元素的加法
• 有限域元素的乘法
• 查找有限域元素的乘法逆元

希望具备的功能

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

我已经查看过但可能无法使用的库

• FFLAS/FFPACK，似乎无法处理这么大的有限域
• Givaro，似乎无法在这么大的有限域上运行

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

• NTL，我无法求出一个元素的逆元，但它应该真的可以工作，因为SAGE在定义GF(2^256)时似乎使用了这个库，在那里可以使用x^(-1)求出元素的逆元

PARI/GP，我在文档中找不到所需内容，但SAGE文档似乎说它应该可以工作。

其他注释

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

- Johannes Weiss

---

你有没有研究过SAGE（http://www.sagemath.org/）？我相信它具备那种功能。 - Qnan

它还有一个Python接口，与C++相比（可以说）更加愉悦 :) - Qnan

@Qnan 烦人的乘法逆元在有限域中似乎会引发NotImplementedError。尽管可以自己实现扩展欧几里得算法。 - cmh

你刚才看了一下http://en.wikipedia.org/wiki/Finite_field_arithmetic 吗？那里有一个指向c++库的链接http://www.partow.net/projects/galois/index.html，但我不确定它的质量和效率。 - aka.nice

如果您完成了Haskell程序，您能分享它吗？ - hola

Answer 1

NTL库似乎可以正常工作，使用以下代码（抱歉我不太会用C++编程）

#include <NTL/GF2E.h>
#include <NTL/GF2EX.h>
#include <NTL/GF2X.h>
#include <NTL/GF2XFactoring.h>

NTL_CLIENT

int main()
{
    GF2X P = BuildIrred_GF2X(256);
    GF2E::init(P);

    GF2E zero = GF2E::zero();
    GF2E one;
    GF2E r = random_GF2E();
    GF2E r2 = random_GF2E();
    conv(one, 1L);
    cout << "Cardinality: " << GF2E::cardinality() << endl;
    cout << "ZERO: " << zero << " --> " << IsZero(zero) << endl;
    cout << "ONE:  " << one  << " --> " << IsOne(one)   << endl;
    cout << "1/r:  " << 1/r  << ", r * (1/r): " << (r * (1/r)) << endl;
    cout << "1/r2:  " << 1/r2  << ", r2 * (1/r2): " << (r2 * (1/r2)) << endl;
}

看起来它能够运行，证明（这个程序的输出）：

Cardinality: 115792089237316195423570985008687907853269984665640564039457584007913129639936
ZERO: [] --> 1
ONE:  [1] --> 1
1/r:  [0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1], r * (1/r): [1]
1/r2:  [1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1], r2 * (1/r2): [1]

即使反转也似乎是有效的（在上面的输出示例中向右滚动尽可能远）:-)

- Johannes Weiss