时间戳

首页 > 解决方案 > 二进制多项式模 - Python

python - 二进制多项式模 - Python

问题描述

我有二进制多项式，我将其表示为二进制数。例如

a = 0b10011 
b = 0b101

a 是 x^4+x+1，b 是 x^2+1。所以我想要那个

a%b = 2 # 10 as polynomial x

我想问一下，我该怎么做？我认为两个多项式的标准运算 % 不起作用。

标签： pythonmodulopolynomials

解决方案

这是一个简单的想法，给定一个正常的多项式除法例程，您可以创建一个自定义类来表示二元多项式，然后重写 (%) 运算符，可能是这样的：

from math import fabs


def poly_div(p1, p2):
    def degree(poly):
        while poly and poly[-1] == 0:
            poly.pop()
        return len(poly)-1

    p2_degree = degree(p2)
    p1_degree = degree(p1)

    if p2_degree < 0:
        raise ZeroDivisionError

    if p1_degree >= p2_degree:
        q = [0] * p1_degree
        while p1_degree >= p2_degree:
            d = [0]*(p1_degree - p2_degree) + p2
            mult = q[p1_degree - p2_degree] = p1[-1] / float(d[-1])
            d = [coeff*mult for coeff in d]
            p1 = [fabs(p1_c - p2_c) for p1_c, p2_c in zip(p1, d)]
            p1_degree = degree(p1)
        r = p1
    else:
        q = [0]
        r = p1

    return q, r


class BinPoly:

    def __init__(self, poly):
        self.poly = [int(bit) for bit in list(poly)]

    def __mod__(self, other):
        return poly_div(self.poly, other.poly)


if __name__ == '__main__':
    a = BinPoly('10011')
    b = BinPoly('101')
    print(a%b)

如您所见，您正在用字符串构造多项式，调整类以使用二进制数而不应该太难，留给读者作为练习；）

推荐阅读