python - 在 GF2 中用 python 查找逆多项式

Question

我对 Python 相当陌生，我有一个与多项式相关的问题。让我们在 GF(2) 中得到一个高次多项式，例如:x^n + x^m + ... + 1，其中 n、m 最多可达 10000。我需要找到这个的逆多项式。在 Python 中最快的方法是什么(可能使用 numpy)？

谢谢

Answer 1

您基本上有两个选择:

• 使用sympy.polys.galoistools，Sympy是一个优秀的符号数学Python库。然而，至少根据我的经验，如果多项式的次数非常高(这在纠错编码理论中很常见)，sympy 就会非常慢。

  from sympy.polys.galoistools import gf_gcdex, gf_strip
  
  def gf_inv(a, irr_poly):  # irriducible polynomial 
  
      return gf_gcdex(gf_strip(a), irr_poly, 2 , ZZ)[0]
  

该解决方案适用于所有 GF(2^p) 字段，例如GF(2)/(x^p+1)。

• 如果您的多项式的次数非常高，则 sympy 太慢，您必须开发自己的扩展欧几里得算法例程以及执行该算法所需的所有其他函数。

就我个人而言，因为我必须对 GF(2) 中的多项式求逆(一万次!)，所以我也使用 numpy 开发了 EEA，但仅适用于 GF2[x] 多项式:

def gf2_xgcd(b, a):
"""Perform Extended Euclidean Algorithm over GF2

Given polynomials ``b`` and ``a`` in ``GF(p)[x]``, computes polynomials
``s``, ``t`` and ``h``, such that ``h = gcd(f, g)`` and ``s*b + t*a = h``.
The typical application of EEA is solving polynomial diophantine equations and findining multiplicative inverse.


Parameters
----------
b : ndarray (uint8 or bool) or list
    b polynomial's coefficients.
a : ndarray (uint8 or bool) or list
    a polynomial's coefficients.
Returns
-------
y2 : ndarray of uint8
     s polynomial's coefficients.
x2 : ndarray of uint8
     t polynomial's coefficients.
b : ndarray of uint8
    h polynomial's coefficients.

Notes
-----
Rightmost element in the arrays is the leading coefficient of the polynomial.
In other words, the ordering for the coefficients of the polynomials is like the one used in MATLAB while
in Sympy, for example, the leftmost element is the leading coefficient.

Examples
========

>>> x = np.array([1, 1, 1, 1, 1, 0, 1, 0, 1], dtype="uint8")
>>> y = np.array([1, 0, 1], dtype="uint8")
>>> gf2_xgcd(x,y)
(array([0, 1, 1, 1], dtype=uint8),
 array([1, 1], dtype=uint8),
 array([1], dtype=uint8))

"""

x1 = np.array([1], dtype="uint8")
y0 = np.array([1], dtype="uint8")

x0 = np.array([], dtype="uint8")
y1 = np.array([], dtype="uint8")

while True:

    q, r = gf2_div(b, a)

    b = a

    if not r.any():
        break

    a = r

    if not (q.any() and x1.any()):  # if q is zero or x1 is zero
        x2 = x0
    elif not x0.any():  # if x0 is zero
        x2 = mul(x1, q)
    else:
        mulres = mul(x1, q)

        x2 = gf2_add(x0, mulres)

    if not (q.any() and y1.any()):
        y2 = y0
    elif not y0.any():
        y2 = mul(y1, q)
    else:
        mulres = mul(y1, q)

        y2 = gf2_add(y0, mulres)

    # update
    y0 = y1
    x0 = x1
    y1 = y2
    x1 = x2

return y2, x2, b

当然，要执行 EEA，首先需要定义允许在 GF2[x 上执行加法、乘法和除法的函数] 字段。

事实上，我已经开发了一个python模块，可以在GitHub中找到:pyGF2它可以在 GF2[x] 上有效地计算多项式算术，包括比 Sympy 快几个数量级的多项式求逆。这里的 EEA 代码直接取自该存储库。