# Finite field F_16=F_4[y]/(y**2+xy+1) (where F_4=F_2[x]/(x**2+x+1)) [closed]

So SageMath is new for me and I'm trying to find the parent element of F_16. My code is simple, but I have no idea why it doesn't work. Here it is:

F.<x> = GF(2)[]

K.<y> = GF(16, modulus=y^2 + x * y + 1)

The result is TypeError: not a constant polynomial

Is it about y^2 + x * y + 1? Why should it be constant? I'll appreciate any help.

edit retag reopen merge delete

### Closed for the following reason the question is answered, right answer was accepted by sashkent3 close date 2019-10-17 12:09:57.068701

Sort by » oldest newest most voted

To construct GF(16) as a two-step extension, which is what it appears you are interested in, would go as follows.

sage: k=GF(2)
sage: kx.<x>=k[]
sage: kt.<t>=k[]
sage: kx.<x>=k.extension(t^2+t+1)
sage: x^2+x+1
0
sage: kxu.<u>=kx[]
sage: kxy.<y>=kx.extension(u^2+x*u+1)
sage: y^2+x*y+1
0
sage: kxy
Univariate Quotient Polynomial Ring in y over Finite Field in x of size 2^2 with modulus y^2 + x*y + 1


This has a slight problem: the field kxy constructed above is a relatively inefficient version of GF(16): sage just knows it's a quotient of a polynomial ring, whereas for GF(16) sage has a specialized implementation that should be quite fast.

As suggested by dan_fuela one you can just construct GF(16) any way you want and then find the elements x,y with the desired properties in it. You don't have to exhaustively search the whole field for the right minimal polynomials to occur though: you can just ask sage to solve the relevant polynomial equation. In GF(16) it doesn't matter much because it's a tiny field, but enumerating larger fields quickly becomes undoable.

sage: kxy=GF(16)
sage: kxyT.<T>=kxy[]
sage: x=(T^2+T+1).roots()[0][0] # this just selects the first root from the full list of roots with multiplicities
sage: y=(T^2+x*T+1).roots()[0][0]
sage: x^2+x+1
0
sage: y^2+x*y+1
0

more

I see, thank you so much!

( 2019-10-17 12:08:24 +0200 )edit

Things are not so simple.

First of all, the y inside GF(16, modulus=y^2 + x * y + 1) is not defined. If the R.H.S. is not defined, the code will crash for the one or the other reason. For my taste, the simplest mode to construct the field $K$ with $16$ elements and in it two elements $x,y$ that satisfy $x^2+x+1=0$ and $y^2+xy+1=0$ is as follows:

sage: K = GF(2^4)
sage: x_list = [ x for x in K if x^2 + x + 1 == 0 ]
sage: x = x_list[0]    # we pick one element in the above list...
sage: x.multiplicative_order()
3
sage: y_list = [ y for y in K if y^2 + x*y + 1 == 0 ]
sage: y = y_list[0]    # we pick one element in the above list...
sage: y.multiplicative_order()
5
sage: set( yy.minpoly() for yy in y_list )
{x^4 + x^3 + x^2 + x + 1}

more

To avoid constructing the list you could use next on the iterator.

( 2019-10-16 14:03:11 +0200 )edit

Thank you!

( 2019-10-17 12:09:35 +0200 )edit