0

我有一个类正在接收 1 和 0 的列表并执行 GF(2) 有限域算术运算。在我试图让它以多项式格式输入之前，它一直有效。至于在修复正则表达式问题后如何完成有限算术，我正在考虑重载运算符。

parsePolyToListInput(input)在课堂外时，实际的代码可以工作。问题似乎出在正则表达式中，它只会在字符串中出现错误（这是有道理的），但似乎没有使用 self.expr 作为参数进行初始化（这是一个问题）。初始化之前的@staticmethod 试图挽救未绑定的错误，因为它传入了多项式，但这显然是完全错误的。如果您决定查看任何算术运算，只是为了节省您的时间，模逆不起作用（似乎是由于函数中除法的 while 循环的每次迭代后的格式问题以及返回类型是什么） ：

import re

class gf2poly:
    #binary arithemtic on polynomials
    #@staticmethod
    def __init__(self,expr):
        self.expr = expr
        #self.expr = [int(i) for i in expr]
        self.expr = gf2poly.parsePolyToListInput(self.expr)
    def convert(self):  #to clarify the input if necessary
        convertToString = str(self.expr)
        print "expression is %s"%(convertToString)
    def id(self): #returns modulus 2 (1,0,0,1,1,....) for input lists
        return [int(self.expr[i])%2 for i in range(len(self.expr))]
    def listToInt(self):  #converts list to integer for later use
        result = gf2poly.id(self)
        return int(''.join(map(str,result)))
    def prepBinary(a,b):  #converts to base 2 and orders min and max for use
        a = gf2poly.listToInt(a); b = gf2poly.listToInt(b)
        bina = int(str(a),2); binb = int(str(b),2)
        a = min(bina,binb); b = max(bina,binb);
        return a,b
    @staticmethod
    def outFormat(raw):
        raw = str(raw[::-1]); g = [] #reverse binary string for enumeration
        [g.append(i) for i,c in enumerate(raw) if c == '1']
        processed = "x**"+' + x**'.join(map(str, g[::-1]))
        if len(g) == 0: return 0 #return 0 if list empty
        return processed  #returns result in gf(2) polynomial form
    def parsePolyToListInput(poly):
        c = [int(i.group(0)) for i in re.finditer(r'\d+', poly)] #re.finditer returns an iterator
        #m = max(c)
        return [1 if x in c else 0  for x in xrange(max(c), -1, -1)]
        #return d
    def add(self,other): #accepts 2 lists as parameters
        a = gf2poly.listToInt(self); b = gf2poly.listToInt(other)
        bina = int(str(a),2); binb = int(str(b),2)
        m = bina^binb; z = "{0:b}".format(m)
        return z  #returns binary string
    def subtract(self,other):  #basically same as add() but built differently
        result = [self.expr[i] ^ other.expr[i] for i in range(len(max(self.expr,other.expr)))]
        return int(''.join(map(str,result)))
    def multiply(a,b): #a,b are lists like (1,0,1,0,0,1,....)
        a,b = gf2poly.prepBinary(a,b)
        g = []; bitsa = "{0:b}".format(a)
        [g.append((b<<i)*int(bit)) for i,bit in enumerate(bitsa)]
        m = reduce(lambda x,y: x^y,g); z = "{0:b}".format(m)
        return z #returns product of 2 polynomials in gf2
    def divide(a,b): #a,b are lists like (1,0,1,0,0,1,....)
        a,b = gf2poly.prepBinary(a,b)
        bitsa = "{0:b}".format(a); bitsb = "{0:b}".format(b)
        difflen = len(str(bitsb)) - len(str(bitsa))
        c = a<<difflen; q=0
        while difflen >= 0 and b != 0:  #a is divisor, b is dividend, b/a
            q+=1<<difflen; b = b^c  # b/a because of sorting in prep
            lendif = abs(len(str(bin(b))) - len(str(bin(c))))
            c = c>>lendif; difflen -= lendif
        r = "{0:b}".format(b); q = "{0:b}".format(q)
        return r,q #returns r remainder and q quotient in gf2 division
    def remainder(a,b): #separate function for clarity when calling
        r = gf2poly.divide(a,b)[0]; r = int(str(r),2)
        return "{0:b}".format(r)
    def quotient(a,b): #separate function for clarity when calling
        q = gf2poly.divide(a,b)[1]; q = int(str(q),2)
        return "{0:b}".format(q)
    def extendedEuclideanGF2(a,b): # extended euclidean. a,b are GF(2) polynomials in list form
        inita,initb=a,b;  x,prevx=0,1;  y,prevy = 1,0
        while sum(b) != 0:
            q = gf2poly.quotient(a,b);
            q = list(q); q = [int(x) for x in q]
            #q = list(q);
            #q = tuple([int(i) for i in q])
            q = gf2poly(q)
            a,b = b,gf2poly.remainder(a,b);
            #a = map(list, a);
            #b = [list(x) for x in a];
            #a = [int(x) for x in a]; b = [int(x) for x in b];
            b = list(b); b = [int(x) for x in b]
            #b = list(b);
            #b = tuple([int(i) for i in b])
            b = gf2poly(b)
            #x,prevx = (prevx-q*x, x);
            #y,prevy=(prevy-q*y, y)
            print "types  ",type(q),type(a),type(b)
            #q=a//b;  a,b = b,a%b;  x,prevx = (prevx-q*x, x);  y,prevy=(prevy-q*y, y)
        #print("%d * %d + %d * %d = %d" % (inita,prevx,initb,prevy,a))
        return a,prevx,prevy  # returns gcd of (a,b), and factors s and t
    def modular_inverse(a,mod): # where a,mod are GF(2) polynomials in list form
        gcd,s,t = gf2poly.extendedEuclideanGF2(a,mod); mi = gf2poly.remainder(s,mod)
        #gcd,s,t = ext_euc_alg_i(a,mod); mi = s%mod
        if gcd !=1: return False
        #print ("%d * %d mod %d = 1"%(a,mi,mod))
        return mi   # returns modular inverse of a,mod

