For didactic purposes, I am trying to write my own function to compute the inverse in a finite field.
So far my code is like this:
# Extended Euclides Algorithm
def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0, r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
# Inverse in finite fields
def GF_inverse(elem):
"""
INPUT: element a from a finite field F_q
OUTPUT: inverse of the element
"""
GF = elem.parent()
f = GF.modulus() # defining polynomial of the field
ZpX = f.parent()
elem_bar = ZpX(elem) # representant of x in Zp[x]
r, inv_bar, _ = extended_euclides(elem_bar, f)
print(r)
assert(r == 1) # since Fq is a field, all elements are units
inv = GF(inv_bar) # elevate sbar
return inv
# EXAMPLE
GF9.<a> = GF(3^2)
elem = GF9(2*a+1)
inv = GF_inverse(elem)
print("The inverse of {} is {}".format(elem, inv))
assert(elem*inv == 1)
The idea why this should work is that $GF(p^k) = Zp[x] / (f)$ for $f\in Zp[x]$ an irreducible polynomial of degree $k$.
Therefore $elem$ is represented by $elem_bar + c*f$ for any $c\in Zp[x]$
So $inv * elem = 1 \implies \bar{inv} * \bar{elem} + c*f = 1 = gcd(\bar{elem}, f)$ (since $f$ is irreducible and $elem \ne 0$). And therefore a representative of the inverse is a bezoit coefficient.
The problem is that my code does not really work. The snippet above produces the following output:
2
The inverse of 2*a + 1 is a
Error in lines 15-15
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
AssertionError
What is going on? Is my understanding of the math wrong or my code?
