# Modular Inverse over some given finite field. Which method is more efficient?

I'm trying to do division in some given finite field (let's say mod p). I have 2 Python methods here that are currently doing that, but I'm not sure which is better or if 1 or both is simply wrong. This seems too math-specific and off-topic for Stack Overflow. Originally, I was going about this completely wrong and was going to simply do $(a/b)\%p$ to keep it within the mod p. However, it seems like I'm supposed to be using the modular inverse so that a/b actually computes (a*(modular inverse of b mod p)) mod p. I've been looking over: http://en.wikipedia.org/wiki/Finite_field_arithmetic http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

I'm still shaky on whether I'm going in the right direction or if I'm just on the slow boat to nowhere. Here are the methods I'm using:

def extendedEuclideanGF2(self,a,b):
"""extended euclidean. a,b are values 10110011... in integer form; returns gcd of (a,b), and factors s and t"""
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("Extended Euclidean  [%d] * [%d] + [%d] * [%d] = [%d]" % (inita,prevx,initb,prevy,a))
return a,prevx,prevy

def extendedEuclideanGF2123(self, 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

def modular_inverse(self,mod):
"""a,mod are GF(2) polynomials like x**7 + x**3 + x**0 ...; returns modular inverse of a,mod"""
if self.polyVariableCheck(mod) == False:
return "error: variables of [%s] and [%s] do not match"%(self.string,other.string)
gcd,s,t = self.extendedEuclideanGF2(self.bin,mod.bin); s = int("{0:b}".format(s))
initmi = s%mod.bin; mi = int("{0:b}".format(initmi))
print ("Modular Inverse [%d] * [%d] mod [%d] = 1"%(self.bin,initmi,mod.bin))
if gcd !=1: return GF2Polynomial(self.outFormat(mi)),False
return GF2Polynomial(self.outFormat(mi))


polyVariableCheck() just verifies that the 2 input polynomials (taken in as strings) have matching variables. return GF2Polynomial(self.outFormat(mi)) just references that class's name and uses the outFormat() in order to put it back into polynomial format (as a string). The modular_inverse() probably isn't really necessary here, but I'm including it just in case that helps in seeing the big picture.

-
Are you working mod $p$ or in a finite field of prime power order? The first case is much easier. – Alex Becker Aug 15 '13 at 1:41
@AlexBecker I'm taking in some polynomial in 2m then another that acts as p. Another polynomial is taken in, and initialized in some field the same way, then all operations after that can only occur if the 2 fields are matching. – stackuser Aug 15 '13 at 2:44