Ask Your Question

Polynomial functions over nonprime finite fields

asked 2019-08-30 17:28:38 -0500

nate_n gravatar image

updated 2019-09-03 06:28:53 -0500

FrédéricC gravatar image

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)]


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

2 answers

Sort by » oldest newest most voted

answered 2019-08-31 04:53:15 -0500

rburing gravatar image

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
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)]
edit flag offensive delete link more

answered 2019-08-31 04:02:09 -0500

tmonteil gravatar image

updated 2019-08-31 04:07:45 -0500

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)]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2019-08-30 17:28:38 -0500

Seen: 99 times

Last updated: Aug 31 '19