Python --- multiplication in GF(2) field

Question

This function is returning unusual values in the list g. It should return 32774, 65548, 1048768 but instead it's values are more like it's treating the entire binary like a big slinky and just moving the LSB's towards the MSB's instead of actually shifting.

Here's the function:

def multiply(a,b): #a,b are values like 1101010001....
    a = min(a,b); b = max(a,b)
    g = []; bitsa = "{0:b}".format(a)  #returns product of 2 polynomials in gf2
    [g.append((b<<i)*int(bit)) for i,bit in enumerate(bitsa)]
    return reduce(lambda x,y: x+y,g)

This is what I'm testing with:

x = int(str(100000000000011),2)
y = int(str(1000110),2)
x1 = int(str(111),2)
y1 = int(str(11),2)
x2 = int(str(0001),2)
y2 = int(str(1111),2)
print "multiply: ",multiply(x,y)
print "multiply: ",multiply(x1,y1)
print "multiply: ",multiply(x2,y2)

Only x1,y1 works right now, the others don't. This is the whole equation for the last input:

      100000000000011
              1000110
---------------------
     100000000000011 
    100000000000011  
100000000000011      
---------------------
100011000000011001010

So as you can see, to get the product, both binaries need to have their indexes checked for 1's and then append based on that. I'm not sure how to fit that part in, and how to do it so it returns the correct value. Trying to understand why x1,y1 works and the others don't.

EDIT:

I just want it to be clear that J0HN's answer appears to be completely accurate and furthermore he caught an error in the online tool that was referenced. From what it appears now, the built-in's are preferential when working with finite field math in this way. Anyone happening across this should definitely consider showing him some vote love for those keen observation skills-to-pay-the-bills.

Answer 1

You've got enumerate wrong. It starts form the MSB, so

for i, bit in enumerate('110'):
     print (i, bit)

would yield (0, 1), (1, 1), (2, 0), not (0, 0), (1, 1), (2, 1).

Aside from that, some style suggestions:

• Please avoid using ; in python. Search for Compound statements on the page
• Use list comprehensions if possible
• Either the comment is wrong, or you forgot to mention that you multiply operates on lists. If former - remove it, it's very confusing. If latter - your existing code wont work at all as there are no << operator defined on lists.

So, multiply better written and fixed:

def multiply(a,b):
    bitsa = reversed("{0:b}".format(a))
    g = [(b<<i)*int(bit) for i,bit in enumerate(bitsa)]
    return reduce(lambda x,y: x+y,g)    

Also, as a final suggestion, why wouldn't you allow python do the things for you? It has built-in support for arbitrary long integers, so all your examples are equvivalent to just a*b, or, if you want the result to be in binary form "{0:b}".format(a*b)

Answer 2

Isn't multiplying in GF(2) just bit wise and? So couldn't you just do:

x = int("1001",2)
y = int("1010",2)
z = x&y
print "{0:b}".format(z)