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

savecancel

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

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}