Ask Your Question

Evaluating a polynomial at root of unity over finite fields

asked 2022-07-08 06:14:32 +0100

tungnt gravatar image

updated 2022-07-08 06:19:31 +0100

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

2 Answers

Sort by ยป oldest newest most voted

answered 2022-07-08 10:21:39 +0100

dan_fulea gravatar image

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

edit flag offensive delete link more


Thank you for your answer!

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.

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

answered 2022-07-08 14:24:36 +0100

Max Alekseyev gravatar image

updated 2022-07-08 14:25:13 +0100

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


Thank you very much for your answer!

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

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2022-07-08 06:14:32 +0100

Seen: 160 times

Last updated: Jul 08 '22