Processing math: 100%
Ask Your Question
0

Difference of finite fields

asked 4 years ago

Alain Ngalani gravatar image

updated 2 years ago

FrédéricC 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.

Preview: (hide)

2 Answers

Sort by » oldest newest most voted
1

answered 4 years ago

Max Alekseyev gravatar image

updated 4 years ago

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*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,
 a + z,
 a + z + 1,
 a + 1]

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

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

Preview: (hide)
link

Comments

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 ( 4 years ago )

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

Max Alekseyev gravatar imageMax Alekseyev ( 4 years ago )
0

answered 4 years ago

Alain Ngalani gravatar image

updated 4 years ago

At the end I settled for this solution :

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

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
Preview: (hide)
link

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: 4 years ago

Seen: 872 times

Last updated: Feb 20 '21