Python - 多项式除法 GF(2) 域

Question

我正在尝试除 GF(2) 域中的多项式。 http://en.wikipedia.org/wiki/Finite_field_arithmetic http://en.wikipedia.org/wiki/GF(2)

看起来我的整个除法序列进展顺利，但我非常困惑的问题是它一直持续到应该停止的点。 XOR 用于减法，如果您检查变量 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)

从这个输出中，它似乎在某个时刻(每次)得到了正确的答案，但随后就直接过去了。

*** Remote Interpreter Reinitialized  ***
>>> 
divide:  a,b,type(a)   111 1101 <type 'int'>
a,b   7 13
difflen,bitsa,bitsb,type(bitsa)   1 111 1101 <type 'str'>
a,b   7 13
a,b,c   7 13 14
A.  b,c   0b1101 0b1110
B.  b,c,lendif   0b11 0b11 2
A.  b,c   0b11 0b11
B.  b,c,lendif   0b0 0b1 1
g   []
0
divide:  a,b,type(a)   1011111 1111 <type 'int'>
a,b   15 95
difflen,bitsa,bitsb,type(bitsa)   3 1111 1011111 <type 'str'>
a,b   15 95
a,b,c   15 95 120
A.  b,c   0b1011111 0b1111000
B.  b,c,lendif   0b100111 0b111100 1
A.  b,c   0b100111 0b111100
B.  b,c,lendif   0b11011 0b11110 1
A.  b,c   0b11011 0b11110
B.  b,c,lendif   0b101 0b111 2
A.  b,c   0b101 0b111
B.  b,c,lendif   0b10 0b11 1
A.  b,c   0b10 0b11
B.  b,c,lendif   0b1 0b1 1
A.  b,c   0b1 0b1
B.  b,c,lendif   0b0 0b1 0
g   []
0
divide:  a,b,type(a)   1011111 101 <type 'int'>
a,b   5 95
difflen,bitsa,bitsb,type(bitsa)   4 101 1011111 <type 'str'>
a,b   5 95
a,b,c   5 95 80
A.  b,c   0b1011111 0b1010000
B.  b,c,lendif   0b1111 0b1010 3
A.  b,c   0b1111 0b1010
B.  b,c,lendif   0b101 0b101 1
A.  b,c   0b101 0b101
B.  b,c,lendif   0b0 0b1 2
A.  b,c   0b0 0b1
B.  b,c,lendif   0b1 0b1 0
A.  b,c   0b1 0b1
B.  b,c,lendif   0b0 0b1 0
g   []
0
divide:  a,b,type(a)   101 1111 <type 'int'>
a,b   5 15
difflen,bitsa,bitsb,type(bitsa)   1 101 1111 <type 'str'>
a,b   5 15
a,b,c   5 15 10
A.  b,c   0b1111 0b1010
B.  b,c,lendif   0b101 0b101 1
A.  b,c   0b101 0b101
B.  b,c,lendif   0b0 0b1 2
g   []
0

这可能是我在自学 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 等于左移，以便最高有效位位于同一位置。

问题 1

当 b 不为零时，该循环永远不会终止 => 当它终止时，答案 b 始终为零。

修复:

 while difflen > 0 and b != 0:

问题2

如果在单次迭代中删除多个位，lendif>1 和 c 向右移动的位数可能多于向左移动的位数。

修复:

  difflen -= lendif

问题3

您没有执行最终迭代。该代码正在计算一个多项式相对于另一个多项式的模，因此divide(101,101)应该为0。(该函数的更好名称可能是modulus而不是divide，因为您返回的是余数而不是商)。您的代码当前发现 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