Computing the inverse in GF(p^k) using the extended euclides algorithm

savecancel

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 $\bar{elem} + 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?