Polynomial functions over nonprime finite fields

finite-fields

asked 5 years ago

nate_n
13 ●4

updated 5 years ago

FrédéricC

5456 ●4 ●44 ●122

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

add a comment

2 Answers

Sort by » oldest newest most voted

answered 5 years ago

rburing

10984 ●6 ●80 ●220 https://www.rburing.nl/

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

link

add a comment

answered 5 years ago

tmonteil
27493 ●32 ●205 ●519 http://wiki.sagemath.o...

updated 5 years ago

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

link

add a comment

Your Answer

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

Add Answer

Polynomial functions over nonprime finite fields

2 Answers

Your Answer

Question Tools

Stats

Related questions

Polynomial functions over nonprime finite fields savecancel

2 Answers

Your Answer

Question Tools

Stats

Related questions

Polynomial functions over nonprime finite fields