我正在尝试实现一种适用于 Galois Field(3) 的高斯算法。我已经成功地在 GF(2) 上实现了该算法，但 GF(3) 似乎有点棘手。我的主要问题是：当我选择的枢轴线的值为 2 (pl = 2) 时，如何消除列中的 2？我的第一个想法是将 pl/2 添加到 2，但在 GF(3) 中，我不确定 2/2 = 1。
问问题
418 次
2 回答
1
2/2 == 1 总是，因为 1 是乘法的中性元素。
但是，在有限域中，不能确定 2 是唯一导致 1 的 2 的除数。
通常，只需使用乘法而不是除法即可达到 1；容易多了！
于 2016-04-17T17:54:03.957 回答
0
要消除域 中的枢轴a = 2，GF(3)您需要在伽罗瓦域中找到 2 的乘法逆元，这样a * a_inv = 1在 中GF(3)。所以除以a，你将乘以a_inv（mod 3）。恰好是那个a_inv = 2，但不是因为那个2/2 = 1（这是不正确的）。例如，在GF(5)2 的倒数中是 3，而不是 2。
在素数域中找到元素的逆的方法GF(p)是使用扩展欧几里得算法。该算法找到整数d, s, t，使得d = a*s + b*t = gcd(a, b). GF(p)对于求元素 逆的素数域a，您计算1 = a*s + p*t = gcd(a, p)和a_inv = s。GCD 始终为 1，因为p它是素数。
我编写了一个 Python 包galois，它在 Galois 字段上扩展了 NumPy 数组。它还包括用于计算扩展欧几里得算法等的函数。以下是使用galois.
手动求 2 的倒数GF(3)。
In [1]: import galois
In [2]: a, p = 2, 3
In [3]: d, s, t = galois.egcd(a, p); d, s, t
Out[3]: (1, -1, 1)
In [4]: a_inv = s % p; a_inv
Out[4]: 2
In [5]: a * a_inv % p
Out[5]: 1
手动求 2 的倒数GF(5)。
In [6]: a, p = 2, 5
In [7]: d, s, t = galois.egcd(a, p); d, s, t
Out[7]: (1, -2, 1)
In [8]: a_inv = s % p; a_inv
Out[8]: 3
In [9]: a * a_inv % p
Out[9]: 1
或者，您可以使用galois创建字段GF(5)，然后按照库的意图直接计算逆。
In [10]: GF = galois.GF(5)
In [11]: GF(2)**-1
Out[11]: GF(3, order=5)
还支持线性代数，包括行缩减（高斯消除），如您所提到的，以及矩阵求逆。
In [19]: import numpy as np
In [20]: GF = galois.GF(3)
In [21]: A = GF.Random((4,4)); A
Out[21]:
GF([[2, 2, 2, 2],
[0, 2, 1, 1],
[0, 1, 0, 1],
[2, 1, 2, 0]], order=3)
In [22]: A.row_reduce()
Out[22]:
GF([[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]], order=3)
In [23]: A_inv = np.linalg.inv(A); A_inv
Out[23]:
GF([[1, 2, 2, 1],
[2, 0, 2, 1],
[1, 1, 0, 2],
[1, 0, 2, 2]], order=3)
In [24]: A @ A_inv
Out[24]:
GF([[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]], order=3)
于 2021-08-11T19:43:08.160 回答