ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 31 Aug 2019 11:53:15 +0200Polynomial functions over nonprime finite fieldshttps://ask.sagemath.org/question/47680/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).Sat, 31 Aug 2019 00:28:38 +0200https://ask.sagemath.org/question/47680/polynomial-functions-over-nonprime-finite-fields/Answer by tmonteil for <p>What is the correct way to construct polynomial functions over nonprime finite fields?</p>
<p>Here is the code I have come up with.</p>
<pre><code>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)
</code></pre>
<p>Why is it treating P as a polynomial GF(3)->GF(3) instead of GF(27)->GF(27)?</p>
<p>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).</p>
https://ask.sagemath.org/question/47680/polynomial-functions-over-nonprime-finite-fields/?answer=47682#post-id-47682Regarding 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)]Sat, 31 Aug 2019 11:02:09 +0200https://ask.sagemath.org/question/47680/polynomial-functions-over-nonprime-finite-fields/?answer=47682#post-id-47682Answer by rburing for <p>What is the correct way to construct polynomial functions over nonprime finite fields?</p>
<p>Here is the code I have come up with.</p>
<pre><code>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)
</code></pre>
<p>Why is it treating P as a polynomial GF(3)->GF(3) instead of GF(27)->GF(27)?</p>
<p>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).</p>
https://ask.sagemath.org/question/47680/polynomial-functions-over-nonprime-finite-fields/?answer=47684#post-id-47684From 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)]Sat, 31 Aug 2019 11:53:15 +0200https://ask.sagemath.org/question/47680/polynomial-functions-over-nonprime-finite-fields/?answer=47684#post-id-47684