6

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"
stackuser
  • 869
  • 16
  • 34

1 Answers1

4

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.

C Gearhart
  • 296
  • 1
  • 5
  • thanks. i'm trying to use this in division within a finite field. not sure if this is right but `return self * (mi % min(other,self)) % min(other,self)` where mi is the mod_inverse of self and other. what do you think? – stackuser Aug 15 '13 at 02:34
  • 1
    I see the real problem here: the rules for arithmetic in GF2 are *not* the same as the rules for integers. The operators in Python do not obey GF2 arithmetic - they perform carry operations. You could *make* them behave like GF2 by writing a GF2 class, but if you're trying to perform division in GF2, it won't make much sense to implement `//` and `%` in the GF2 class. – C Gearhart Aug 23 '13 at 01:51