Fast polynomial calculation over $\mathbb{Z}_{487}$

Question

Given a polynomial $a(x)$ of degree at most $242$ over $\mathbb{Z}_{487}$, I'd like to choose distinct values $x_0, x_1, . . . , x_{242} ∈ \mathbb{Z}_{487}$, such that I'll be able to calculate $a(x_j )$ for all $j = 0, . . . , 242$ by calculating three polynomials $a _0 (x), a_1(x), a_2(x)$ of degree at most $80$ for $81$ different values of $x$.

So first of all I divided $a(x)$ into sub-polynomials, simply by: $$\begin{align*} a(x)=x^{162}\cdot&\left( a_{242}\cdot x ^ {80}+...+a_{163}\cdot x+a_{162} \right)+\\ & x^{81}\cdot\left( a_{161}\cdot x ^ {80}+...+a_{82}\cdot x+a_{81} \right)+\\ &\left( a_{80}\cdot x ^ {80}+...+a_{1}\cdot x+a_{0} \right)\end{align*}$$

Now I have shown that $2^{243} = 1 \mod 487$, and that for every $1\leq a \leq 242: \,\,\, 2^a \neq 1 \mod 487$.

I wanted to use this so that I can choose distinct $x_i$ by $x_i=2^i \mod 487$ for all $0\leq i \leq 242$. Now I thought taking triples, and for that I had two ideas:

1. Choose triples $x_i,x_{i+1},x_{i+2}$ for each $0\leq i\leq 242$ such that $i = 0 \mod 3$.
2. Choose triples $x_i,x_{i+81},x_{i+162}$ for each $0 \leq i \leq 80$.

In any case, given a trio, I wanted to calculate only $a_2(x_i), \,a_1(x_i), \,a_0(x_i)$, and then using them to calculate $a(x_i),\,a(x_{i^{'}}),\,a(x_{i^{''}})$, where ${i^{'}} $and ${i^{''}}$ will be the next in my trio (depending on which idea to choose).

The problem is, I either got confused and all that's left is obvious, or I just can't seem to make those last few steps. If Im on the right way, can someone help me here? Or perhaps I should choose other trios? Or if not, maybe there's a hint that can help me out?

Answer 1

You can very efficiently compute $a(x_j)$ for each of those 243 values of $x_j$ by simply evaluating $a(\cdot)$ using Horner's rule. The running time is 243 evaluations of $a(\cdot)$, and each evaluation requires 243 modular multiplications and 243 modular additions. That's a total of $243^2 \approx 2^{16}$ modular multiplications. Consequently, the total running time will be extremely efficient, even without trying to split this into three polynomials $a_0(x),a_1(x),a_2(x)$.

If you want a more efficient method, a better approach is to use a Discrete Fourier Transform. You can use a DFT over $\mathbb{Z}_{487}$ to evaluate $a(x)$ at 256 different points in running time that's asymptotically $O(n \lg n)$, where here concretely $n = 256$. [Alternatively, you could use the Number-theoretic transform for $\mathbb{Z}_{487}$ to evaluate $a(x)$ at $486$ points, and do all your calculations in $\mathbb{Z}_{487}$.]