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

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?

• ok but why $\mathbb{Z}_{487}$? arent you really asking about an algorithm for $\mathbb{Z}_n$ with $n=487$ as an example? – vzn Dec 11 '14 at 22:28

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}$.]
• I don't see how is this going to help me to calculate $a(x)$ for $243$ values by calculating $a_0(x),a_1(x),a_2(x)$ for $81$ values each? The main point is that I get to choose the values $x_1,...,x_{243}$, and this is why I thought taking them as $2^i$, but even reading the number-theoretic transform, I still can't find a way to divide them into trios, such that in every trio there'll be a need to calculate $a_0(x), \,a_1(x)$ and $a_2(x)$ only once, and then I can easily calculate $a(x)$ for each of the trio. – Eric_ Dec 12 '14 at 11:45
• @Eric_, if your goal is to calculate $a(x)$ for 243 values, my suggestion is to do it entirely different way. The question assumes that the best way to do it will be to calculate $a_0(x),a_1(x),a_2(x)$ for 81 values each, but I think you can achieve it more effectively via a totally different route. In other words, your question seems to presuppose that the best solution will have a particular characteristic (it will involve calculating $a_0(x),a_1(x),a_2(x)$ for 81 values each), but I'm saying that doesn't seem to be the case. – D.W. Dec 12 '14 at 18:13
• That I did understand, but I feel more comfortable using my type of suggested idea, and the entire point of my question was the choosing of such values and how to divide them into triples. Apparently my idea of taking $x_i = 2^i \mod 487$ doesn't work so smooth as I hoped, or perhaps I just dont see how to divide them to such trios? – Eric_ Dec 13 '14 at 16:51