Multiplicative Python Reverse in GF (2) Finite Field

Question

These 2 functions perform the Extended Euclidean Algorithm, and then find the multiplicative inverse. The order seems to be correct, but it does not return with what I expect from U of Sydney on this tool http://magma.maths.usyd.edu.au/calc/ , and since this is done in GF (2), the final field , I think I missed some key step that translates from base 10 to this field.

This has been tested and processed based on 10, but taking polynomials with binary coefficients with them may not be possible. Therefore, my question is which parts of Python I incorrectly apply to this algorithm, for example // floor, which can carry on the fact that a function in base 10 could be able to do this in GF (2).

The tool above can be tested as follows:

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; 

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 tested such polynomials, but in binary form:

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

Answer 1

The function worked when testing with base-10, because all your conversions int("{0:b}".format(x)) do not affect x:

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

The number of objects in python is all base-10. Converting your numbers to binary strings and then back to integer values ​​is not affected. Here is an alternate version of your function that should work on a and b as base-10 ints and return them in binary format. You can remove the bin() function to return 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, do not use lambdas in a function like this: I suggest writing your program to avoid using all binary code, which you can only do by converting from / to binary in the interface of your program using a data source.