Ask Your Question
0

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

asked 2018-11-14 19:53:03 +0100

Jsevillamol gravatar image

updated 2018-11-14 19:59:10 +0100

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2018-11-14 22:41:29 +0100

tmonteil gravatar image

updated 2018-11-14 23:23:04 +0100

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-11-14 19:53:03 +0100

Seen: 909 times

Last updated: Nov 14 '18