Python multiplicative inverse in GF(2) finite field -

these 2 functions perform extended euclidean algorithm, , find multiplicative inverse. order seems right, it's not coming i'm expecting per tool u of sydney http://magma.maths.usyd.edu.au/calc/ , since done in gf(2) finite field, think i'm missing key step translates base 10 field.

this tested , worked on base 10, taking in polynomials binary coefficients might not possible here. question parts of python incorrectly applying algorithm, such // floor, may not carry function capable of in base 10 able in gf(2).

the tool above can tested 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 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), , factors s , t  def modular_inverse(self,a,mod): # a,mod 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 polynomials in binary form of course:

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

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

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

number objects in python base-10. converting numbers binary strings, integers has no effect. here alternative version of function should work on a , b base-10 ints , return them in binary. can remove bin() function return numbers in base-10, or use lambda x: int("%d".format(x)) convert a , b binary decimal in first line of function.

def extendedeuclideangf2(a, b): # extended euclidean. a,b values 10110011... in         integer form     inita, initb = a, b   # if , b given 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 binary value in decimal number     return i2b(a), i2b(prevx), i2b(prevy)  # returns gcd of (a,b), , factors s , t 

all said, don't use lambdas in function - i'd suggest writing program avoid using binary altogether, can converting from/to binary @ interface of program source data.