我正在尝试除 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 时犯的一些简单错误。
最佳答案
这部分代码似乎有一些错误:
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
关于Python - 多项式除法 GF(2) 域，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16885065/