1
$\begingroup$

Find a $7^\text{th}$ degree polynomial $p(x)$ in $\mathbb{Z}_{41}[x]$, so that $$ p(14^i) = i\pmod{41}\ \forall i = 0,1,\ldots,7. $$

Hint: $3$ is the $8^\text{th}$ primitive root of unity and $3 \cdot 14 = 8 \cdot 36 = 1$ in $\mathbb{Z}_{41}$.

How does one solve such a task?

$\endgroup$
1
$\begingroup$

I shall write $w$ for $14$. Note that $w^8=1$. For $k=0,1,2,\ldots,8$, consider the polynomial $$f_k(x):=\frac{w^k}{8}\left(\frac{x^8-1}{x-w^k}\right)=\frac{1}{8}\left(\frac{\left(w^{-k}x\right)^8-1}{w^{-k}x-1}\right)=\frac{1}{8}\left(\sum_{r=0}^7\,w^{-kr}x^r\right)\,.$$ Furthermore, for $l=0,1,2,\ldots,8$ with $l \neq k$, $f_k\left(w^l\right)=0$, whereas $f_k\left(w^k\right)=1$. The unique polynomial $p(x) \in \mathbb{F}_{41}[x]$ satisfying the condition is $p(x)=\sum\limits_{k=0}^7\,k\,f_k(x)$. That is, $$p(x)=\frac{1}{8}\,\sum_{k=0}^7\,k\,\sum_{r=0}^7\,w^{-kr}x^r=\frac{1}{8}\,\sum_{r=0}^7\,\left(\sum_{k=0}^7\,k\,w^{-kr}\right)\,x^r\,.$$

Now, consider $g(x)=\frac{x^8-1}{x-1}=\sum_{r=0}^7\,x^r$. Then, $$\sum_{k=0}^7\,k\,x^k=x\,g'(x)=\frac{8x^8}{x-1}-\frac{x\left(x^8-1\right)}{(x-1)^2}\,.$$ Thus, $$\sum_{k=0}^7\,k\,w^{-kr}=w^{-r}\,g'\left(w^{-r}\right)=\frac{8}{w^{-r}-1}$$ for $r=1,2,\ldots,7$. Consequently, $$p(x)=24+\sum_{r=1}^7\,\frac{1}{w^{-r}-1}\,x^r=24+\sum_{r=1}^7\,\frac{1}{3^r-1}\,x^r\,,$$ as $w^{-1}=14^{-1}=3$. That is, $$p(x)=24+21x+36x^2+30x^3+20x^4+10x^5+4x^6+19x^7\,.$$

$\endgroup$
  • $\begingroup$ Thank you for your answer, but I'am looking for a solution that uses FFT algorithm. I will try my luck at computer science stackexchange. $\endgroup$ – blur Jun 21 '15 at 9:48
  • $\begingroup$ If that is what you wanted, then let $p(x)=\sum_{k=0}^7\,p_kx^k$ for some $p_0,p_1,p_2,\ldots,p_7\in\mathbb{F}_{41}$. Then, consider the FFT matrix $\mathbf{F}:=\left[w^{ij}\right]_{i,j\in[7]}$, where $[7]:=\{0,1,2,\ldots,7\}$, and vectors $\mathbf{p}:=\left(p_0,p_1,\ldots,p_7\right)$ and $\mathbf{q}:=\left(0,1,2,\ldots,7\right)$. The inverse is $\mathbf{F}^{-1}=\frac{1}{8}\left[w^{-ij}\right]_{i,j\in[7]}$. Hence, the condition on $p(x)$ is the same as saying $\mathbf{Fp}=\mathbf{q}$, which then implies $\mathbf{p}=\mathbf{F}^{-1}\mathbf{q}$, and the rest is only computation. $\endgroup$ – Batominovski Jun 21 '15 at 10:11
  • $\begingroup$ That is closer to what I was looking for, thank you. $\endgroup$ – blur Jun 21 '15 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.