Python multiplicative inverse in GF(2) finite field

Question

These 2 functions perform Extended Euclidean Algorithm, and then find the multiplicative inverse. The order seems right, but it's not coming back with what I'm expecting as per this tool from U of Sydney http://magma.maths.usyd.edu.au/calc/ and since this is done in the GF(2) finite field, I think I'm missing some key step that translates from base 10 into this field.

This was tested and worked on base 10, but taking in polynomials with binary coefficients might not be possible here. So my question is what parts of Python am I incorrectly applying to this algorithm, such as // floor, that may not carry from what the function was capable of in base 10 to be able to do this in GF(2).

The tool above can be tested like this:

R<x>:=PolynomialRing(GF(2));
p:=x^13+x+1; q:=x^12+x;
g,r,s:=XGCD(p,q);

g eq r*p+s*q;

g,r,s;

The functions:

def extendedEuclideanGF2(self,a,b): # extended euclidean. a,b are values 10110011... in integer form
    inita,initb=a,b;  x,prevx=0,1;  y,prevy = 1,0
    while b != 0:
        q = int("{0:b}".format(a//b),2)
        a,b = b,int("{0:b}".format(a%b),2);
        x,prevx = (int("{0:b}".format(prevx-q*x)), int("{0:b}".format(x,2)));  y,prevy=(prevy-q*y, y)
    print("Euclidean  %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(self,a,mod): # a,mod are integer values of 101010111... form
    a,mod = prepBinary(a,mod)
    bitsa = int("{0:b}".format(a),2); bitsb = int("{0:b}".format(mod),2)
    #return bitsa,bitsb,type(bitsa),type(bitsb),a,mod,type(a),type(mod)
    gcd,s,t = extendedEuclideanGF2(a,mod); s = int("{0:b}".format(s))
    initmi = s%mod; mi = int("{0:b}".format(initmi))
    print ("M Inverse %d * %d mod %d = 1"%(a,initmi,mod))
    if gcd !=1: return mi,False
    return mi   # returns modular inverse of a,mod

I've been testing with polynomials like this but in binary form of course:

p = "x**13 + x**1 + x**0" 
q = "x**12 + x**1"

Answer 1

The function worked when tested with base-10 because all of your conversions int("{0:b}".format(x)) have no effect on x:

37 == int("{0:b}".format(37), 2)  # >>> True

Number objects in python are all base-10. Converting your numbers to binary strings, then back to integers has no effect. Here is an alternative version of your function that should work on a and b as base-10 ints and return them in binary. You can remove the bin() function to return the numbers in base-10, or use something like lambda x: int("%d".format(x)) to convert a and b from binary to decimal in the first line of the function.

def extendedEuclideanGF2(a, b): # extended euclidean. a,b are values 10110011... in         integer form
    inita, initb = a, b   # if a and b are given as base-10 ints
    x, prevx = 0, 1
    y, prevy = 1, 0
    while b != 0:
        q = a//b
        a, b = b, a%b
        x, prevx = prevx - q*x, x
        y, prevy = prevy - q*y, y
    print("Euclidean  %d * %d + %d * %d = %d" % (inita, prevx, initb, prevy, a))
    i2b = lambda n: int("{0:b}".format(n))  # convert decimal number to a binary value in a decimal number
    return i2b(a), i2b(prevx), i2b(prevy)  # returns gcd of (a,b), and factors s and t

All that said, don't use lambdas in a function like this - I'd suggest writing your program to avoid using binary altogether, which you can do by only converting from/to binary at the interface of your program with source data.