I have a $p$ degree polynomial where $p$ is prime, I want to find the value of this polynomial at all points from $1$ to $p-1$,to make the fft on this polynomial easier I padded it with zeroes up to length to the next power of $2$ greater than p(note that here $p$ and $n$ are both large, the padded length is $2^{20}$ here $p-1$ is a multiple of power of $2$), now I should find the value of this polynomial from $0$ to $2^{20}-1$ but since $2^{20}$ has no primitive root, I cannot do fft on this size. So my question is how do I proceed. I tried finding primitive root of $2^{20}$ modulo some prime $p_2$ of the form $k\cdot 2^{20} +1$, but doing so, the $n$ powers of that primitive root${}^k$ did not give me all values from $0$ to $n-1$. How should I deal with this problem? Although my approach might be wrong new methods are welcome, the original goal is to find value of the polynomial at all points from $0$ to $p-1$ in time $O(n\log n)$.

  • $\begingroup$ What is $n$ here? The first mention of it is that it is large $\endgroup$ – Hagen von Eitzen Jul 11 '16 at 4:41
  • $\begingroup$ n here is the padded length of 2^20 $\endgroup$ – user346777 Jul 11 '16 at 4:42
  • $\begingroup$ Ah, so with $n\approx 2p$ we have $n=O(p)$ and so your really original goal is $O(p\log p)$, I presume $\endgroup$ – Hagen von Eitzen Jul 11 '16 at 4:43
  • $\begingroup$ yes that is my primary goal! $\endgroup$ – user346777 Jul 11 '16 at 4:44
  • $\begingroup$ That's an ambitious goal. Merely writing out $p$ values in the range $0,\ldots,p-1$ takes $O(p\log p)$ time. $\endgroup$ – Hagen von Eitzen Jul 11 '16 at 4:47

Your Answer

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

Browse other questions tagged or ask your own question.