在 GF2 中查找 python 中的反多项式

Question

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

谢谢

Answer 1

尝试使用numpy.polyval()。

它计算特定值的多项式。

In [1]: p = np.poly1d([1, 1, -10])  # Use a poly1d to represent the polynomial.

In [2]: y = 100

In [3]: (p - y).roots
Out[4]: array([-11.,  10.])

Numpy 是您正在搜索的库

Answer 2

尝试使用数学包sage

Answer 3

你基本上有两个选项：

使用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) 字段，例如生长因子 (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 代码直接取自那个 repo。

在 GF2 中查找 python 中的反多项式

Find inverse polynomial in python in GF2

python

numpy

inverse

scipy

polynomials