Ask Your Question

Difference of finite fields

asked 2021-02-16 17:43:25 +0200

Alain Ngalani gravatar image

I'm trying to write a funcion that included a for cycle.

This cycle should take all the elements in the set GF(16)\GF(4).

However I'm having some probelms with this, I tried using .difference but this way doesn't work as intended, the resulting set ends up having 14 elements instead of 12 as I want.

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2021-02-16 22:08:34 +0200

Max Alekseyev gravatar image

updated 2021-02-16 22:09:34 +0200

We need an explicit embedding of GF(4) into GF(16). Viewing GF(16) as an extension of GF(4), we can create a list of elements from GF(16)\GF(4) as follows:

F.<z> = GF(4)                             # GF(4)
R.<x> = F[]                                # polynomials in x over GF(4)
p = R.irreducible_element(2)     # some irreducible polynomial over GF(4) of degree 2
K = R.quotient_ring(p, 'a')          # GF(16) as a factor ring GF(4)[x] / (p(x))
[t for t in K if t.lift().degree() > 0]

It gives the following 12 elements:

 z*a + z,
 z*a + z + 1,
 z*a + 1,
 (z + 1)*a,
 (z + 1)*a + z,
 (z + 1)*a + z + 1,
 (z + 1)*a + 1,
 a + z,
 a + z + 1,
 a + 1]

where $\{0,1,z,1+z\}$ form GF(4) (and polynomials of degree $\leq 0$ in R), and a is a zero of the polynomial p ($=x^2 + (z + 1)x + 1$ in the above example).

P.S. You may find this answer also relevant to your question.

edit flag offensive delete link more


Nice, However mine was only an example, I need to do this for different extensions that may have different dimensions so I can't force polynomial to be of degree 2

Alain Ngalani gravatar imageAlain Ngalani ( 2021-02-17 22:10:40 +0200 )edit

You can specify the needed degree d for polynomial p as p = R.irreducible_element(d).

Max Alekseyev gravatar imageMax Alekseyev ( 2021-02-17 23:29:24 +0200 )edit

answered 2021-02-20 13:52:26 +0200

Alain Ngalani gravatar image

updated 2021-02-20 13:53:04 +0200

At the end I settled for this solution :

  def FieldM(q, n):
  k.<t> = GF(q^n)
  Frob = k.frobenius_endomorphism()
  for a in k:
  for l in divisors(n):
      if l!=n:  
        for a in k:
            if a==power(Frob, l)(a):
               if a in K:

Where we have the function power defined as such

    def power(func, n):
           def pow(x, i=n):
               return func(pow(x, i-1)) if i > 0 else x
           return pow
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


Asked: 2021-02-16 17:43:25 +0200

Seen: 63 times

Last updated: Feb 20