Python多项式除GF（2）域

Question

我试着在GF（2）域中划分多项式。 http://en.wikipedia.org/wiki/Finite_field_arithmetichttp://en.wikipedia.org/wiki/GF(2)

看起来整个除法过程都很顺利，但问题是我一直坚持到它应该停止的地方。异或用于减法，如果你检查变量b，它应该在某个点保持右余数值，但是它会继续。在

class binary1polynomials:
    #binary arithemtic on polynomials
    def __init__(self,expr):
        self.expr = expr
    def degree(self):
        return len(self.expr)
    def id(self):
        return [self.expr[i]%2 for i in range(len(self.expr))]
    def listToInt(self):
        #return int(reduce(lambda x,y: x+str(y), self.expr, ''))
        result = binary1polynomials.id(self)
        return int(''.join(map(str,result)))
    def divide(a,b): #a,b are lists like (1,0,1,0,0,1,....)
        a = binary1polynomials.listToInt(a); b = binary1polynomials.listToInt(b)
        print "a,b,type(a)  ",a,b,type(a)
        bina = int(str(a),2); binb = int(str(b),2)
        a = min(bina,binb); b = max(bina,binb);
        print "a,b  ",a,b
        g = []; bitsa = "{0:b}".format(a); bitsb = "{0:b}".format(b)
        difflen = len(str(bitsb)) - len(str(bitsa))
        print "difflen,bitsa,bitsb,type(bitsa)  ",difflen,bitsa,bitsb,type(bitsa)
        print "a,b  ",a,b
        c = a<<difflen
        print "a,b,c  ",a,b,c
        #for bit in range(difflen):
        #for i,bit in enumerate(bitsa): #'bitsa' must be an integer base 2 before passing in
        while difflen > 0 or b != 0:
            print "A.  b,c  ",bin(b),bin(c)
            b = b^c #,a*int(bitsa[bit])
            lendif = abs(len(str(bin(b))) - len(str(bin(c))))
            c = c>>lendif
            difflen = difflen - 1
            print "B.  b,c,lendif  ",bin(b),bin(c),lendif#,int(bitsa[bit])
        z = "{0:b}".format(b)
        return z


j = (1,1,1,1);h = (1,1,0,1);k = (1,0,1,1,0);t1 = (1,1,1); t2 = (1,0,1)
t3 = (1,1); t4 = (1, 0, 1, 1, 1, 1, 1)
a = binary1polynomials(j);b = binary1polynomials(h);c = binary1polynomials(k)
f1 = binary1polynomials(t1); f2 = binary1polynomials(t2)
f3 = binary1polynomials(t3); f4 = binary1polynomials(t4)
print "divide: ",binary1polynomials.divide(f1,b)
print "divide: ",binary1polynomials.divide(f4,a)
print "divide: ",binary1polynomials.divide(f4,f2)
print "divide: ",binary1polynomials.divide(f2,a)

从这个输出来看，它似乎在某个时刻（每次）都能得到正确的答案，但之后就直接过去了。在

^{pr2}$

这可能是我在自学Python时犯的一个简单的错误。在

Answer 1

这部分代码似乎有一些错误：

while difflen > 0 or b != 0:
        b = b^c 
        lendif = abs(len(str(bin(b))) - len(str(bin(c))))
        c = c>>lendif
        difflen = difflen - 1

你看起来像是把b除以a，其中c等于a左移，以便最有效的位在同一位置。在

问题1

当b为非零时，此循环永远不会终止；当它终止时，答案b始终为零。在

修复：

^{pr2}$

问题2

如果在一次迭代中删除多个位，lendif>；1和c的右移可能比左移的多。在

修复：

  difflen -= lendif

问题3

您没有执行最终迭代。代码正在计算一个多项式相对于另一个多项式的模，所以除法（101101）应该是0。（函数的更好名称可能是模数，而不是除法，因为返回的是余数而不是商）。您的代码当前发现difflen=0，因此跳过while循环。在

修复：

  while difflen >= 0 and b != 0:

最终代码

while difflen >= 0 and b != 0:
        b = b^c 
        lendif = abs(len(str(bin(b))) - len(str(bin(c))))
        c = c>>lendif
        difflen -= lendif