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

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?

edit retag close merge delete

Sort by » oldest newest most voted

Apparently, though r is a unit in the polynomial ring, it is not necessarilly equal to 1, but it is a polynomial of degree 0, so you can assert instead r.is_unit() and replace inv = GF(inv_bar) with inv = GF(inv_bar)/GF(r) or inv = GF(inv_bar/GF.base_ring()(r)) if you do not want to rely on division in GF to redefine it.

more