# Polynomial functions over nonprime finite fields

What is the correct way to construct polynomial functions over nonprime finite fields?

Here is the code I have come up with.

p = 3
q = 3

K = GF(p**q, 'c')
PR = PolynomialRing(K, 'x')
x = PR.gen()

# return the trace polynomial for Tr_{F_{ground}/F_{ground^exp}}
def get_trace_poly(ground, exp):
P = sum([x**((ground**i)) for i in range(0,exp)])
return P
# P = x^9 + x^3 + x
P = get_trace_poly(p,q)
e = [P(i) for i in range(0,p**q)]

print(e)


Why is it treating P as a polynomial GF(3)->GF(3) instead of GF(27)->GF(27)?

Also, is there something wrong with my understanding of the trace function? It seems to be true that the trace of GF(27) over GF(3) is supposed to be Tr(x)= x^9 + x^3 + x, but then Tr(1)=3 which isn't an element of GF(3).

edit retag close merge delete

Sort by » oldest newest most voted

From your expression for e it is clear that you want to interpret an integer $n < 27$ as an element of the field $K = \mathbb{F}_{27} = \mathbb{F}_3[c]$ by taking the base-3 digits of $n$ as coefficients of the powers of the generator $c$. To do this in Sage you should be more explicit, because coercion of integers into $K$ is the "modulo 3" operation, which is not what you want.

For example:

sage: K(17) # modulo 3
2
sage: 17.digits(base=3)
[2, 2, 1]
sage: K(17.digits(base=3)) # "vector" to field element
c^2 + 2*c + 2


So what works is:

e = [P(K(i.digits(p))) for i in srange(0,p**q)]

more

Regarding the first question, P is a polynomial over GF(27):

sage: P.parent()
Univariate Polynomial Ring in x over Finite Field in c of size 3^3


Now, when you write P(i) for i in range(0,p**q), you should understand that i is an integer, so it has to be transformed into an element of K to be accepted by P. This morphism maps 1 to 1, so every integer remains stuck int the prime field GF(3). The additive struture of GF(p**q) is that of $(\mathbb{Z}/p\mathbb{Z})^q$, not $\mathbb{Z}/p^q\mathbb{Z}$.

If you want to compute P on each value of K, you should directly iterate oeve relement of K:

sage: e = [P(i) for i in K]


and you will see that the result is very different.

If you prefer a more "cyclic" view, you can use the multiplicative generator of K, which you named c:

sage: c = K.gen()
sage: e = [P(c**i) for i in range(0,p**q)]

more