title: Python multiplicative inverse in GF(2) finite field
body: <p>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 <a href="http://magma.maths.usyd.edu.au/calc/">http://magma.maths.usyd.edu.au/calc/</a> 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.</p>
  
  <p>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).</p>
  
  <p>The tool above can be tested like this:</p>
  
  <pre><code>R&lt;x&gt;:=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;
  </code></pre>
  
  <p>The functions:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>I've been testing with polynomials like this but in binary form of course:</p>
  
  <pre><code>p = "x**13 + x**1 + x**0" 
  q = "x**12 + x**1"
  </code></pre>