# Evaluating a polynomial at root of unity over finite fields

Hi everyone!

I need to do some simulations for a project that I am working on. This involves the following "puzzle" which I don't know how to resolve. Your help is much appreciated.

Suppose I have a polynomial $F \in \mathbb{Z}[x]$. Let $p$ be a prime number and $F_p$ be the reduction of $F$ modulo $p$. In other words, $F_p \in \mathbb{F}_p[x]$. Let $n$ be a number relatively prime to $p$ and $\zeta_n$ is an $n$-primitive root of unity over $\mathbb{F}_p$. I want to compute the following number $F_p(\zeta_n) F_p(\zeta_n^{-1})$.

I searched on this website and the closest answer that I got is the following

I tried to modify this approach without success. More precisely, I do the following.

Step 1: To get $F_p$, I use F.change_ring(GF(p)).

Step 2: Define K=GF(p) and K.<w> = CyclotomicField(n).

Step 3: Compute F_p(w)*F_p(1/w)

It seems to me that Step 2 causes some problems. Additionally, the term 1/w also causes an issue as $1$ is recognized here as an integer and not an element over $\mathbb{F}_p$.

Please let me know if you have any comments or suggestions. Thank you very much!

Best wishes, Tung

edit retag close merge delete

Sort by ยป oldest newest most voted

An alternative way to think about the problem, shifting the solution on the mathematical side, is as follows. I will denote by $g$ the given polynomial with integer coefficients (instead of $F$), and by $\Bbb F=\Bbb F_p$ the field with $p$ elements. Let $\Phi_n$ be the $n$.th cyclotomic polynomial. So instead of $\zeta_n$, seen as an element of the field $\Bbb Q(\zeta_n)$ we will work with a variable $w$, seen as an element of the field $K=\Bbb Z(w)=\Bbb Z[W]/(\Phi_n(W))$, constructed as quotient of the polynomial ring in $W$, and $w$ is the class of $W$ modulo the ideal $J$ generated by $\Phi_n(W)$. We can build then $g(W)g(W^{n-1})$ as an element in the polynomial ring $\Bbb Z[W]$, then consider $g(w)g(w^{n-1})=g(w)g(w^{-1})$ by working in $\Bbb Z[W]$ modulo $J$. Now we pass to the quotient modulo $p$. This could have been done also earlier, sooner or later, we work in the ring $$R = \Bbb Z[W]/(\Phi_n(W),\ p) = \Bbb Z[W]/p/(\Phi_n(W)) = \Bbb F_p[W]/(\Phi_n(W))$$ The question tacitly assumes that the result does not depend on $W$. Let's see if this is the case in some example with $p=5$ and $n=2022$, my sample polynomial is $W+1$:

p, n = 5, 30
R.<W> = PolynomialRing(GF(p))
g = W + 1
Q.<w> = R.quotient(cyclotomic_polynomial(n)(W))
g(w) * g(w^(n-1))


I'm getting

4*w^7 + 4*w^6 + w^4 + w^3 + w^2 + w + 1


(I hope i have correctly understood the algebraic situation... do not see the reason why some corresponding Galois automorphisms in $w$ should invariate the expression $g(W)g(W^{-1})$ for a general $g$.)

more

I like this approach as it allows us to see the coefficients of $w^m$. My original goal is to show that $F(\zeta_n)F(\zeta_n^{-1})$ is not zero mod $p$ and this goal does not depend on the choice of $w$ as you explained.

( 2022-07-08 17:29:41 +0100 )edit

Perhaps, the easiest approach would be extending $GF(p)$ with $\zeta_n$ - like in the following example, where z stands for $\zeta_n$:

p, n = 7, 5
Fp.<x> = GF(p)[]
K.<z> = GF(p).extension(cyclotomic_polynomial(n))
f = x^2 + x + 1
print( f(z)*f(1/z) )

more

( 2022-07-08 17:27:15 +0100 )edit