该galois库是一个 Python 3 包，它扩展了 NumPy 数组以对有限域进行操作。

用户FieldArray使用GF = galois.GF(p**m). GF是 的子类，np.ndarray其构造函数x = GF(array_like)模仿 . 的签名np.array()。除了所有算术都在 $\mathrm{GF}(p^m)$ 中执行，而不是 $\mathbb{R}$ 之外，它的操作与任何其他 NumPy 数组一样。 FieldArray x

在内部，有限域算法是通过替换NumPy ufuncs来实现的。新的 ufunc 是用纯 Python 编写的，并使用 Numba即时编译。ufunc 可以配置为使用查找表（以提高速度）或显式计算（以节省内存）。

警告 NumPy ufunc 中实现的算法不是恒定时间的，而是为性能而设计的。因此，该库可能容易受到侧信道时序攻击。该库并非用于生产安全，而是用于研发、逆向工程、密码分析、实验和普通教育。

特征

• 支持所有的伽罗瓦域$\mathrm{GF}(p^m)$，甚至是任意大的域！
• 比原生 NumPy更快！GF(x) * GF(y)比(x * y) % p$\mathrm{GF}(p)$ 更快。
• 与 NumPy 无缝集成——正常的 NumPy 函数在FieldArrays上工作。
• np.linalg使用正规函数的有限域上的线性代数。
• 有限域上的线性变换，例如带有 的 FFT 和带有np.fft.fft()的 NTT ntt()。
• 生成不可约多项式、原始多项式和康威多项式的函数。
• 具有 的有限域上的单变量多项式Poly。
• 前向纠错码BCH和ReedSolomon。
• FLFSRFibonacci 和 Galois 线性反馈移位寄存器在任何具有和的有限域上GLFSR。
• 各种数论函数。
• 整数分解和伴随的算法。
• 素数生成和素性检验。

路线图

• 有限域上的椭圆曲线
• 伽罗瓦环阵列
• 显卡支持

文档

的文档galois位于https://mhostetter.github.io/galois/latest/。

入门

入门指南旨在帮助用户安装库、创建两个示例数组和执行基本的数组算术。有关更详细的讨论和示例，请参阅基本用法 。

安装包

galois可以从PyPI使用pip.

$ python3 -m pip install galois

galois在 Python 中导入包。

In [1]: import galois

In [2]: galois.__version__
Out[2]: '0.1.1'

创建一个FieldArray子类

接下来，FieldArray为您想要工作的特定有限域创建一个子类。这是使用galois.GF()类工厂创建的。在这个例子中，我们在 $\mathrm{GF}(3^5)$ 中工作。

In [3]: GF = galois.GF(3**5)

In [4]: print(GF.properties)
Galois Field:
  name: GF(3^5)
  characteristic: 3
  degree: 5
  order: 243
  irreducible_poly: x^5 + 2x + 1
  is_primitive_poly: True
  primitive_element: x

FieldArray子类GF是 np.ndarray在伽罗瓦域 $\mathrm{GF}(3^5)$ 中执行所有算术运算的子类，而不是在 $\mathbb{R}$ 中。

In [5]: issubclass(GF, galois.FieldArray)
Out[5]: True

In [6]: issubclass(GF, np.ndarray)
Out[6]: True

有关详细信息，请参阅数组类。

创建两个FieldArray实例

接下来，通过将 对象传递给的构造函数来创建一个新对象。FieldArray xArrayLikeGF

In [7]: x = GF([236, 87, 38, 112]); x
Out[7]: GF([236,  87,  38, 112], order=3^5)

该数组x是 的一个实例，FieldArray也是 的一个实例np.ndarray。

In [8]: isinstance(x, galois.FieldArray)
Out[8]: True

In [9]: isinstance(x, np.ndarray)
Out[9]: True

通过调用. 在有限域中完成工作后，将其作为带有.FieldArray y.view().view(np.ndarray)

# y represents an array created elsewhere in the code
In [10]: y = np.array([109, 17, 108, 224]); y
Out[10]: array([109,  17, 108, 224])

In [11]: y = y.view(GF); y
Out[11]: GF([109,  17, 108, 224], order=3^5)

有关更多详细信息，请参阅阵列创建。

更改元素表示

有限域元素的显示表示可以设置为整数 ( "int")、多项式 ( "poly") 或幂 ( "power") 表示。默认表示是整数表示，因为在使用整数 NumPy 数组时这是很自然的。

通过将display关键字参数传递给galois.GF()或调用display()类方法来设置显示模式。选择最适合您的元素表示。

# The default representation is the integer representation
In [12]: x
Out[12]: GF([236,  87,  38, 112], order=3^5)

In [13]: GF.display("poly"); x
Out[13]: 
GF([2α^4 + 2α^3 + 2α^2 + 2,               α^4 + 2α,
             α^3 + α^2 + 2,      α^4 + α^3 + α + 1], order=3^5)

In [14]: GF.display("power"); x
Out[14]: GF([α^204,  α^16, α^230,  α^34], order=3^5)

# Reset to the integer representation
In [15]: GF.display("int");

有关详细信息，请参阅元素表示。

执行数组算术

一旦你有两个伽罗瓦域数组，几乎任何算术运算都可以使用普通的 NumPy 算术来执行。传统的NumPy 广播规则适用。

标准的逐元素数组算术——加法、减法、乘法和除法——很容易执行。

In [16]: x + y
Out[16]: GF([ 18,  95, 146,   0], order=3^5)

In [17]: x - y
Out[17]: GF([127, 100, 173, 224], order=3^5)

In [18]: x * y
Out[18]: GF([ 21, 241, 179,  82], order=3^5)

In [19]: x / y
Out[19]: GF([ 67,  47, 192,   2], order=3^5)

还支持更复杂的算术，如平方根和对数底 $\alpha$。

In [20]: np.sqrt(x)
Out[20]: GF([ 51, 135,  40,  16], order=3^5)

In [21]: np.log(x)
Out[21]: array([204,  16, 230,  34])

有关详细信息，请参阅数组算术。

致谢

该galois库是 NumPy 的扩展，并且完全依赖于NumPy。它还严重依赖Numba和LLVM 即时编译器来优化有限域算术的性能。

在可能的情况下， Frank Luebeck 的Conway 多项式汇编和 Wolfram 的原始多项式汇编用于高效的多项式查找。

Sage广泛用于生成有限域算术和多项式算术的测试向量。 SymPy用于生成一些测试向量。Octave 用于生成前向纠错码的测试向量。

如果没有提到的所有其他库，这个库是不可能的。感谢他们所有的开发者！

引文

如果这个库对您的研究有用，请引用我们。遵循GitHub 引用标准，这里是推荐的引用。

中文提供

@software{Hostetter_Galois_2020,
    title = {{Galois: A performant NumPy extension for Galois fields}},
    author = {Hostetter, Matt},
    month = {11},
    year = {2020},
    url = {https://github.com/mhostetter/galois},
}

APA

Hostetter, M. (2020). Galois: A performant NumPy extension for Galois fields [Computer software]. https://github.com/mhostetter/galois