0
$\begingroup$

Find a $7^{th}$ degree polynomial $p(x)$ in $\mathbb{Z}_{41}$, so that

$$ p(14^i) = i\ (mod\ 41)\ \forall i = 0,1,\ldots,7. $$

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

How does one solve such a task? I think it should be solved using FFT algorithm.

$\endgroup$
1
  • $\begingroup$ Hello and welcome! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you edit your question to write your thoughts and what you could not figure out. For instance, why do you think it should be solved using FFT? What did you try, to use a FFT? What other approaches did you consider? It will definitely draw more answers to your post. Until then, the question may be voted to be closed / downvoted. $\endgroup$
    – D.W.
    Jun 21, 2015 at 23:05

2 Answers 2

Reset to default
3
$\begingroup$

Well I don't know how to solve it with a FFT, but you can solve it using Gaussian elimination ($\mathbb{Z}_{41}$ is a field, so that all works). First build the system of equations which asserts for every $i$ that $p(14^i) \equiv i \mod 41$, which looks like this (it has some sweet symmetry):

$ \left( \begin{array}{cccccccc|c} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 14 & 32 & 38 & 40 & 27 & 9 & 3 & 1 \\ 1 & 32 & 40 & 9 & 1 & 32 & 40 & 9 & 2 \\ 1 & 38 & 9 & 14 & 40 & 3 & 32 & 27 & 3 \\ 1 & 40 & 1 & 40 & 1 & 40 & 1 & 40 & 4 \\ 1 & 27 & 32 & 3 & 40 & 14 & 9 & 38 & 5 \\ 1 & 9 & 40 & 32 & 1 & 9 & 40 & 32 & 6 \\ 1 & 3 & 9 & 27 & 40 & 38 & 32 & 14 & 7 \\ \end{array} \right) $

Then take the RREF (don't throw it in just any solver, it has to work with finite fields here and most assume reals), you get this

$ \left( \begin{array}{cccccccc|c} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 24 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 21 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 36 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 30 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 20 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 10 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 19 \\ \end{array} \right) $

So in the end the polynomial is $24 + 21x + 36x^2 + 30x^3 + 20x^4 + 10x^5 + 4x^6 + 19x^7$

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. You get RREF by Gauss-Jordan elimination, am I correct? $\endgroup$
    – blur
    Jun 21, 2015 at 11:23
  • $\begingroup$ @blur yes that is correct $\endgroup$
    – harold
    Jun 21, 2015 at 11:28
2
$\begingroup$

Lagrange interpolation is another chance.

$$ p(x) = \sum_{i=0}^{7}i\cdot\!\!\!\prod_{\substack{j\in [0,7]\\j\neq i}}\frac{x-14^j}{14^i-14^j} $$ works for sure: since $14$ has order $40$ in $\mathbb{F}_{41}^*$, no denominator in the previous expression is zero.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .