Ask Your Question

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

asked 2019-10-15 06:00:31 -0500

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

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

2 answers

Sort by ยป oldest newest most voted

answered 2019-10-16 05:36:05 -0500

dan_fulea gravatar image

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()
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()
sage: set( yy.minpoly() for yy in y_list )
{x^4 + x^3 + x^2 + x + 1}
edit flag offensive delete link more


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

rburing gravatar imagerburing ( 2019-10-16 07:03:11 -0500 )edit

Thank you!

sashkent3 gravatar imagesashkent3 ( 2019-10-17 05:09:35 -0500 )edit

answered 2019-10-16 11:16:14 -0500

nbruin gravatar image

updated 2019-10-16 11:17:08 -0500

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
sage: kxu.<u>=kx[]
sage: kxy.<y>=kx.extension(u^2+x*u+1)
sage: y^2+x*y+1
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
sage: y^2+x*y+1
edit flag offensive delete link more


I see, thank you so much!

sashkent3 gravatar imagesashkent3 ( 2019-10-17 05:08:24 -0500 )edit

Question Tools

1 follower


Asked: 2019-10-15 05:41:50 -0500

Seen: 54 times

Last updated: Oct 16 '19