我通常用这个输入来测试它：

a = x**14 + x**1 + x**0
p1 = gf2poly(a)
b = x**6 + x**2 + x**1
p2 = gf2poly(b)

关于我的代码，您可能会注意到的第一件事是它不是很好。有两个原因：

1) 我写它是为了让第一个版本可以在有限域 GF(2) 中工作，并以多项式格式输出。然后下一个版本应该能够接受多项式输入，并且还执行关键的“模逆”功能，该功能没有按计划工作（这意味着它实际上根本没有工作）。

2) 我正在自学 Python（我实际上是在自学整体编程），因此欢迎来自专业 Python 程序员的任何建设性批评，因为我正试图尽快打破自己的初学者习惯。

编辑：

也许我一直在测试的更多代码将有助于阐明哪些有效，哪些无效：

t1 = [1,1,1]; t2 = [1,0,1]; t3 = [1,1]; t4 = [1, 0, 1, 1, 1, 1, 1]
t5 = [1,1,1,1]; t6 = [1,1,0,1]; t7 = [1,0,1,1,0]
f1 = gf2poly(t1); f2 = gf2poly(t2); f3 = gf2poly(t3); f4 = gf2poly(t4)
f5 = gf2poly(t5);f6 = gf2poly(t6);f7 = gf2poly(t7)
##print "subtract: ",a.subtract(b)
##print "add: ",a.add(b)
##print "multiply: ",gf2poly.multiply(f1,f3)
##print "multiply: ",gf2poly.multiply(f1,f2)
##print "multiply: ",gf2poly.multiply(f3,f4)
##print "degree a: ",a.degree()
##print "degree c: ",c.degree()
##print "divide: ",gf2poly.divide(f1,b)
##print "divide: ",gf2poly.divide(f4,a)
##print "divide: ",gf2poly.divide(f4,f2)
##print "divide: ",gf2poly.divide(f2,a)
##print "***********************************"
##print "quotient: ",gf2poly.quotient(f2,f5)
##print "remainder: ",gf2poly.remainder(f2,f5)
##testq = gf2poly.quotient(f4,f2)
##testr = gf2poly.remainder(f4,f2)
##print "quotient: ",testq,type(testq)
##print "remainder: ",testr,type(testr)
##print "***********************************"
##print "outFormat testp: ",gf2poly.outFormat(testq)
##print "outFormat testr: ",gf2poly.outFormat(testr)
##print "***********************************"
#print "gf2poly.modular_inverse():  ",gf2poly.modular_inverse(f2,f3)
print "p1  ",p1 #,type(f2),type(f3)
#print "parsePolyToListInput   ",gf2poly.parsePolyToListInput(a)
4

1 回答 1

0

您的部分问题是您没有声明self为parsePolyToListInput. 当你调用一个方法时，你调用它的实例被隐式绑定为第一个参数。命名第一个参数self是一种约定，而不是严格的要求 - 实例被绑定到poly，然后您尝试在其上运行正则表达式。

看起来我在这里的设计中有一些混淆，关于类的各个实例的行为以及类级别或模块级别的行为是什么。在 Python 中，将不将类的实例作为参数定义为模块级函数而不是笨拙地硬塞进去是完全可以接受的。 parsePolyToListInput可能是这样的功能之一。

同样，您的add实现有一条评论说它“接受 2 个列表作为参数”。事实上，它将获取一个gf2poly实例作为它的第一个参数——如果您打算进行运算符重载，这可能是正确的，但这意味着第二个参数也应该是一个gf2poly实例。

编辑：是的，您的示例代码显示了类行为和实例行为之间的细分。您的乘法调用应该如下所示：

print "multiply: ",f1.multiply(f3)

或者乘法根本不应该是一种方法：

gfpoly.py:
def multiply(f1, f2):
    a,b = prepBinary(a,b)
    g = []; bitsa = "{0:b}".format(a)
    [g.append((b<<i)*int(bit)) for i,bit in enumerate(bitsa)]
    m = reduce(lambda x,y: x^y,g); z = "{0:b}".format(m)
    return z #returns product of 2 polynomials in gf2

例如，后一种方法是标准math库如何做事。

定义乘法方法的优点是您可以适当地命名它（http://docs.python.org/2/reference/datamodel.html#special-method-names）并将其与*运算符一起使用：

print "multiply: ",f1 *f3
于 2013-06-25T23:48:03.550 回答